Illeszkedésen alapuló ütemezési módszer vizsgálata flow shop feladatokon
Egy ütemezési probléma során a feladat egy gyártási ütemterv elkészítése, azaz meghatározásra kerül a munkafolyamatok (job-ok) összes műveletének kezdési és befejezési ideje adott végrehajtó egységekre – gépekre lebontva. Egy ütemezés jónak tekinthető, ha egy cél mentén sikerül optimális eredményt elérni, például a végrehajtás teljes átfutási idejét sikerül minimalizálni.
Az ütemezési problémák megoldási módszerei alapvetően két csoportra sorolhatóak. A matematikai optimalizációs módszerek képesek az optimális célértéket (például minimális átfutási idő) megtalálni, de futási idejük hosszú, akár több hét is lehet, a konkrét feladattól függően. Ezzel szemben a valamilyen heurisztikán alapuló közelítő módszerek futási ideje rövid, ugyanakkor a megtalált célérték nem feltétlenül az elérhető optimum érték.
Munkám során a folyamatrendszerű gyártás (flow shop) típusú ütemezési problémákat vizsgáltam. Ezen feladatok az irodalomban az egyik legintenzívebben kutatott ütemezési problémák, mivel a manapság használatos ipari gyártási rendszereket (például a műhelyrendszerű összeszerelő egységeket) jól modellezik. A flow shop probléma a következőképpen definiálható: ’n’ darab munkafolyamatot kell végre hajtani, amely mindegyike ’m’ műveletből áll és a műveletek végrehajtásához összesen ’m’ darab gép áll rendelkezésre. A gépek csak egy bizonyos művelet elvégzésére képesek. Egy gépen egyszerre csak egy művelet végezhető. A munkafolyamatokon belüli műveletek sorrendje nem változtatható az ütemezés során.
TDK dolgozatomban bemutatom az általam készített heurisztikán alapuló algoritmust. Az algoritmust úgy terveztem meg, hogy az egyes munkafolyamatok karakterisztikáját alapul véve, határozza meg a munkafolyamatok végrehajtási sorrendjét. A megoldási módszerem újszerűsége abban rejlik, hogy míg egy ütemezés természeténél fogva az egyes műveletek egy adott időponthoz való hozzárendelésével kerül kialakításra, addig az én megközelítésemben az egyes munkafolyamatok egymáshoz való illeszkedését vizsgálom, és eszerint alakítom ki a munkafolyamatok végrehajtási sorrendjét az ütemezésben. A hozzárendelés során a magyar módszerre épülő megközelítést alkalmazom.
A kutatás során definiáltam egy, az ütemezési feladatokhoz egyértelműen hozzárendelhető mutatószámot, mely az adott ütemezési probléma illesztési karakterisztikáját fejezi ki. Felhasználva ezt a mutatót további elemzéseket folytattam a bemutatott algoritmus hatékonyságának növelésére és működésének finomhangolására.
Az átfutási idő minimalizálása mellett, a gépkihasználtságot is vizsgáltam és fenti ütemező algoritmusom részeként új módszert dolgoztam ki annak javítására. Megmutattam, hogy az általam készített ütemező algoritmus jobb gépkihasználási eredményeket ér el ugyanolyan vagy jobb átfutási idejű ütemezések esetén, mint más publikált algoritmusok. Az algoritmus hatékonyságát a széles körben elterjedt, Taillard által ismertetett ütemezési problémákon teszteltem és vetettem össze más kutatások, algoritmusok eredményeivel.