i job sequencing problem målet är att hitta sekvensen av jobb,som är klar inom sina tidsfrister och ge maximal vinst.
om en uppsättning n-jobb ges som är förknippade med tidsfrister och vinst tjänas och ett jobb slutförs inom tidsfristen. Dessa jobb måste beställas på ett sådant sätt att det finns maximal vinst.
Låt oss ta ett exempel. Som visas i figur 1.1 ges en rad jobb där varje jobb har en tidsfrist och tillhörande vinst om jobbet är klart före tidsfristen. Det är också med tanke på att varje jobb tar en enda tidsenhet, så minsta möjliga tidsfrist för alla jobb är 1. Hur man maximerar den totala vinsten om bara ett jobb kan schemaläggas åt gången.
en enkel lösning är att generera alla delmängder av en viss uppsättning jobb och kontrollera enskilda delmängder för genomförbarhet av jobb i den delmängden. Håll koll på maximal vinst bland alla möjliga delmängder. Tidskomplexiteten för denna lösning är exponentiell.Vi kan också lösa detta problem med hjälp av girig metod som är mer optimal än enkel lösning.Så låt oss lösa detta problem via girig metod.
för att lösa jobbsekvenseringsproblemet via girig metod följ dessa steg:
- sortera alla jobb i minskande vinstordning.
- initiera resultatsekvensen som första jobb i sorterade jobb.
- gör följande för återstående n-1 jobb.
- om det aktuella jobbet kan passa i den aktuella resultatsekvensen utan att missa tidsfristen, Lägg till aktuellt jobb i resultatet. Annars ignorerar det nuvarande jobbet.
som du kan se i figur 1.1 är jobben redan i minskande vinstordning.Här har jobb 1 Den högsta vinsten och tidsfristen är 3 så sätt det jobbet mellan 2-3 som visas i figur 1.2.Jobb 2 har näst högsta vinst och tidsfristen är 4 så sätt det jobbet mellan 3-4 och gör detsamma för alla jobs.So den slutliga sekvensen är J4-J3-J1-J2 och den totala vinsten är 110.
du kan föredra koden för denna algoritm på https://www.geeksforgeeks.org/job-sequencing-problem.
tidskomplexiteten för denna lösning är O (n2).den kan optimeras genom ojämn datastruktur.
hoppas du gillar artikeln.Tack:)
