i jobb sekvensering problem målet er å finne sekvensen av jobber, som er fullført innen sine tidsfrister og gi maksimal profitt.
hvis et sett med n jobber er gitt som er knyttet til tidsfrister og fortjeneste er opptjent og en jobb er fullført innen fristen. Disse jobbene må bestilles på en slik måte at det er maksimalt overskudd.
La oss ta ett eksempel. Som vist i figur 1.1 er det gitt en rekke jobber der hver jobb har en frist og tilhørende fortjeneste hvis jobben er ferdig før fristen. Det er også gitt at hver jobb tar en enkelt tidsenhet, så den minste mulige fristen for enhver jobb er 1. Hvordan maksimere total fortjeneste hvis bare en jobb kan planlegges om gangen.
En enkel løsning er å generere alle delsett av gitt sett med jobber og sjekke individuelle delsett for gjennomførbarhet av jobber i det delsett. Hold styr på maksimal fortjeneste blant alle mulige undergrupper. Tidskompleksiteten til denne løsningen er eksponentiell.Vi kan også løse dette problemet ved hjelp av grådig metode som er mer optimal enn enkel løsning.Så kan løse dette problemet via grådig metode.
for å løse jobbsekvenseringsproblemet via grådig metode, følg disse trinnene:
- Sorter alle jobber i avtagende rekkefølge av fortjeneste.
- Initialiser resultatsekvensen som første jobb i sorterte jobber.
- Gjør følgende for gjenværende n-1 jobber.
- hvis gjeldende jobb får plass i gjeldende resultatsekvens uten å gå glipp av fristen, legger du til gjeldende jobb i resultatet. Ellers ignorerer den nåværende jobben.
som du kan se i figur 1.1 jobbene er allerede i synkende rekkefølge av profitt.Her har jobb 1 høyest fortjeneste og fristen er 3 så sett den jobben mellom 2-3 som vist i figur 1.2.Jobb 2 har nest høyeste fortjeneste og fristen er 4 så sett den jobben mellom 3-4 og gjør det samme for alle jobs.So den endelige sekvensen Er J4-J3-J1-J2 og totalresultatet er 110.
du kan foretrekke koden for denne algoritmen på https://www.geeksforgeeks.org/job-sequencing-problem.
tidskompleksiteten til denne løsningen Er O (n2). Den kan optimaliseres Av Disjoint Datastruktur.
Håper du liker artikkelen.Takk skal du ha:)
