Szimuláció és optimalizáció – Célzott numerikus matematikai alapkutatás komplex fizikai folyamatokra és termelési rendszerekre a Széchenyi István Egyetemen nemzetközi kutatói team kialakításával

TÁMOP-4.2.2-08/1-2008-0021

Diszkrét optimalizálási kutatások és alkalmazásuk ütemezési feladatok megoldására

Ipari gyártósorok egyik legelterjedtebb matematikai modellje az ún. Permutation Flow Shop Problem (PFSP), amely az adott időszak alatt megmunkálandó termékek összes lehetséges megmunkálási sorrendje közül keresi azt, amelyet kiválasztva a gyártósoron a lehető legrövidebb idő alatt elkészül a teljes termelés. Habár a PFSP modell számos egyszerűsítést tartalmaz a valósághoz képest, közelítő megoldásai mégis kitűnő terveket adnak a gyártástervezőknek. A feladat nehézségét az adja, hogy egy tipikus ipari feladatban mind a munkák, mind a gyártósoron lévő gépek száma nagy (tipikusan néhány száz feladatról és félszáznál több gépről van szó), ezért még közelítő megoldás előállítása is rendkívül számításigényes.

A projekt során több pontos (pl. kevert egészértékű lineáris) és több heurisztikus (pl. genetikus, bakteriális, hangya-kolóniás, részecske-rajos, iterált mohó) módszert vizsgáltunk, ezek alapján saját algoritmusokat fejlesztettünk és ezeken nyugvó kutatói kódokat hoztunk létre. Legfontosabb eredményeink egyike, hogy bevezettünk és előállítottunk egy, az ipari feladatok sajátságait figyelembe vevő tesztfeladat-családot, amely sokkal jobban méri az egyes módszerek közötti különbséget, mint a klasszikus tesztfeladat-család, a Taillard-féle tesztkészlet. Továbbá az általunk használt módszertan segítségével egy valódi, iparból származó tesztfeladatra az elméletileg is optimális (tehát nemcsak közelítő) megoldást képesek vagyunk meghatározni – mindezt ráadásul nagyon rövid, pár perces gépidő alatt; az eredmény 8%-kal rövidebb megmunkálási idejű tervet eredményez, mint amit egy tapasztalt mérnök kézzel elő tud állítani. Egy általánosabb, az IG (Itarated Greedy, Iterált Mohó) algoritmuson alapuló kódunk több parallel architektúrán fut: SMP és cluster típusú sokprocesszoros gépeken, valamint GPU-n is, ezáltal minden hardveres erőforrás hatékonyan kihasználható. Az alábbi képeken egy referenciának választott evolúciós algoritmus, a hangyakolóniás PACO (piros) és az IG különböző processzorszám melletti futtatásának eredményeit vetjük össze, először egy akadémiai tesztfeladaton (balra), majd egy ipari méretű és ahhoz hasonló szerkezetű tesztfeladaton (jobbra). A sötét-, illetve világoskék oszlopok 30, illetve 60 másodpercig tartó futásoknak felelnek meg az akadémiai és 120, illetve 300 másodpercesnek a nagyobb, iparihoz hasonló feladaton; a referencia futási ideje lényegesen nagyobb, 300, illetve 600 másodperc volt. Látható, hogy a processzorszám növelése lényegesen jobb eredményt, azaz kisebb minimum-közelítést eredményez, mint a referenciának választott.

A megoldási módszertanunk későbbi ipari alkalmazhatóságát növeli, hogy előállítottunk egy az iparban elterjedt szimulációs és optimalizációs szoftverhez, a Plant Simulationhöz egy csatlakozó felületet, amelynek alkalmazásával a szoftver a benne rendkívül időigényes optimalizációs lépést a projekt által fejlesztett programok meghívásával oldja meg – lényegesen rövidebb idő alatt sokkal pontosabb eredményt szolgáltatva mint a Plant Simulation saját optimalizálója.