työn jaksottamisongelmassa tavoitteena on löytää työjärjestys,joka valmistuu määräajassa ja antaa mahdollisimman suuri hyöty.
jos annetaan joukko n työpaikkoja, jotka liittyvät määräaikoihin ja ansaitaan voitto ja työ valmistuu määräaikaansa mennessä. Nämä työt on järjestettävä niin, että saadaan mahdollisimman suuri voitto.
otetaan yksi esimerkki. Kuten kuvassa 1.1 esitetään joukko työpaikkoja, joissa jokaisella työllä on määräaika ja siihen liittyvä voitto, jos työ on valmis ennen määräaikaa. On myös annettu, että jokainen työ vie yhden aikayksikön, joten pienin mahdollinen määräaika mille tahansa työlle on 1. Miten maksimoida kokonaisvoitto, jos vain yksi työ voidaan ajoittaa kerrallaan.
yksinkertainen ratkaisu on tuottaa kaikki osajoukot tietyn joukon työpaikkoja ja tarkistaa yksittäisten osajoukko toteutettavuutta työpaikkojen että osajoukko. Pidä kirjaa maksimivoitosta kaikkien toteuttamiskelpoisten osajoukkojen joukossa. Tämän ratkaisun ajallinen monimutkaisuus on eksponentiaalinen.Voimme myös ratkaista tämän ongelman käyttämällä ahne menetelmä, joka on enemmän optimaalinen kuin yksinkertainen ratkaisu.Joten lets ratkaista tämän ongelman kautta ahne menetelmällä.
voit ratkaista työn sekvensointi ongelma kautta ahne menetelmä seuraa tätä vaihetta:
- Lajittele kaikki työt alenevassa järjestyksessä voiton.
- alustaa tulosjärjestys ensimmäisenä työnä lajitelluissa töissä.
- Do following for remaining n – 1 jobs.
- jos nykyinen työ mahtuu nykyiseen tulosjonoon ilman aikarajaa, Lisää nykyinen työ tulokseen. Muuten jätä nykyinen työ huomiotta.
kuten kuvasta 1.1 näkyy, työpaikat ovat jo alenevassa voittojärjestyksessä.Tässä työ 1 on suurin voitto ja määräaika on 3 Niin asettaa, että työ välillä 2-3 kuten kuvassa 1.2.Työ 2 on toiseksi korkein voitto ja määräaika on 4 Niin asettaa, että työ välillä 3-4 ja tehdä sama kaikille jobs.So finaalisarja on J4-J3-J1-J2 ja kokonaisvoitto 110.
voit suosia tämän algoritmin koodia kohdassa https://www.geeksforgeeks.org/job-sequencing-problem.
tämän ratkaisun ajallinen monimutkaisuus on O (n2).
Toivottavasti pidät artikkelista.Kiitos:)
