Miskolci Egyetem Gépészmérnöki és Informatikai Kar Hatvany József Informatikai Tudományok Doktori Iskola ÜTEMEZÉSI MODELL ÉS HEURISZTIKUS MÓDSZEREK AZ IGÉNYSZERINTI TÖMEGGYÁRTÁS FINOMPROGRAMOZÁSÁNAK TÁMOGATÁSÁRA PhD értekezés Készítette: KULCSÁR GYULA
Témavezető: Dr. ERDÉLYI FERENC Doktori iskola vezető: Prof. Dr. TÓTH TIBOR ME Alkalmazott Informatikai Tanszék
Termelési finomprogramozás (SFS) ERP CAPE MES SFS
PAC, MA, MSC
SFS: Shop Floor Scheduling Rövid távú, műhelyszintű ütemezés Bemenet: Belső rendelések Termék adatok Technológiai adatok Erőforrás adatok Anyag és komponens adatok Ütemezési célok Kimenet: Termelési finomprogram Munkák és erőforrások összerendelése Tervezett tevékenységek Tervezett időadatok
VITAL projekt VITAL „Valós idejű, kooperatív vállalatok” projekt
Prof. Dr. Monostori László (NKTH 2/010/2004) SZTAKI, GE és beszállítói, BME, ME Erőforrás-menedzsment és ütemezés a vállalatok szintjén Termeléstervező, gyártásütemező, erőforrás kezelő alkalmazások fejlesztése MES szinten Valósidejű termelésirányítás változások és zavarok kezelésére Gyártásirányító, termeléskövető, zavarkezelő valósidejű alkalmazások fejlesztése MES szinten Elosztott, kooperatív termelési és logisztikai rendszerek Kooperatív beszállítói, készletgazdálkodási, logisztikai alkalmazások fejlesztése SCM
Kitűzött kutatási célok
Kiterjesztett, az igény szerinti tömeggyártás modelljét is magába foglaló modell kifejlesztése a gyártási feladatok és sorozatnagyságok meghatározásának, a gépek allokálásának és a munkák időbeli ütemezésének céljából. Olyan megoldási módszerek kifejlesztése, amelyek a termelés változó feltételeihez és igényeihez igazodva egy vagy több értelemben optimumközeli, végrehajtható termelési finomprogramot állítanak elő a gyakorlatban elfogadhatónak számító tervezési időkorlátok betartásával. A MES dinamikus gyártásirányítási funkcióinak, különösen a termelési bizonytalanságok kezelésének támogatása, figyelembe véve a termelési folyamatok minősítésének, a korrekciós újraütemezésnek, a termelési célok, prioritások és bizonytalanságok menedzselésének igényeit is.
Alkalmazott módszerek
Felhasznált elvek, modellek és módszerek: termelésinformatika diszkrét matematika operációkutatás témakörökből ütemezéselmélet mesterséges intelligencia információ technológia Fejlesztési metodika: ismeretek összegyűjtése és szintetizálása probléma, részprobléma megfogalmazása matematikai és informatikai modellezés megoldási koncepció kidolgozása tervezés és implementálás tesztelés és értékelés a követelményrendszer és a célok pontosítása
Ismert Flow Shop modellek Flow Shop – egyutas modell M1
M2
…
Mi
…
Mm
Rugalmas Flow Shop – párhuzamos kapacitások modell
S1
S2
Si
Sk
M1.1
M2.1
Mi.1
Mk.1
M1.2
M2.2
M1.j
M2.j
Mi.j
Mk.j
M1.m1
M2.m2
Mi.mi
Mk.mk
…
Mi.2
…
Mk.2
Kiterjesztett rugalmas Flow Shop modell TS1
MG1
…
TS2
MG2
…
TS3
TS4
MG3
…
MG4
…
Termék 1 Termék p
… MG5
Technológiai lépés TS Gépcsoport MG
… MG6
… MG7
…
Gép (gépsor)
MG8
… MG9
… MG10
Az ütemezési feladat formális leírása || formalizmus:
erőforráskörnyezet korlátozások, végrehajtási jellemzők célfüggvények
Kiterjesztett rugalmas Flow Shop (EFFS) ütemezési feladatosztály:
Fx, M g , Qi ,m , Seti , j ,m , Calm Ri , Di , Exei , Ai [ f1 , f 2 ,..., f K ]
Számítógépi reprezentáció
Objektum orientált modell Legfontosabb osztályok:
Termék, Rendelés, Munka, Feladat, Gép, Gépcsoport, Végrehajtási lépés, Útvonal, Termelési finomprogram, Gyártórendszer …
Indexelt kapcsolatrendszer:
Név1_Név2
0
Név1[1]
N1
…
…
…
…
0
1
NK
Név1[K]
NK
1
N1
Név2[i]
Név2[u]
…
…
Név2[j]
Név2[v]
Név1_Név2[Index1][Index2] Index1 = (1,…, K), Index2 = (0,…, Név1_Név2[Index1][0])
1. tézis Új kiterjesztett rugalmas Flow Shop ütemezési modell és annak számítógépi reprezentációja. Kidolgoztam egy új, kiterjesztett ütemezési feladatosztályt (Extended Flexible Flow Shop, EFFS) és annak számítógépi reprezentációját a rövid távú, műhelyszintű termelésprogramozási feladatok modellezésére, figyelembe véve az igény szerinti tömeggyártás legfontosabb általános jellemzőit és követelményeit.
Megoldási koncepció Felhasználó Rendelés Termék Technológia Erőforrás
Termelési finomprogram
Modellépítés
Célfüggvényértékek
Ütemezés Munkák
Ütemterv
Szimuláció Objektumok Éles termelési finomprogram
Finomprogram
Minősítés
Teljesítménymutatók
Szimuláció
Szimuláció
Szabályalapú számítási eljárás jól definiált ütemterv adott gyártási környezetben történő végrehajtásának gyors szimulációjára. Időadatok számítása: 0 MG1 1 MG2 2 MG3 3 MG4 Gyártási feladatok: 0 MG5 Előkészítési idő 1 MG6 Műveleti idő 2 MG7 Kezdési időpont 0 MG8 Befejezési időpont 1 MG9 Munka: 0 MG10 Indítási időpont Befejezési időpont Rendelés: Indítási időpont Befejezési időpont
Ütemezés
Ütemezés
Integrált, általános célú ütemezési módszer a hozzárendelési és a sorrendi problémák megoldására, amely minden egyes munkához: hozzárendel egy megfelelő útvonalat, hozzárendel egy megfelelő gépet a kiválasztott útvonal minden egyes végrehajtási lépésének megfelelő gépcsoportból, meghatározza minden hozzárendelt gépen a végrehajtási sorban elfoglalt pozícióját. Kétfázisú heurisztikus megoldási módszer: Heurisztikus felépítő algoritmus-változatok Heurisztikus Tabu kereső algoritmus
Heurisztikus felépítő algoritmusok
Viszonylag jó kezdeti megoldás gyors előállítása. BWBA algoritmus: Cél: a termelési jellemzők egyensúlyban tartása Lépések: Rendelések csoportosítása és rendezése az EXE típusok alapján növekvő sorrendbe. Minden megrendelés egy egységként (bontás nélkül) kerül beütemezésre: a legnagyobb integráltsági fokkal jellemezhető útvonal hozzárendelésével, az érintett gépcsoportokból egyenletes valószínűséggel választott gépek alkalmazásával, a gépeken a munkák sorrendjét a beütemezés sorrendje határozza meg. További algoritmusok: HEFCA, HIA, EHIA
Heurisztikus Tabu kereső algoritmus s* = s0 = kezdeti megoldás készítése ( ); tabulista = üres; while ( leállási feltétel nem teljesül() ) { while ( kiterjesztés feltétele teljesül() ) { s = szomszédos megoldás készítése( s0 ); if ( nem eleme a tabulistának( s ) ) { felvétel a tabulista elejére( s ); if ( tabulista elemszáma > megengedett elemszám ) tabulista utolsó elemének törlése( ); if ( kiterjesztés első megoldása ( s ) ) s_k = s; else if ( jobb megoldás ( s, sk) ) sk = s; } } s0 = sk; if ( jobb megoldás ( sk, s* ) ) s* = sk; } return s*;
A keresési módszer sajátosságai
Tabulista Speciális formában megoldásokat tárol. Szisztematikus különbségvizsgálatra alapozott gyors ellenőrzést valósít meg. Szomszédság kezelése Többféle szomszédsági operátor alkalmazása. A szomszédsági operátorok csak megengedett megoldásokat állítanak elő, nincs szükség konzisztencia-vizsgálatra. A módosító operátorok rugalmasak, nem függnek a célfüggvényektől. Prioritásértékekkel szabályozható a szomszédsági operátorok használata.
2. tézis Többfázisú heurisztikus módszer az EFFS ütemezési feladatok megoldására. Az EFFS modellel kezelhető termelésprogramozási feladatok megoldására kifejlesztettem egy új szemléletű integrált módszert, amely végrehajtás-szimulációra alapozott problématér-transzformációval, heurisztikus algoritmusok valamint keresési technikák kombinált alkalmazásával egyidejűleg támogatja a rendelések bontására és/vagy egyesítésére, a gyártási sorozatnagyságok dinamikus meghatározására, a technológiai alternatívák kezelésére, a gépi erőforrások allokálására, a gyártási feladatok definiálására és azok végrehajtásának időbeli ütemezésére vonatkozó döntéseket.
Termelési folyamat minősítése menedzser mutatók
Minősítés
: célfüggvény max (Ci )
Erőforrás mutatók Készletszint mutatók Szállítókészség mutatók
i
max (Ci ) min ( Ri )
Munka (i=1,…,n) Di : határidő Ri : indítási időpont Ci : befejezési időpont vi : súlyozó tényezők Eltérés: Csúszás: Átfutási idő:
Li Ci Di Ti max(0, Li ) FTi Ci Ri
Speciális mutatók
i
i
viGi i
}
max (viGi ) i
Gi
v G i
i
i
n | {i | Ti 0} |
Többcélú optimalizálás Egynél több célfüggvényt kell egyszerre figyelembe venni:
min f1 ( s ),..., f k ( s ),..., f K ( s ) k {1,2,..., K} sS
s S fk
egy megengedett megoldás a megengedett megoldások halmaza egy komponens célfüggvény f : S k
Ismert módszerek: Párhuzamos (Pareto) megközelítés Súlyozott célfüggvények alkalmazása Hierarchikus optimalizálás Célprogramozás …
{0}
Új megközelítés: relatív minősítés a, b
sx , s y S
max : 2
a, ha a b max( a, b) b, egyébként
0, ha max( a, b) 0 2 D ( a , b) b a D: max( a, b) 100, egyébként wk wk 0 k {1,2,..., K}
F : S2
K
F ( sx , s y ) ( wk D( f k ( sx ), f k ( s y ))) k 1
Többcélú kereső eljárások Az az
F ( sx , s y ) előjeles érték kifejezi az s y megoldásnak s x megoldáshoz viszonyított relatív minőségét.
s yjobb megoldás mint s x ha F ( sx , s y ) 0 s yés s x azonosan jó megoldások ha F ( s x , s y ) 0 s yrosszabb megoldás mint s ha F ( sx , s y ) 0 x
Egycélú keresés
Többcélú keresés
Szimulált hűtés (SA) Tabu keresés (TS) Genetikus algoritmus (GA) …
3. tézis Új módszer többcélú kombinatorikus optimalizálási feladat megengedett megoldásainak egymáshoz viszonyított minősítésére. Matematikai modellt és megoldási módszert dolgoztam ki a többcélú kombinatorikus optimalizálási feladatokban előírt – dinamikusan változó fontosságú, különböző dimenziójú és értékkészletű – célfüggvények együttes figyelembevételére és a megengedett megoldások egymáshoz viszonyított (relatív) minőségének számszerűsítésére.
Újraütemezés: a viselkedés alapú gyártásirányítás eszköze
Kihívások: Végrehajtás alatt álló, megszakított ütemterv Valós folyamatok bizonytalanságai, állapotai Összetett újraütemezési célok Megváltozott rendelések és erőforráskörnyezet Speciális korlátozások Ütemezési modell és módszerek kiterjesztése: Célfüggvények a változtatások számszerűsítésére Zárolási technikák Továbbfejlesztett kereső operátorok
Integrált termelésprogramozási koncepció INTEGRÁLT ÜTEMEZŐ ÉS ÚJRAÜTEMEZŐ
ERP
Cégadatbázis
Rendelés Termék Technológia Erőforrás
Modellépítés
Ütemezés és újraütemezés
GUI
Szimuláció GUI Termelési finomprogram
Éles termelési finomprogram
Minősítés GUI
MES
MES TERMELÉSMENEDZSMENT
TERMELÉSI FOLYAMAT
MES
MES
Teljesített rendelések
Új termelési finomprogram
Elemzés
Termelésfelügyelet
Értékelés
Viselkedés
ADATGYŰJTÉS
BIZONYTALANSÁGKEZELÉS
GUI
Termelésprogramozó szoftver 1
Termelésprogramozó szoftver 2
Termelésprogramozó szoftver 3
4. tézis Integrált termelésprogramozási modell a rugalmas tömeggyártásban fellépő változások és zavarok kezelésének támogatására. A MES szintű gyártásirányítás és bizonytalanságkezelés ütemezési és újraütemezési feladatainak támogatására kifejlesztettem egy új, integrált modellt és kidolgoztam annak egy számítógépi (szoftver) reprezentációját. A megoldás alkalmas az igény szerinti tömeggyártás műhelyszintű termelésprogramozási feladatainak integrált, kiterjesztett funkciójú kezelésére.
Futási eredmények Gép: 119 Rendelés: 393 Munka: 2173 Beállítástípusok: 4 Lépés: 2000 Kit.: 100 minKit.: 10 Javulás: 40 TABU:150 Nx_op_pri: N1: 1 N2: 1 N3: 1 N4: 1 N5: 1 ObjF:
LOrder LJob
sumT
maxT
Set
maxC
ObjPri:
7
8
10
10
7
5
rand:
277,5
992,1
1,30E+06 4241,1
1779,6 4685,2
heur:
109,2
430,7
118618
1275,3
964
1725
search:
2,1
3,2
48
21,3
248,7
1034,7
Avp(10it):
Átlagos programfutási idő: 2 min 55s
Futási eredmények s_1: s_2: s_3: s_4: s_5: s_6: s_7: s_8: s_9: s_10:
LOrder 2 2 2 2 2 2 2 2 3 2
LJob 3 3 3 3 3 3 3 3 5 3
sumT 33 46 46 46 33 46 46 46 92 46
maxT 14 22 22 22 14 22 22 22 31 22
Set 243 234 250 265 228 228 237 244 304 254
maxC 998 1068 1035 1032 1031 995 1055 1058 1014 1061
Köszönetnyilvánítás Dr. Erdélyi Ferenc Prof. Dr. Tóth Tibor Dr. Dudás László ME AIT MTA SZTAKI VITAL projekt résztvevők Dr. Csáki Tibor Dr. Kádár Botond
Köszönöm megtisztelő figyelmüket!
