Akers 1956-os algoritmusának kiterjesztése három feladatos problémákra
A dolgozatom témája Akers módszerének bemutatása, illetve ennek az algoritmusnak az általam kitalált kiterjesztése. Ezen algoritmusok speciális Job-Shop ütemezésre adnak optimális megoldást polinomiális időben.
Job-Shop ütemezés egy olyan probléma ami 'n' darab feladatból és 'm' darab gépből áll, minden feladatnak, minden géphez van egy hozzá rendelt ideje, illetve a gépek sorrendje is előre meghatározott feladatonként. Ez egy P versus NP nehéz probléma, ami azt jelenti, hogy nincs rá algoritmus ami polinomiális időben optimális megoldást ad, csak ha P=NP.
Akers 1956-ban megalkotott algoritmusa egy speciális Job-Shop ütemezésre ad optimális megoldást polinomiális időben, mégpedig akkor, amikor kettő feladat van és 'm' darab gép (az algoritmus nem is futtatható más esetekben). Az algoritmus egy kétdimenziós koordináta rendszerben szemléltethető, és a lépéseit is ott lehet végig követni. Az algoritmussal akár több eltérő, de optimális megoldást is kaphatunk, tehát nem csak egyet talál meg, hanem az összes optimálisat. Az általam kitalált tovább fejlesztése, arra épül, hogy míg Akers két dimenziót használt, addig én kiterjesztettem az algoritmust három dimenzióra, és így már egy három problémás/feladatos 'm' db gépes ütemezésre is tud az algoritmus optimális megoldást adni, tehát a dimenziók száma a feladatok számát határozzák meg.
Dolgozatomban tehát Akers módszerét, és ennek a módszernek a kiterjesztését fogom bemutatni.
szerző
-
Ponkházi András
Villamosmérnöki szak, alapképzés
alapképzés (BA/BSc)
konzulens
-
Dr. Villányi Balázs
docens, Elektronikai Technológia Tanszék
