i job sekventering problem målet er at finde rækkefølgen af job,som er afsluttet inden for deres frister og give maksimal profit.
hvis der gives et sæt n-job, der er knyttet til frister, og fortjeneste optjenes, og et job er afsluttet inden dets frist. Disse job skal bestilles på en sådan måde, at der er maksimal fortjeneste.
lad os tage et eksempel. Som vist i figur 1.1 gives en række job, hvor hvert job har en deadline og tilhørende fortjeneste, hvis jobbet er færdigt inden deadline. Det er også givet, at hvert job tager en enkelt tidsenhed, så den mindste mulige frist for ethvert job er 1. Sådan maksimeres det samlede overskud, hvis kun et job kan planlægges ad gangen.
en simpel løsning er at generere alle undergrupper af et givet sæt job og kontrollere den enkelte delmængde for gennemførligheden af job i denne delmængde. Hold styr på maksimal fortjeneste blandt alle mulige undergrupper. Tidskompleksiteten af denne løsning er eksponentiel.Vi kan også løse dette problem ved hjælp af grådige metode, som er mere optimal end simpel løsning.Så lad os løse dette problem via grådige metode.
følg disse trin for at løse jobsekventeringsproblemet via grådig metode:
- Sorter alle job i faldende rækkefølge af overskud.
- Initialiser resultatsekvensen som første job i sorterede job.
- gør følgende for resterende N-1 job.
- hvis det aktuelle job kan passe ind i den aktuelle resultatsekvens uden at gå glip af deadline, skal du tilføje det aktuelle job til resultatet. Ellers ignorere det nuværende job.
som du kan se i figur 1.1, Er arbejdspladserne allerede i faldende rækkefølge.Her har job 1 den højeste fortjeneste, og fristen er 3, så indstil jobbet mellem 2-3 som vist i figur 1.2.Job 2 har næsthøjeste fortjeneste, og fristen er 4, så indstil det job mellem 3-4 og gør det samme for alle jobs.So den endelige sekvens er J4-J3-J1-J2, og det samlede overskud er 110.
du kan foretrække koden til denne algoritme på https://www.geeksforgeeks.org/job-sequencing-problem.
tidskompleksiteten af denne løsning er O(n2).det kan optimeres ved uensartet datastruktur.
håber du kan lide artiklen.Tak:)
