MISKOLCI EGYETEM DOKTORI (PHD) TÉZISFÜZETEI
HATVANY JÓZSEF INFORMATIKAI TUDOMÁNYOK DOKTORI ISKOLA
ÜTEMEZÉSI MODELL ÉS HEURISZTIKUS MÓDSZEREK AZ IGÉNY SZERINTI TÖMEGGYÁRTÁS FINOMPROGRAMOZÁSÁNAK TÁMOGATÁSÁRA
KÉSZÍTETTE:
KULCSÁR GYULA OKLEVELES MÉRNÖK-INFORMATIKUS
AKI DOKTORI (PHD) FOKOZAT ELNYERÉSÉRE PÁLYÁZIK
TÉMAVEZETİ:
DR. ERDÉLYI FERENC A MŐSZAKI TUDOMÁNY KANDIDÁTUSA
MISKOLC, 2007
2
TÉZISFÜZET
TARTALOMJEGYZÉK Tartalomjegyzék ....................................................................................................... 2 1.
Bevezetés.......................................................................................................... 3
2.
Tudományos elızmények................................................................................. 4
3.
A kutatás célkitőzése ........................................................................................ 7
4.
Az alkalmazott módszerek és az elvégzett kutatómunka összefoglalása......... 8
5.
Új tudományos eredmények........................................................................... 12
6.
Az eredmények hasznosíthatósága................................................................. 19
7.
További kutatási feladatok ............................................................................. 20
8.
Az értekezés témakörében készített saját publikációk ................................... 21
9.
Hivatkozott irodalom...................................................................................... 22
New scientific results.............................................................................................. 28
TÉZISFÜZET
3
1. BEVEZETÉS Napjainkban a tömeggyártással foglalkozó vállalatok tekintélyes része is kénytelen a vevık igényeinek közvetlen kiszolgálására (pl. tömegcikkek, világítótestek, háztartási gépek, stb. gyártása). A versenyképesség növelése érdekében folyamatosan és rugalmasan alkalmazkodniuk kell a piaci körülmények gyors változásaihoz. Ez megköveteli a gyártási hatékonyság és a szállítókészség egyidejő javítását. Az elıbbit például az erıforrások minél jobb kihasználásával, alacsony gyártási költségekkel, az utóbbit jól ütemezett termeléssel, a rendelésre és a raktárra való gyártás kombinálásával lehet elérni. A vállalatok sikeressége számos esetben a megrendelık határidıigényeinek magas szintő kielégítésén múlik. Mindez egyre fontosabbá teszi a hosszú, közép és rövid távú termeléstervezési és -ütemezési feladatok hibátlan megoldását. A termelés finomprogramozása (folyamatközeli ütemezés) a MES (Manufacturing Execution System) néven ismert gyártásirányítás, rövid távú – esetenként valós idejő – tervezési feladata. Ismertek a termelési rendszer korlátozásai, a véges technológiai kapacitások, a rendelkezésre állások, a mőveletek sorrendi elıírásai stb. Az ütemezésnél a gyártásra kiadott, belsı rendeléseken alapuló munkák és mőveletek elvégzéséhez gyártási erıforrásokat (gépek, eszközök stb.) valamint indítási és befejezési idıpontokat kell tervezni úgy, hogy a korlátozások teljesüljenek, és a termelés teljesítményét mérı mutatók optimálisak legyenek, azaz a menedzsment magasabb szintjén megfogalmazott célok megvalósuljanak. A diszkrét termelési folyamatokban a termékek elkészítése gyártási sorozatokban, kötegekben történik. A sorozatok nagysága nagyon változó lehet, egyetlen darabtól (pl. nagy értékő alkatrészek vagy egyedi gépek, berendezések gyártása) több ezer, sıt több millió darab termékig is terjedhet (pl. tömegcikkek, komponensek, alkatrészek tömeggyártása esetén). A diszkrét gyártó-szerelı rendszerekben a mőveletek végrehajtása elkülönült gépeken (esetleg kézi munkahelyeken) történik. A gyártási folyamat rendszerint több térben és idıben egymás után (sorba) kapcsolt részfolyamatból, mőveletbıl, technológiai lépésekbıl áll. A mőveleteknek és ezek sorrendjének alternatívái is lehetnek. A sorba kapcsolt mőveletek száma néhánytól (25) akár 100-ig is terjedhet. Tömeggyártásnál nagyszámú termék ugyanazt a technológiai utat járja be. Az ilyen gyártási folyamatot soros felépítéső, folyamszerő „Flow Shop” gyártásnak nevezik. A soros gyártási struktúrához és homogén technológiai tervekhez kapcsolódó modellben (Flow Shop, FS) a rendelésekben megadott számú munkadarab adott számú különbözı gépen, a technológiai sorrendnek megfelelıen, egymás után kerül megmunkálásra. Ha megengedett az, hogy az egyes gépeken a munkák sorrendje eltérı legyen, akkor elızéses, ellenkezı esetben elızésmentes modellrıl van szó. A termelés során tehát munkadarab-sorozatok (kötegek) gyártásáról kell gondoskodni. A
4
TÉZISFÜZET
rendelési sorozatok független bemeneti adatok a gyártás számára. A gyártási és logisztikai sorozatnagyságok azonban termelésirányítási döntések tárgyai lehetnek. Az értekezés az igény szerinti tömeggyártás finomprogramozásának támogatására szolgáló számítógépes modellek és ütemezési módszerek továbbfejlesztése terén szándékozik új eredményeket bemutatni.
2. TUDOMÁNYOS ELİZMÉNYEK A „Flow Shop” típusú ütemezési feladatok leírása és a megoldás lehetıségeinek vizsgálata már több mint ötven éves, és napjainkban is számos termelésirányítási és ütemezési tankönyvben vagy monográfiában megtalálható (pl. [25], [72], [34], [23]). A formális alapmodellben ismert a gépek (erıforrások) halmaza: M = {m j }, j = 1,..., m , m ∈ Z + ; a munkák halmaza: J = {J i } , i = 1,..., n , n ∈ Z + , minden munka sorba
kapcsolt mőveletekbıl áll: O = {oi , j }, minden mővelet τ ij idıt vesz igénybe, τ ij ∈ R . A
mőveletek homogén sorrendje: j = 1 → 2 → ... → m . A raktárra gyártás (make to stock) teljesítményt mérı célfüggvénye legtöbbször a „makespan”: f = min[max( TCi ) − min( TRi )] , ahol TCi az i. munka befejezési idıpontja, és TRi az i. munka indítási idıpontja. Rendelésre gyártás esetén a célfüggvény inkább a késések n
összes idejének minimalizálása: f = min ∑ max( 0,TCi − TDi ) , ahol TDi az i. munka i =1
határideje. A klasszikus (egyutas, elızésmentes) feladatnak a teljes átfutási idı minimalizálására csak m ≤ 2 estben, valamint bizonyos megszorításokkal m = 3 esetben van polinomiális futási idejő megoldási algoritmusa. Ez a nevezetes Johnson algoritmus [45]. Ennek fıként elméleti jelentısége van, mert a gyakorlati feladatokban általában m > 2 . Ezekre az esetekre a feladat NP-nehéz, sıt NP-teljes [37]. Gyors processzorokkal a leszámlálásos triviális tervezési algoritmus elızésmentes esetben kb. n < 10 -re ad elfogadható tervezési idıt. Az évek során a különbözı mérető és komplexitású FS feladatok megoldására sokféle egzakt módszer, approximáció, heurisztika, metaheurisztika és más alapú megoldás született. Ezekrıl részletes áttekintést, összefoglalót adnak például a [25], [72], [18], [36], [27] munkák. A weben is számos győjtemény található az ütemezési feladatok megoldási algoritmusairól (pl. [29], [60], [26]). A kutatások egy másik fontos iránya a klasszikus feladat bıvítése, kiterjesztése olyan irányokban, ami megfelel a diszkrét gyártásirányítás számítógépes támogatása (MES alkalmazások) növekvı igényeinek. Az alapmodell párhuzamos gépekkel történı kibıvítéseként ismert a rugalmas, egyutas (Flexible Flow Shop FFS) modell. Az ilyen modellekben összetett munkahelyek vannak definiálva. Minden egyes munkahelyen adott számú, azonos feladat végrehajtására alkalmas, egymással párhuzamosan mőködı egyenértékő, részben azonos vagy különbözı intenzitás- és
TÉZISFÜZET
5
más paraméterértékekkel rendelkezı gépek találhatók. A párhuzamosan mőködı gépek száma munkahelyenként eltérı lehet. Az egymást követı munkahelyek között átmeneti tárolók kaphatnak helyet. A munkadarabokat minden munkahelyen – annak egy kiválasztott gépén – kell megmunkálni. Ezáltal a modellekben megjelenik a gépválasztás (allokáció) feladata is, ugyanakkor továbbra is alapvetı szerepet játszik a munkák gépenkénti sorrendjének és indítási idıpontjának meghatározása. Az alap FS feladat ilyen irányú kibıvítését Arthanari és Ramamurthy (1971) az elsık között tették meg [22]. Gupta (1988) majd Hoogeveen és társai (1996) különbözı FFS feladatokat vizsgálva állapították meg, hogy azok NP-nehéz feladatosztályba tartoznak [39], [41]. A kutatók széles körben, különbözı jelzıket használva tárgyalják ezeket a modelleket. Leggyakoribbak a rugalmas (Flexible Flow Shop: FFS), a hibrid (Hybrid Flow Shop: HFS), a párhuzamos gépes (Flow Shop with Paralell Machines: FSPM), az összetett munkahelyes (Multi-Stage Flow Shop: MSFS) és a többgépes (Multiprocessor Flow Shop: MFS vagy Flow Shop with Multipe Processors: FSMP) elnevezéső modellek. Ezek közé sorolhatók még a rugalmas gyártósor (Flexible Flow Line: FFL) néven ismert modellek is. Az ismert modellváltozatokról és megoldási módszerekrıl különbözı szempontok szerint rendszerezett, részletes összefoglalót készített Linn és Zhang (1999) [53], Wang (2005) [74], továbbá Kis és Pesch (2005) [49], valamint Quadt és Kuhn (2007) [61]. A témakörhöz tartozó ismert megoldások többsége optimalizálási kritériumként egyetlen célfüggvényt használ. Ez az esetek többségében (a raktárra történı gyártás alapesetét feltételezve) a megrendelt munkacsoport legkésıbbi befejezési idejének minimalizálását jelenti. Kevesebb megoldási módszer született (a határidıre történı gyártásnak megfelelıen) a késésekkel kapcsolatos célfüggvények valamelyikének minimalizálására [54], [75]. A speciális feladatváltozatokra kifejlesztett módszerek alkalmazhatósága más célfüggvényekre erısen korlátozott, részletesebb modellekre pedig még komoly módosításokkal sem igazán alkalmazhatók. Az egycélú ütemezéshez viszonyítva a több célfüggvény értékének kompromisszumos optimumát biztosító (multi-objective, multi-criteria) megoldások elıállítása terén kevesebb kutatási eredmény született. Jellemzıen olyan módszerek léteznek, amelyek csak egy elsıdleges és egy másodlagos, vagy egy elsıdleges és több alacsonyabb prioritású cél elérésére koncentrálnak [46]. Ugyanakkor, az ilyen megoldási módszerek – az ütemezési hatékonyság és a számítási sebesség növelése érdekében alkalmazott heurisztikák miatt – megváltozott célok kezelésére nem vagy csak nehezen alkalmazhatók. Léteznek különbözı általános elvek és módszerek többcélú kombinatorikus optimálási feladatok megoldására (pl. [63], [55], [38]), azonban dinamikus rendszerekben, gyakran változó fontosságú célok esetén a bonyolult paraméterezés miatt ezek alkalmazása nehézkes. A kutatások jelentıs része az aktuálisan vizsgált modelltulajdonság kiemelésére helyezi a hangsúlyt, az egyszerőbb kezelhetıség érdekében háttérbe kerülnek az egyéb jellemzık. Az FFS modellekben rendszerint folyamatosan elérhetı gépek szerepelnek
6
TÉZISFÜZET
(pl. [46], [76], [52], [18]). Kivételnek számító esetekben jelennek csak meg a gépek rendelkezésre állására vonatkozó idıbeli korlátozások, és ilyenkor is csak egyéb tényezık egyszerősítésével, elhagyásával kerülnek bemutatásra. Allaoui és Artiba (2006) például a gépek korlátozott rendelkezésre állását úgy vizsgálták HFS környezetben, hogy modelljükben két munkahelyet definiáltak. Az elsı munkahelyen csak egyetlen gép, míg a másodikon több párhuzamos gép szerepelt. Szétválasztás és korlátozás alapú megoldási módszert használtak a legkésıbbi befejezési idıpont minimalizálására. A munkák sorrendjétıl függı vagy attól független gépbeállítási/átállítási idıket figyelembe vevı FFS modelleket és módszereket Allahverdi és társai (1999) [19], (2007) [20] rendszerezték. Azok a megoldási módszerek, amelyek a sorozatnagyságra (a rendelések bontására és/vagy egyesítésére) vonatkozó kérdésekkel is foglalkoznak, rendszerint csak a teljes rendeléscsoport átfutási idejét, vagy a befejezési idıpont csökkentését célozzák meg. Jó példák ezekre a Lee és társai (1997) [52], valamint Zdansky és Pozivil (2002) [76] által bemutatott módszerek. A sorozatnagyságok kezelését is tartalmazó ütemezési feladatokról és azok megoldási módszereirıl részletes elemzést készített Zhu és Wilhelm (2006) [77]. Az egyik fontos kutatási terület, mely az utóbbi idıben hangsúlyt kapott, az elıidejő (prediktív) ütemezés és a valós idejő folyamatmenedzsment (Process Management) összehangolása. Ennek az integrációnak több aspektusa is van, például a „bizonytalanságkezelés”, a „kockázatmenedzsment”, a „prioritásmenedzsment”, a „viselkedés alapú termelésirányítás” stb. [67], [58]. A problémakör a gyártásirányítás fontos beavatkozási tevékenységeként kezeli a termelési folyamatok részbeni vagy teljes újraütemezését. A témával kapcsolatos eredményekrıl, a különbözı újraütemezési stratégiákról a [70], [59], és [71] publikációk is beszámolnak. A kutatók egyetértenek abban, hogy az újraütemezést az eredeti ütemezési feladat jelentıs módosításaként kell tekinteni, ahol új korlátozások és új célok jelennek meg. A probléma megoldásterét általában ezek a feltételek szőkítik, de járulékos nehézséget okoznak a speciális gyártásirányítási követelmények (pl. anyagellátási, minıségbiztosítási, logisztikai stabilitási igények) kielégítésének lehetıségei. Fontos új követelményként fogalmazható meg, hogy az alkalmazott modellnek lehetıvé kell tenni a gyártásirányító személy (üzemvezetı, mővezetı, üzemmérnök) olyan interaktív ütemezési javaslatainak és döntéseinek beillesztését, amely az eredeti és a járulékos korlátozások és célok kielégítését egyaránt biztosítja. Az újraütemezés speciális igényeivel kapcsolatos összefoglalások találhatók pl. a [62], [24] irodalomban. Magyarországon a diszkrét gyártási folyamatok modellezése és a gyártási folyamatok ütemezése több évtizede kutatás és fejlesztés tárgya. A mőszaki egyetemek (BME, ME) gépgyártástechnológiai és alkalmazott informatikai tanszékei mellett eredményes kutatás-fejlesztés folyik az MTA SZTAKI-ban, és korábban a GTI-ben is. Az ütemezéselmélet témakörében eredményeket publikáltak további egyetemek kutatócsoportjainak, alkalmazott matematika, operációkutatás, informatika
TÉZISFÜZET
7
tanszékeinek kutatói is. Példaként említhetı meg néhány jellemzı eredmény az elmúlt évekbıl. MTA SZTAKI: [31], [30], [48], [47], [51], [57], [69]; BME: [66], [64], [65]; ME: [35], [42], [67]; ELTE: [73], [68]; SZTE: [17], [43], [44], [43]; PTE: [32], [33]; VE: [40], [56]. Összefoglalva megállapítható, hogy a tématerület jelentıs elméleti háttere és a publikációk nagy száma ellenére a jelenleg ismert többgépes termelésütemezési modellek, és azok megoldási módszerei még nem veszik egyszerre figyelembe az igény szerinti tömeggyártás jellegzetességeit: több mővelet együttes végrehajtására képes gépeket, technológiaiútvonal-alternatívákat, gépek változó rendelkezésre állási idıintervallumait, gépenként eltérı termelési intenzitásokat és selejtarányokat, sorrendfüggı átállási idıket valamint az esetenként gyorsan változó termelési célokat, prioritásokat. Szükség van tehát ezeknek a modelleknek a kiterjesztésére, továbbfejlesztésére és hatékony megoldási módszerek kifejlesztésére, amelyek aztán új, hatékony funkcionális komponensei lehetnek a számítógépes MES alkalmazásoknak.
3. A KUTATÁS CÉLKITŐZÉSE Napjainkban – a globalizációs kihívásokra válaszolva – számos nagyvállalat egyedi megrendelésekhez, a kereskedelmi és logisztikai központok egyedi igényeihez igazodó tömegtermelést kénytelen folytatni (Customized Mass Production). Az ilyen termelési folyamatok közös jellemzıje a terméktulajdonságok, specifikációk, technológiai, valamint erıforrás-alternatívák sokfélesége, a megrendelések változatossága, az igények nehéz elırejelezhetısége, és a vevık kívánságaihoz való (pl. egyedi kiszerelés, szállítási idıpontok) magasfokú alkalmazkodás igénye a nagysorozat- és tömeggyártás technológiai körülményei között. A kutatás alapvetı célja az igény szerinti tömeggyártás rövid-távú, mőhelyszintő termelésprogramozási feladatának modellezése a gyártási feladatok és sorozatnagyságok maghatározásának, a gépek allokálásának és a munkák idıbeli ütemezésének szempontjából. További célja olyan megoldási módszerek és algoritmusok 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 (futási) idıkorlátok betartásával. A rövid idıhorizontú tervezési modell és ütemezı egy gyártásirányító (MES) alkalmazás szerves része kell legyen, amelynek támogatnia kell a MES dinamikus gyártásirányító funkcióit is, beleértve a termelési folyamatok minısítésének, a korrekciós újraütemezéseknek, a termelési célok, prioritások és paraméterek megváltoztatásának, valamint a bizonytalanságok menedzselésének igényeit is. Egy sikeres ütemezési koncepció kidolgozásához szükséges a témához kapcsolódó ismert fontosabb ütemezési modellek és azok megoldási módszereinek elemzése,
8
TÉZISFÜZET
alkalmazhatóságuk vizsgálata, a lehetıségek és a követelmények összevetése. Ezek ismeretében kell hatékony ütemezési, döntéstámogatási modelleket és algoritmusokat kifejleszteni, implementálni, tesztelni és értékelni. Az értekezésben összefoglalt kutatás az MTA SZTAKI vezetésével folyó „Valós idejő, kooperatív vállalatok” (VITAL) c. projekthez kapcsolódik. A funkcionális követelmények megfogalmazásánál a VITAL kutatási beszámolókban megfogalmazott specifikációkat is figyelembe vettem.
4. AZ ALKALMAZOTT MÓDSZEREK ÉS AZ ELVÉGZETT KUTATÓMUNKA ÖSSZEFOGLALÁSA A kitőzött feladat komplexitása és interdiszciplináris jellege megkövetelte a különbözı, egymással szoros kapcsolatban álló tématerületek eredményeinek figyelembe vételét. A megoldás során alapvetıen a termelésinformatika, a diszkrét matematika, az operációkutatás, az ütemezéselmélet, a mesterséges intelligencia és az információtechnológia korszerő elveire, modelljeire és módszereire támaszkodtam. A kutatómunkám során végzett tevékenységsorozat egy ismétlıdı körfolyamattal jellemezhetı. Ennek során a felmerült részfeladatokhoz kapcsolódó ismereteket, eredményeket összegyőjtöttem és szintetizáltam. A kapcsolódó konvenciók (jelölés, fogalmak) felhasználásával megfogalmaztam a problémát. Ezt követıen modelleztem a feladatot úgy, hogy mind számítási mind informatikai szempontból számítógépi programmal hatékonyan kezelhetı legyen. Kidolgoztam a feladatmegoldás koncepcióját, ezt követıen definiáltam a szükséges modelleket, algoritmusokat és heurisztikákat. Kidolgoztam a feladatmegoldás számítógépes implementációját. Tesztelés és értékelés után a folyamat részleges ismétlésére került sor részletesebb és szigorúbb követelményrendszer felállításával és pontosított célok kitőzésével. Kiindulásként az igény szerinti tömeggyártást folytató vállalatok diszkrét gyártószerelı folyamatainak a termelésprogramozás szempontjából fontos, általánosítható jellemzıit győjtöttem össze. Ebben nagy segítségemre voltak egyrészt a szakirodalomból nyerhetı, fıként elméleti szempontból fontos anyagok, másrészt azok a konkrét kutatáshoz kapcsolódó technikai specifikációk, jelentések valamint valósághoz közeli termelési mintaadatok, amelyek a gyakorlatból származó igényeket, elvárásokat tükrözték. Ez utóbbi anyagok megismerésére jó lehetıséget biztosított a „VITAL” Valósidejő, kooperatív vállalatok (NKTH 2/010/2004) projekt, amely a termelési folyamatok számítógépes támogatásának fejlesztésére irányul (2004-2007). Ebben a projektben a General Electric (GE) magyarországi leányvállalatai, több hazai beszállító vállalat, továbbá a Budapesti Mőszaki és Gazdaságtudományi Egyetem (BME), valamint a Miskolci Egyetem (ME) kutatócsoportjai a Magyar Tudományos Akadémia Számítástechnikai és Automatizálási Kutató Intézetének (MTA SZTAKI) vezetésével vesznek részt. A Miskolci Egyetem Alkalmazott Informatikai Tanszékén
TÉZISFÜZET
9
(tanszékvezetı: Tóth Tibor) folyó kutatómunka célja hozzájárulni az MTA SZTAKI vezette nagy mérető, komplex kutatás-fejlesztési munka támogatásához. A kutatásokat Monostori László projektvezetı, Kis Tamás, Kádár Botond és Váncza József klasztervezetık (MTA SZTAKI), továbbá Farkas Zoltán informatikai fejlesztésvezetı (GE Hungary) irányította. A projektben végzett munka során megszerzett ismereteket összevetve a nemzetközi irodalomban elérhetı ismeretekkel a kutatási tématerületre nézve a következı fontosabb általánosítható jellemzıket és követelményeket foglaltam össze: • Egy igény szerinti tömeggyártást folytató vállalat több (esetenként számos) különbözı terméket állít elı. A gyártásirányítás szintjén jellemzıen adott egy belsı rendelésállomány, amelyet a külsı rendelések és az elırejelzések figyelembevételével a vállalat termeléstervezési szintjén definiálnak. Minden egyes rendelés meghatározott típusú, adott darabszámú egyforma termék, adott határidıre történı legyártását írja elı. • A tömeggyártás mőhelyszintő irányításban elıredefiniált logisztikai egységek szerepelnek. A logisztikai egység (pl. paletta, konténer) megadott darabszámú, adott típusú termék elıállítására irányuló munkadarabok együttesét jelenti. A logisztikai egység munkadarabjai együtt kerülnek mozgatásra a gyártó-szerelı rendszerben, és azonos mőveleteket kell rajtuk végrehajtani. Egy rendelés ilyen logisztikai egységek halmazának tekinthetı, ahol a logisztikai egységek számát a rendelt mennyiség és a logisztikai egység termékfüggı mérete együttesen határozzák meg. • A belsı rendelésekben szereplı termékek elıállításához – a termék típusától függıen – adott számú mőveletet kell kötött sorrendben végrehajtani. A mőveletek rendszerint további részoperációk sorozatából tevıdhetnek össze, azonban a mőveletek jellemzıen nem szakíthatók meg, ezért ezek tekinthetık az ütemezés során a legkisebb allokációs egységeknek. Egy mővelet adott idıben történı elvégzéséhez megfelelı gép (munkahely), továbbá meghatározott típusú és mennyiségő (esetleg többféle) anyag és/vagy komponens együttes rendelkezésre állása szükséges. Ugyanakkor a termelés rugalmas jellegébıl következik, hogy egy adott típusú termék alternatív anyagok, komponensek, gépek és útvonalak használatával is elıállítható. • A gyártó-szerelı rendszerben rendszerint automatizált gépek, gépsorok, (esetleg kézi munkaszalagok) mőködnek, amelyek a terméktıl függı gyártási sebességekkel, a munkák sorrendjétıl függı átállási idıkkel, rendelkezésre állási idıintervallumokkal és egy adott termékcsoportra érvényes, egymást követı mőveletek sorozatával jellemezhetık. A gyártás során egy adott gép egyszerre csak egy feladaton dolgozhat, és egy adott feladaton egyszerre csak egy gép dolgozhat. A gépek között átmeneti tárolóhelyek vannak kialakítva, melyek mérete – ütemezési szempontból – rendszerint nem korlátozott.
10
TÉZISFÜZET
• A finomprogram elkészítésekor figyelembe kell venni, hogy az ütemezési idıhorizonton a mőhely bizonyos gépei már korábbi, még be nem fejezett, nem módosítható feladatokkal terheltek, így az utolsó végrehajtásra kiadott és érvényben lévı finomprogram következményei hatással vannak az új finomprogramra. Ezekbıl az általános jellemzıkbıl kiindulva – a gyártási sorozatnagyságok, a gépek allokálására és a munkák idıbeli ütemezésére koncentrálva – az anyagok, komponensek és humánerıforrások rendelkezésre állásának egyszerősítésével – definiáltam a vizsgált ütemezési feladat osztályát, melyet kiterjesztett rugalmas flow shop (Extended Flexible Flow Shop, EFFS) ütemezési feladatnak neveztem el és a szakirodalomban használt szimbolikus jelölésrendszer felhasználásával írtam le. Az irodalomban számos példa mutatta, hogy a kitőzött ütemezési feladatnál kisebb mérető és kevésbé összetett feladatok esetében is fennáll, hogy a feladat kombinatorikus jellege következtében nem lehet polinomiális idı alatt futó algoritmust készíteni az optimális megoldás elıállítására. Ennek megfelelıen a heurisztikus megoldási módszerek kerültek a kutatás középpontjába. Nagymérető kombinatorikus optimálási feladatok megoldására korábban már hatékonyan alkalmazott megoldási módszereket, metaheurisztikákat vettem alapul. A feladatosztály jellegzetességeire alapozva kidolgoztam egy új, végrehajtásszemlélető ütemezési modellt. Ebben fontos szerepet játszottak a következı felismerések: (1) Minden logisztikai egység egy önálló absztrakt „munkának” tekinthetı, ezáltal a gyártási sorozatok nagysága az egyes gépeken idıben dinamikusan változhat, megengedve a rendelések bontását és/vagy egyesítését. (2) Az ütemezés alapegységének tekinthetı a mőveletek (technológiai lépések) gépváltás nélkül elvégezhetı sorozata (végrehajtási lépés), elısegítve a többfunkciós gépek kezelését, végrehajtási útvonalak és gépcsoportok definiálását, továbbá a rendelések feladatokra bontását. (3) Egy termelési finomprogram funkcionális szempontból három részre bontható és így hatékonyabban kezelhetı. Ezek a következık: (a) feladatok (munkák és gépek összerendelése), (b) gépenkénti feladat végrehajtási sorrendek, (c) feladatok végrehajtásának tervezett idıadatai. A kidolgozott ütemezési modell építıelemeinek számítógépi realizálására kifejlesztettem egy adatmodellt, amelyben indexelt tömböket használtam az adatelérés egyszerősítése és gyorsítása érdekében. A tömbökben a gyártási környezetre jellemzı entitások (pl. megrendelések, munkák, gépek, termékek stb.) indexekkel vannak helyettesítve, ezek kapcsolatát a tömbökben tárolt alapadatokra történı hivatkozások rendszere írja le. Ennek egyik fontos elınye az, hogy egy tetszıleges elembıl kiindulva – az indexelési szabályok betartásával – minden egyes vele kapcsolatban álló elem közvetlenül elérhetı. Az adatmodellre alapozva kifejlesztettem egy szabályalapú számítási eljárást, amely a gyártási folyamat gyors szimulációjára alkalmas. Ennek egyik célja az volt, hogy az ütemezési feladat speciális tulajdonságait kezelı részek jól elkülönüljenek a
TÉZISFÜZET
11
megoldási módszer általánosan használható részeitıl, ezáltal növelje a megoldás rugalmasságát, továbbfejlesztési lehetıségeit. A szimuláció alkalmazásának másik célja az volt, hogy a finomprogramban szereplı feladatok idıadatai minél rövidebb idı alatt kiértékelhetık legyenek. Ennek a kettıs célnak megfelelıen a szimuláció veszi figyelembe a gépek ismert korábbi terheléseit, elıírt rendelkezésre állási idıintervallumait, a gépeken a munkasorrend által meghatározott átállítási idıket, a munka-gép összerendelések és az eltérı termelési sebességek alapján számítható megmunkálási idıket. Ezáltal a finomprogramban szereplı feladatok, munkák és megrendelések kezdési és befejezési idıpontjai ismertté válnak, ezeket felhasználva termelési mutatók és célfüggvények számításával minısítetté válik a megoldás. Az így felállított végrehajtás-szemlélető szimulációra alapozott megoldási koncepció következtében a termelési finomprogram elkészítése az egyes munkák feladatokra bontására és a feladatok gépenkénti sorrendjének meghatározására redukálódott. Eközben a lehetséges megvalósítható finomprogramok halmaza könnyebben kezelhetıvé vált. A kutatás során ennek a redukált problémának a megoldására több heurisztikus módszert fejlesztettem ki. Már a kutatás kezdeti szakaszában is olyan megoldási módszerekkel foglalkoztam, amelyek a felhasználó által választható, de választás után rögzített célfüggvény optimalizálására koncentráltak, ezáltal alkalmazásuk nem korlátozódott pusztán egyetlen célfüggvényre. Ezt a szemléletet követve, a gyakran változó célokhoz való rugalmas alkalmazkodás biztosítása érdekében kidolgoztam egy többcélú eredményértékelı módszert. A módszer elıredefiniált célfüggvények felhasználó által megadott mértékő figyelembevételével az egyes megengedett megoldások egymáshoz viszonyított minısítésén alapult. Ezt a módszert alkalmaztam a megoldóalgoritmusokban a termelési finomprogramok minıségének összehasonlítására és javítására. A kidolgozott megoldási módszerek menetét figyelembe véve alapvetıen két csoportba sorolhatók: (1) Az elsı csoportba tartoznak a felépítı jellegő heurisztikák. Ezek a módszerek az elızı finomprogram még be nem fejezett részébıl kiindulva, a kiválasztott, soron következı ütemezendı munkához tartozó útvonalra, gépre és sorrendre vonatkozó döntéseket heurisztikus szabályok és szimulációs kiértékelés alapján hozzák meg. (2) A második csoportba tartoznak az iteratív javításon alapuló heurisztikák. Ezeknél a módszereknél egy kezdeti megvalósítható ütemtervbıl kiindulva megengedett módosítások és szimulációs kiértékelések iterálásával alakul ki az aktuális céloknak jobban megfelelı termelési finomprogram. A megoldási módszerek és az azok által elıállított eredmények részletes vizsgálata, fejlesztése érdekében kidolgoztam egy interaktív grafikus felhasználói felületet. Ezt követıen olyan felhasználói beavatkozást támogató szolgáltatásokat terveztem meg és építettem be, amelyek interaktív tervezıi felületen keresztül érhetık el, ezáltal lehetıvé teszik a természetes (felhasználói) intelligencia és a megoldási módszerekben realizált mesterséges (számítógépi) intelligencia kombinált
12
TÉZISFÜZET
alkalmazását. A különbözı szemlélető megoldási módszerek elınyös tulajdonságainak egyesítésére többfázisú, kombinált megoldási koncepciót fejlesztettem ki. A kidolgozott modellek, módszerek és algoritmusok alapján C++ Builder szoftverfejlesztı környezetben objektumorientált módon implementáltam egy ütemezıszoftver-prototípust, amely alkalmas EFFS ütemezési feladatok megoldásának automatikus, kézi és kombinált üzemmódú elıállítására. A szoftver prototípusát átlagos személyi számítógépre, Windows operációs rendszeren történı használatra fejlesztettem ki.
5. ÚJ TUDOMÁNYOS EREDMÉNYEK 1. tézis:
Új, kiterjesztett rugalmas Flow Shop ütemezési modell és annak számítógépi reprezentációja.
Ismeretes, hogy a diszkrét termelési folyamatok mőhelyszintő prediktív ütemezése mind elméleti, mind gyakorlati szempontból az erısen modellfüggı és komplex feladatok körébe tartozik. A klasszikus „Flow Shop” ütemezési feladat formális modellje egy hármassal jellemezhetı: ( M , J , f ) ahol M az erıforrások, J a feladatok (munkák) és f az irányítási célok leírása. Ebben a modellben az optimális ütemterv elıállítása már a klasszikus egyutas, elızésmentes esetre is NP-teljes feladat. A napjaink ipari gyakorlatában egyre fontosabbá váló, rugalmas és igény szerinti tömeggyártás irányítása szükségessé teszi az ismert ütemezési modellek további jelentıs kiterjesztését. 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. Az új, kiterjesztett modellt a következık jellemzik: 1.1 Egyszerre jelennek meg benne: (1) több mővelet együttes végrehajtására képes összetett gépek (gépsorok), (2) párhuzamos gépekbıl funkciók szerint szervezett gépcsoportok, (3) terméktípustól függı végrehajtásiútvonal-alternatívák, (4) géptıl és terméktıl függı termelési intenzitások, (5) géptıl függı változó rendelkezésre állási idıintervallumok, (6) munkák sorrendjétıl függı gépátállítási idık, (7) munkák indítására és befejezésére vonatkozó idıkorlátok. 1.2 Lehetıvé teszi a munkák dinamikus kezelését, a rendelések összevonását és/vagy szétbontását. A modellnek ez a tulajdonsága a tömeggyártás „sorozatnagyság” problémájának egy lehetséges értelmezését nyújtja.
TÉZISFÜZET
13
1.3 Egyidejőleg több és változó fontosságú optimalizálási célt valamint interaktív tervezıi beavatkozásokat is képes kezelni a termelésirányítás rugalmasan változó igényeinek kielégítése érdekében. Definiáltam az ütemezési modell építıelemeit, részletesen megadtam a hozzájuk tartozó attribútumokat és leírtam azok kapcsolatrendszerét. Kifejlesztettem egy számítógépi implementálásra közvetlenül alkalmas adatmodellt, amelyben indexelt hivatkozásrendszert alkalmaztam az adatkezelés egyszerősítése és gyorsítása érdekében. A modell alkalmazhatóságát a számítógépes implementáció tesztfeladatainak elemzése igazolta. A modell tulajdonságait az értekezés 3. fejezete ismerteti. A modellt a [10], [8], [7], [13], [11] és az [1], [3] publikációkban is részletesen bemutattam.
2. tézis:
Többfázisú heurisztikus módszer az EFFS ütemezési feladatok megoldására.
Az ismert FFS ütemezési feladatokhoz viszonyítva az 1. tézisben definiált EFFS termelésprogramozási feladatokban a végrehajtási útvonalak és a párhuzamos gépek alternatívái, valamint a dinamikus sorozatnagyság-képzés lehetıségei jelentısen megnövelik a megvalósítható ütemtervek keresési terét. A méretnövekedésnek a feladat megoldása szempontjából nehezítı hatását fokozza a megengedett megoldások terének szerkezetváltozása is. Ez a változás – többek között – a többmőveletes végrehajtási lépések, a gépenként változó termelési intenzitások, és az átállítási idıtartamok munka-függıségének következménye. További speciális követelményt jelent a gépek terhelhetıségénél egyes korábban ütemezett terhelések figyelembe vétele. Ezek következményeként az EFFS feladatok megoldására az ismert ütemezési módszerek közvetlenül nem alkalmazhatók, szükség van a gyakorlatban elıforduló mérető és nehézségő feladatokat megoldó, elfogadható futási idejő új módszerek kifejlesztésére. 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.
14
TÉZISFÜZET
Rendelés
Termelési finomprogram
Célfüggvényértékek
Termék Technológia Erıforrás
Modellépítés
Ütemezés Munkák Ütemterv
Szimuláció
Éles termelési finomprogram
Modellobjektumok
Finomprogram
Minısítés Teljesítménymutatók
1. ábra: Az ütemezı belsı struktúrájának vázlata
A módszer fontosabb jellemzıi: 2.1 A belsı rendelések ütemezési alapegységekre bontásával önálló munkák jönnek létre. Ezek ütemezése egymástól függetlenül, végrehajtási lépésekre alapozott feladatok (taszkok) formájában történik (a csomagkapcsolt hálózati adattovábbítás elvének egy speciális alkalmazásával). Ezáltal a gépeken a gyártási sorozatnagyságok és az azokat elválasztó átállítási mőveletek dinamikusan, ütemezés közben alakulnak ki. 2.2 A technológiai alternatívák teljes körő rendszerezését és megvalósíthatósági (érvényességi) vizsgálatát követıen azok beépülnek az EFFS modellben szereplı építıelemek attribútumai által definiált kapcsolatrendszerbe. Minden egyes döntési helyzetben a választás már csak megengedett megoldást eredményezhet, ezért nincs szükség további megvalósíthatósági vizsgálatra. 2.3 Az EFFS feladatosztályhoz tartozó (gépek aktuális terhelésére és rendelkezésre állására, legkorábbi mőveletkezdésre, mőveleti sorrendre, rendelések határidejére vonatkozó) korlátfeltételek és a speciális követelmények (eltérı termelési intenzitások, változó átállítási idıtartamok, különbözı mérető logisztikai egységek) figyelembevételét egy szabályalapú számítási eljárás végzi, amely egy jól definiált ütemterv adott gyártási környezetben történı végrehajtásának gyors szimulációjára is alkalmas. 2.4 A végrehajtás-szimuláció az ütemtervben szereplı gyártási feladatokhoz, munkákhoz és megrendelésekhez tartozó kezdési, elıkészítési, mőveleti és befejezési idıadatok kiszámításával a problématér transzformációját valósítja meg. Egy egyszerősített ütemtervhez – amely a munkák és gépek megengedett összerendeléseit és a munkák végrehajtásának gépenkénti sorrendjét tartalmazza
TÉZISFÜZET
15
– egyértelmően hozzárendel egy megvalósítható, minısített, részletes termelési finomprogramot. 2.5 A hozzárendelési és sorrendi problémákat egy kétfázisú, kombinált heurisztikus módszer oldja meg. Az elsı fázisban gyors felépítı algoritmusok (BWBA, HEFCA, HIA, EHIA) több „jó” kezdeti megoldást generálnak. A legjobb kezdeti megoldásból kiindulva a második fázisban többféle szomszédsági operátor (N1, N2, N3, N4, N5) kombinált alkalmazásával, többfunkciós tabulista-kezeléssel és folyamatos tanuláson alapuló, paraméteres szabályozással mőködı, tabukeresési megoldóalgoritmus javítja a megoldást. A definiált EFFS ütemezési feladatok megoldására tesztadatok és/vagy összehasonlításra alkalmas eredmények a szakirodalomból közvetlenül nem nyerhetık. Az új, integrált ütemezési módszer vizsgálatára ezért egy számítógépi keretrendszert hoztam létre. A rendszer egymástól jól elkülönített funkcionális modulokból áll, így az egyes modulok, a megvalósított funkciók, valamint azok különbözı algoritmusai önmagukban is, csoportosan is tesztelhetık, összehasonlíthatók. A módszer helyességét és hatékonyságát – erre a célra fejlesztett problémagenerátorral elıállított – különbözı mérető és nehézségő tesztfeladatokon elvégzett futási eredmények támasztják alá. A megoldási módszer részleteit, a kifejlesztett algoritmusokat az értekezés 4. fejezete részletesen ismerteti, valamint a [10], [7], [13], [12], [11] és az [1], [2], [3] publikációkban nyomon követhetık a módszer kifejlesztésének fontosabb fokozatai.
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.
Ismeretes, hogy a többcélú, kombinatorikus optimalizálási feladatoknak csak kivételes esetekben van olyan megoldása, amely az összes célfüggvény szempontjából egyszerre tekinthetı optimálisnak. Kompromisszumos megoldás értelmezéséhez és megtalálásához szükséges annak definiálása, hogy milyen szempontok szerint és hogyan hasonlíthatók össze a lehetséges megoldások. Léteznek különbözı elvek és módszerek erre a célra, azonban dinamikus rendszerekben ezek alkalmazása – fıként a paraméterezés bonyolultsága miatt – nehézkes, így indokolt új, rugalmasan, könnyen adaptálható módszerek kifejlesztése. Matematikai modellt és megoldási módszert dolgoztam ki a kombinatorikus optimalizálási feladatokban elıírt – dinamikusan fontosságú, különbözı dimenziójú és értékkészlető – célfüggvények figyelembevételére és a megengedett megoldások egymáshoz viszonyított minıségének számszerősítésére.
többcélú változó együttes (relatív)
16
TÉZISFÜZET
A módszer rövid leírása: Jelölje S a megengedett megoldások halmazát. Adottak az f1 ,..., f K optimalizálási célfüggvények: f k : S → ℜ + ∪ {0} , ∀ k ∈ {1, 2 ,..., K } .
A feladat a legjobb s* ∈ S „kompromisszumos” megoldás megtalálása. min [ f 1 ( s ),... f k ( s ),... f K ( s )] , ∀ k ∈ {1, 2 ,..., K } . s∈ S
Legyenek wk ∈ ℜ , wk ≥ 0 , ∀ k ∈ {1, 2 ,..., K } ,
a célfüggvények aktuális fontosságát, „prioritását” kifejezı tényezık, amelyek értékei egymástól függetlenül a felhasználó által tetszılegesen beállíthatók. Legyenek az sx , s y , sz ∈ S lehetséges (megengedett) megoldások. Jelölje max a következı operátort: a , ha a > b max : ℜ 2 → ℜ , max( a , b) = . b, egyébként
Legyen D a következı függvény: 0, ha max(a , b) = 0 D : ℜ → ℜ , a, b ∈ ℜ , D ( a , b) = b − a . max(a , b) ⋅ 100, egyébként 2
Legyen F a következı függvény: K
F : S 2 → ℜ , F ( s x , s y ) = ∑ ( wk ⋅ D ( f k ( s x ), f k ( s y ))) . k =1
A tézisben leírt módszer az F ( sx , s y ) elıjeles értéket nevezi az sy megoldás sx megoldáshoz viszonyított (relatív) jóságának (minıségének). Ennek alapján a következı relációs operátorokat definiáltam: s x < s y (sx jobb megoldás, mint sy) akkor, ha F (sx , s y ) > 0 . s x = s y (sx, sy azonosan jó megoldások) akkor, ha
F (sx , s y ) = 0 .
s x > s y (sx rosszabb megoldás, mint sy) akkor, ha
F (sx , s y ) < 0 .
A módszer többféle feladat-megoldási stratégiában is jól felhasználható az aktuális céloknak legjobban megfelelı megoldás megtalálására. A módszert – termelési finomprogramok minıségének összehasonlítására – objektumorientált elvek alapján, relációs operátorok újraértelmezésével implementáltam. Kimutattam, hogy a módszer széles problémakörben felhasználható ismert keresési algoritmusok (metaheurisztikák) támogatására, kombinatorikus többcélú optimálási feladatok megoldására. A módszert és annak tulajdonságait az értekezés 4.3.2. fejezete részletesen ismerteti, valamint az [1], [3], [12] és az [4] publikációkban is bemutattam.
TÉZISFÜZET
4. tézis:
17
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 rugalmas tömeggyártásban fellépı mőhelyszintő termelésirányítási feladatok esetében a hagyományos MES alkalmazások az igények egy részét nem tudják maradék nélkül kielégíteni. Hatékony, zárt (visszacsatolt) irányítás (szabályozás) megvalósítása érdekében szükség van a tervezett és a tényleges termelésirendszerállapot ismételt összevetésére és szükség esetén korrekciós beavatkozások kezdeményezésére. A kívánt állapotot a mindenkori érvényes termelési finomprogram képviseli, amely a termelés teljesítményét mérı mutatók elıidejő optimalizálásával készült. Ehhez szükséges, hogy az ütemezıben rendelkezésre álljon egy gyors termelésifolyamat-szimulátor. Az éles finomprogram valós termelési teljesítményét mérı mutatók a MES rendszerbıl visszacsatolhatók és összevethetık a tervezettekkel. Az értékelés egyik lehetséges következményeként a hatékony beavatkozás érdekében újraütemezésre kerülhet sor, amelyet a ütemezı megoldó heurisztikája és/vagy egy interaktív kézi ütemezést biztosító szolgáltatás támogathat. 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ésirányítási feladatainak integrált, kiterjesztett funkciójú kezelésére. A modellt a következık jellemzik: 4.1 Az elıidejő ütemezésre használt megoldási módszer továbbfejlesztett, kibıvített formában újraütemezési feladatok megoldására is alkalmas. Ez kezdeti megoldásnak az eredetileg érvényben lévı ütemtervet vagy annak egy interaktív szerkesztéső következményét tekinti. A minısítés kritériumai között ilyenkor megjelennek olyan új elemek is, amelyek kifejezik az ütemtervváltozásokkal szemben támasztott speciális igényeket. Ilyenek lehetnek egyedi (pl. egyes kiemelt gépek átállítására, rendelések késésének engedélyezésére vonatkozó) illetve összesített (pl. megváltozott allokációk vagy indítási sorrendek számának minimalizálására vonatkozó) elvárások is. 4.2 A termelés rövid távú programozására valamint a termelési bizonytalanságokból és zavarokból keletkezı hibák elhárítására (csökkentésére) funkcionális komponensekbıl felépített termelésprogramozó szoftvert hoztam létre. Az alkalmazás funkcionális modelljét, és a termelésinformatikai rendszerben betöltött szerepét a 2. ábra vázolja.
18
TÉZISFÜZET
2. ábra: Az integrált ütemezı/újraütemezı szoftver funkcionális kapcsolatai
4.3 A szoftver új, többfunkciós koncepciót valósít meg a következı fı komponensekkel: (1) többfunkciós paraméterkezelı, (2) ütemezési feladatgenerátor (modellépítı), (3) heurisztikán és keresési metaheurisztikán alapuló feladatmegoldó ütemezı és újraütemezı (interaktív grafikus felülettel a felhasználói beavatkozás támogatására), (4) gyors termelésifolyamat-szimulátor a taszkok idıadatainak meghatározására és (5) termelési teljesítménymutatókat számító és minısítı komponens. 4.4 A modellt megvalósító szoftver a gyártásirányító vezetıi döntéshozást automata, kézi és kombinált üzemmódban, termelési célfüggvények és mutatók számításával, részletes és áttekinthetı grafikus diagramok, táblázatos jelentések készítésével támogatja. 4.5 Fontos jellemzıje az alkalmazásnak, hogy megrendelés-, munka-, feladat- és gépszintő konzisztens beavatkozást biztosító interaktív operációkészlettel támogatja a felhasználót az ütemezési és újraütemezési feladatok megoldásában, ezáltal lehetıvé teszi a természetes (felhasználói) intelligencia és a megoldási módszerekben realizált mesterséges (számítógépi) intelligencia kombinált alkalmazását. A kidolgozott modell és a megoldóalgoritmusok alapján megterveztem és C++ Builder szoftverfejlesztı környezetben objektumorientált módon megvalósítottam a többfunkciós, integrált termelésprogramozó szoftver prototípusát, amely alkalmas:
TÉZISFÜZET
19
(1) Többmőveletes, EFFS típusú termelésirányítási feladatok többkritériumos optimumközeli ütemezésére. (2) A tervezett és a megvalósult termelési célok összevetésére. (3) Viselkedés alapú beavatkozás támogatójaként a feladatok újrafogalmazására. (4) A feladatok újraütemezésére. A szoftver alkalmazhatóságát próbafeladatokon végrehajtott tesztek eredményei támasztják alá. A modell jellemzıit, a szoftver felépítésének részleteit, az alkalmazott információs technológiát, valamint az interaktív felhasználói felület tulajdonságait az értekezés 5. és 6. fejezete részletesen ismerteti. A legfontosabb jellemzık az [1], [2], [3], [7], [12], [11] és a [4] publikációkban is bemutatásra kerültek.
6. AZ EREDMÉNYEK HASZNOSÍTHATÓSÁGA A Miskolci Egyetem Alkalmazott Informatikai Tanszékén Erdélyi Ferenc vezetésével végzett kutatómunkám egyik feladata volt hozzájárulni az MTA SZTAKI vezette „VITAL” Valós idejő, kooperatív vállalatok (NKTH 2/010/2004) kutatási projekt Integrált kapacitástervezés, erıforrás-menedzsment és ütemezés klasztere keretében folyó kutatási és fejlesztési munka támogatásához. Az értekezésben összefoglalt eredmények (ütemezési modell, megoldási koncepció, az alkalmazott módszerek és a megvalósított funkciók) szóbeli prezentáció és írásos kutatási jelentések formájában kerültek belsı felhasználásra. Az értekezésben összefoglalt eredmények a rugalmas tömeggyártás más területein is hasznosíthatók. Mintafeladatokon produkált futási eredmények azt mutatják, hogy a kifejlesztett EFFS ütemezési modell és annak megoldómódszerei alkalmasak a definiált feladatosztályba sorolható sokféle ütemezési feladat megoldására. A megvalósított szoftverprototípus adatbáziskezelı rendszerekhez (DBMS) kapcsolódhat, ezáltal termelésinformatikai rendszerekbe ágyazható. Gyakorlati alkalmazásához szükség lehet a konkrét termelési adatbázis-struktúrához illesztı (adatkonverziós) modul módosítására, a felmerülı igényeknek megfelelıen további célfüggvények, termelési mutatók definiálására, valamint a konkrét gyártó-szerelı rendszer speciális jellemzıinek és igényeinek megfelelıen a szimulátor módosítására, esetleg továbbfejlesztésére. Az ütemezı szoftver könnyen kezelhetı grafikus felülete, beépített problémagenerátora, valamint eredménykijelzı és -értékelı szolgáltatásai lehetıvé teszik a felsıfokú oktatásban való felhasználását is (pl.: ME Alkalmazott Informatikai Tanszék által oktatott „Számítógépes gyártásirányítás”, „Számítógépes termelésirányítás”, „Termelési rendszerek és folyamatok” és „Számítógéppel integrált gyártás” c. tárgyak laborgyakorlatainak keretein belül). A többcélú optimalizálási feladat megoldásainak egymáshoz viszonyított (relatív) minıségének számszerősítésére kifejlesztett (a harmadik tézisben összefoglalt) matematikai modell és megoldási módszer – termelésütemezési problémától független tulajdonsága következtében – széles feladatkörben felhasználható ismert keresési
20 algoritmusok és metaheurisztikák optimalizálási feladatok megoldására.
TÉZISFÜZET támogatására,
kombinatorikus
többcélú
7. TOVÁBBI KUTATÁSI FELADATOK A továbbfejlesztés egyik iránya lehet az EFFS modell bıvítése. Ez vonatkozhat egyrészt a modell specializálására, finomítására további részletek kibontásával, modellezésével és beépítésével. Ilyenek lehetnek például a gyártási folyamat során felhasznált anyagokkal, beépülı komponensekkel és azok alternatíváival mint nem megújuló erıforrásokkal kapcsolatos kérdések részletes vizsgálata, korlátozott mérető átmeneti tárolók, anyagmozgatási idık figyelembevétele és hatásuk vizsgálata. Általános irányú funkcionális bıvítés is kitőzhetı cél lehet, melynek során a modellel kezelhetı ütemezési feladatok körét tovább lehet szélesíteni. Ilyenek lehetnek például a mővelet-végrehajtási (pl. megszakíthatóságra vonatkozó) jellemzık változtatásából származó feladatok, a mőveleti sorrendekre vonatkozó elıírások általánosításából eredı („job shop”, „open shop” vagy „general shop” típusú) feladatok kezelésére irányuló kutatások. A továbbfejlesztés egy másik lehetséges irányát jelentheti a tisztán determinisztikus elıidejő ütemezési (proactive) és újraütemezési (reactive) feladok vizsgált körének bıvítése sztochasztikus ütemezési feladatok irányába, adott eloszlások szerint véletlenszerően generált elemek (pl. idıközben beérkezı megrendelések, ütemezés közben megváltozó mőveleti és rendelkezésre állási idık, egyéb jellemzık) bevonásával. További kutatási feladatot jelenthetnek a szimulációt megvalósító, a megoldást elıállító és a kiértékelést végzı algoritmusok sebességének növelésére (összességében az adott minıségő eredmények elıállításához szükséges futási idı csökkentésére, vagy adott futási idıkorlát mellett elérhetı még jobb minıségő eredmények elıállítására) irányuló törekvések. Hosszú távú fejlesztési célként említhetı meg az ütemezı szoftver és további (meglévı vagy fejlesztés alatt álló) alkalmazások felhasználásával az ME AIT termelésinformatikai laboratóriumában virtuális körülmények között mőködı teljes funkcionalitású gyártásirányító rendszer kialakítása kutatási és oktatási céllal.
TÉZISFÜZET
21
8. AZ ÉRTEKEZÉS TÉMAKÖRÉBEN KÉSZÍTETT SAJÁT PUBLIKÁCIÓK Angol nyelven megjelent tudományos közlemények: [1] KULCSÁR, GY., ERDÉLYI, F., 2007, A New Approach to Solve Multi-Objective Scheduling and Rescheduling Tasks, International Journal of Computational Intelligence Research, Vol. 3, No. 4, (megjelenés alatt). [2] TÓTH, T., ERDÉLYI, F., KULCSÁR, GY., 2008, Decision Supporting of Production Planning and Control by means of Key Production Performance Measuring Indicators, Seventh International Symposium on Tools and Methods of Competitive Engineering, TMCE 2008, April 21–25, 2008, Kusadasi, Turkey, (közlésre elfogadva). [3] KULCSÁR, GY., ERDÉLYI, F., HORNYÁK, O., 2007, Multi-Objective Optimization and Heuristic Approaches for Solving Scheduling Problems, IFAC Workshop on Manufacturing Modeling, Management and Control, MIM 2007, Budapest, November 14-16, 2007, pp. 127-132. [4] KULCSÁR, GY., ERDÉLYI, F., 2007, Multi-Objective Searching Methods for Solving Scheduling and Rescheduling Problems, microCAD 2007 International Scientific Conference, Miskolc, Hungary, pp. 133-138. [5] HORNYÁK, O., ERDÉLYI, F., KULCSÁR, GY., 2006, Behaviour-Based Control for Uncertainty Management in Manufacturing Execution Systems, Proceedings of the 8th International Conference on The Modern Information Technology in the Innovation Processes of the Industrial Enterprises, MITIP 2006. September 11-12, 2006, Budapest, Hungary, pp. 73-79. [6] HORNYÁK, O., ERDÉLYI, F., KULCSÁR, GY., 2006, Detailed Scheduling and Uncertainty Management in Customized Mass Production, 12th International Conference on Machine Design and Production, Kusadasi, Turkey, pp. 423439. [7] KULCSÁR, GY., ERDÉLYI, F., 2006, Modeling and Solving of the Extended Flexible Flow Shop Scheduling Problem, Production Systems and Information Engineering, A Publication of the University of Miskolc, Vol. 3, Miskolc, Hungary, pp. 121-139. [8] KULCSÁR, GY., ERDÉLYI, F., 2006, Extended Flexible Flow Shop Scheduling Problem with Limited Machine Availability, microCAD 2006 International Scientific Conference, Miskolc, Hungary, pp. 181-186. [9] KULCSÁR, GY., ERDÉLYI, F., 2005, Production Goals and Heuristics Methods in Extended Flexible Flow Shop Scheduling Problems, Forum of PhD Students, Miskolc, Hungary, pp. 104-109.
22
TÉZISFÜZET
[10] KULCSÁR, GY., HORNYÁK, O., ERDÉLYI, F., 2005, Shop Floor Decision Supporting and MES Functions in Customized Mass Production, Conference on Manufacturing Systems Development - Industry Expectations, Machine Engineering, Vol. 5. Wroclaw, Poland, pp. 138 - 152. Magyar nyelven megjelent tudományos közlemények: [11] KULCSÁR, GY., 2006, Az igény szerinti tömeggyártás termelésprogramozásának heurisztikus megoldási módszere, Gyártás-2006 Magyar Tudományos Konferencia, pp. 130-140. [12] KULCSÁR, GY., 2006, Az igény szerinti tömeggyártás termelésprogramozásának egy hibrid megoldási módszere, Doktoranduszok Fóruma, Miskolc, pp. 104-111. [13] KULCSÁR, GY., 2006, Az igény szerinti tömeggyártás termelésprogramozásának modellezése és heurisztikus megoldása, GÉP, A Gépipari Tudományos Egyesület Mőszaki Folyóirata, LVII. évfolyam, 2006/10 szám, pp. 3-13. [14] KULCSÁR, GY., ERDÉLYI, F., 2006, Kiterjesztett rugalmas Flow Shop ütemezési feladat modellezése és megoldása, Fiatal Mőszakiak Tudományos Ülésszaka, Kolozsvár, Románia, pp. 223- 226. [15] HORNYÁK, O., ERDÉLYI, F., KULCSÁR, GY., 2005, Valós idejő gyártásirányítás (MES) funkciók fejlıdése, modellek és módszerek, Informatika a felsıoktatásban 2005, CD, Debrecen. [16] KULCSÁR, GY., ERDÉLYI, F., 2004, Technológiai alternatívák hatása rövid távú termelés ütemezési feladatok megoldására, Doktoranduszok Fóruma, Miskolc, pp. 173-178.
9. HIVATKOZOTT IRODALOM [17] AHR, D., BÉKÉSI, J., GALAMBOS, G., OSWALD, M., REINELT, G., 2004, An Exact Algorithm for Scheduling Identical Coupled Task Problems, Mathematical Methods of Operations Research, Vol. 59, No. 2, pp. 193-203. [18] ALCARAZ, J,, MAROTO, C., RUIZ, R,, 2006, Two New Robust Genetic Algorithms for the Flowshop Scheduling Problem, Omega, Vol. 34, pp. 461476. [19] ALLAHVERDI, A., GUPTA, J., N., D., ALDOWAISAN, T., 1999, A Review of Scheduling Research Involving Setup Considerations, Omega, Vol. 27, No. 2, pp. 219-239. [20] ALLAHVERDI, A., NG, C., T., CHENG, T., C., E., KOVALYOV, M., Y., 2007, A Survey of Scheduling Problems with Setup Times or Costs, European Journal of Operational Research, In Press, Corrected Proof, Available online 13 November 2006.
TÉZISFÜZET
23
[21] ALLAOUI, H., ARTIBA, A., 2006, Scheduling Two-Stage Hybrid Flow Shop with Availability Constraints, Computers and Operations Research, Vol. 33, pp. 1399-1419. [22] ARTHANARI, T., S., RAMAMURTHY, K., G., 1971, An Extension of Two Machines Sequencing Problem, Journal of Operational Research, Vol. 41, pp. 641-648. [23] ASKIN, G., A., STANDRIDGE, C., R., 1993, Modeling and Analysis of Manufacturing Systems, John Wiley and Sons Inc., New York. [24] AYTUG, H., LAWLEY, M., A., MCKAY, K., MOHAN, S., UZSOY, R., 2005, Executing Production Schedules in the Face of Uncertainties: A Review and some Future Directions, European Journal of Operational Research, Vol. 161, pp. 86-110. [25] BRUCKER, P., 1998, Scheduling Algorithms, Secong, Revised and Enlarged Edition, Springer-Verlag, Berlin. [26] BRUCKER, P., KNUST, S., 2006, Complexity Results for Scheduling Problems, http://www.mathematik.uni-osnabrueck.de/research/OR/class/ [27] CHENG, T., C., E., GUPTA, J., N., D., WANG, G., 2000, A Review of Flowshop Scheduling Research with Setup Times, Production and Operations Management, Vol. 8, No. 3, pp. 262-282. [28] CHROBAK, M., CSIRIK, J., IMREH, CS., NOGA, J., SGALL, J., WOEGINGER, G., 2001, The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts, Proceedings of ICALP 2001, LNCS 2076, pp. 862-874. [29] CRESCENZI, P., KANN, V., 2005, A Compendium of NP Optimization Problems, http://www.nada.kth.se/~viggo/problemlist/ [30] CSÁJI, B., CS., MONOSTORI, L., 2005, Stochastic Reactive Production Scheduling by Neurodynamic Learning, 16th IFAC World Congress, July 4-8, 2005, Prague, Czech Republic, (CD version is available). [31] CSÁJI, B., CS., MONOSTORI, L., 2005, Stochastic Reactive Production Scheduling by Multi-Agent Based Asynchronous Approximate Dynamic Programming, Lecture Notes in Artificial Intelligence, Springer, Vol. 3690, Proceedings of the 4th International Central and Eastern European Conference on Multi-Agent Systems (CEEMAS 2005), September 15-17, 2005, Budapest, Hungary, pp 388-397. [32] CSÉBFALVI, G., 2000, A New Exact Resource Leveling Procedure for the Multiple Resource Constrained Project Scheduling Problem, Proc. North American Productivity Workshop, Jun 15-21, 2000, Schenectady, New York, USA. [33] CSÉBFALVI, G., KONSTANTINIDIS, P., 1998, Egy implicit leszámláláson alapuló új erıforrás kiegyenlítı eljárás, Szigma, Vol. 29, pp. 43-52. [34] ERDÉLYI, F., 2004, Technológiai folyamatok automatizálásának alapjai, TÓTH, T., Termelési rendszerek és folyamatok 11. fejezete, p. 305-384, Miskolci Egyetemi Kiadó.
24
TÉZISFÜZET
[35] ERDÉLYI, F., TÓTH, T., 2006, Decision Supporting of Production Planning and Control (PPC) by Means of Rate-Type State Variables, Sixth International Symposium on Tools and Methods of Competitive Engineering, TMCE 2006, April 18-22, Ljubljana, (under review). [36] FRAMINAN, J., M., GUPTA, J., N., D., LEISTEN, R., 2002, A Review and Classification of Heuristics for Permutation Flowshop Scheduling with Makespan Objective, Technical Report OI/PPC-2001/02, Version 1.2 – 20/07/2002 (http://taylor.us.es/cicyt/reports/TROI-2001-02.pdf). [37] GAREY, M., R., JOHNSON, D., S., SETHI, R., 1976, The Complexity of Flowshop and Jobshop Scheduling, Mathematics of Operations Research, Vol. 1, No. 2, pp. 117-129. [38] GEIGER, M., J., 2006, Foundations of the Pareto Iterated Local Search Metaheuristic, Proceedings of the 18th International Conference on Multiple Criteria Decision Making, June 19-23, 2006, Chania, Greece. http://www.dpem.tuc.gr/fel/mcdm2006/Papers/Geiger.pdf [39] GUPTA, J., N., D., 1988, Two-stage, hybrid flow shop scheduling problem, The Journal of the Operational Research Society, Vol. 39, No. 4, pp. 359-364. [40] HOLCZINGER, T., ROMERO, J., PUIGJANER, L., FRIEDLER, F., 2002, Scheduling of Multipurpose Batch Processes with Multiple Batches of the Products, Hungarian Journal of Industrial Chemistry, Vol. 30, pp. 305-312. [41] HOOGEVEEN, J., A., LENSTRA, J., K., VELTMAN, B., 1996, Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard, European Journal of Operational Research, Vol. 89, No. 1-2, pp. 172-175. [42] HORNYÁK, O., ERDÉLYI, F., 2004, Manufacturing Execution System for Advanced Shop Floor Control, Proceedings of The Eleventh International Conference on Machine Design and Production, October 13-15, Antalya, Turkey. pp. 48-52. [43] IMREH, CS., 2001, Scheduling on a Two Layer Multiprocessor Architecture, Acta Cybernetica, Vol. 15, pp. 163-172. [44] IMREH, CS., 2003, Scheduling Problems on Two Sets of Identical Machines, Computing, Vol. 70, pp. 277-294. [45] JOHNSON, S., M., 1954, Optimal Two- and Three-Stage Production Schedules with Setup Times Included, Research Logistics Quarterly, Vol. 1, pp. 61-68. [46] JUNGWATTANAKI, J., REODECHA, M., CHAOVALITWONGSE, P., WERNER, F., 2006, Algorithms for Flexible Flow Shop Scheduling Problems with Unrelated Parallel Machines, Setup Times, and Dual Criteria, Preprint 200626, Mathematics Preprint Servers, Otto-von-Guericke-University, Magdeburg, Germany. [47] KÁDÁR, B., MONOSTORI, L., CSÁJI, B., 2005, Adaptive Approaches to Increasing the Performance of Production Control Systems, CIRP Journal of Manufacturing Systems, Vol. 34, No. 1, pp. 349-352.
TÉZISFÜZET
25
[48] KÁDÁR, B., PFEIFFER, A., MONOSTORI, L., 2005, Stability-oriented Evaluation of Rescheduling Strategies by using Simulation, Computers in Industry, Elsevier, (paper accepted in 2006). [49] KIS T., PESCH, E., 2005, A Review of Exact Solution Methods for the NonPreemptive Multiprocessor Flowshop Problem, European Journal of Operational Research, Vol. 164, No. 3, pp. 573-695. [50] KIS, T., ERDİS, G., 2005, Specification: Automatic Scheduling System with Basic Scheduling Engine for GE Lighting, (VITAL project NKTH 2/010/2004: internal report). [51] KOVÁCS, A., EGRI, P., KIS, T., VÁNCZA, J., 2005, Proterv-II: An integrated Production Planning and Scheduling System, In: Principles and Practice of Constraint Programming, Proc. of CP2005, (ed.: van Beek, P.,), Springer LNCS. [52] LEE, I., R., SIKORA, AND M., J., SHAW, 1997, A Genetic Algorithm-Based Approach to Flexible Flow-Line Scheduling with Variable Lot Sizes, IEEE Transactions on Systems, Man and Cybernetics, Vol. 27, No. 1, pp. 36-54. [53] LINN, R., ZHANG, W., 1999, Hybrid Flow Shop Scheduling: A Survey, Computers and Industrial Engineering, Vol. 37, No. 1-2, pp. 57-61. [54] LIU, C., Y., CHANG, S., C., 2000, Scheduling Flexible Flow Shops with Sequence-Dependent Setup Effects, IEEE Transactions on Robotics and Automation, Vol. 16, No. 4, pp. 408-419. [55] LOUKIL, T., TEGHEM, J., TUYTTENS, D., 2005, Solving Multi-Objective Production Scheduling Problems Using Metaheuristics, European Journal of Operational Research, Vol. 161, pp. 42-61. [56] MAJOZI, T., FRIEDLER, F., 2006, Maximization of Throughput in a Multipurpose Batch Plant Under Fixed Time Horizon: S-Graph Approach, Ind. Eng. Chem. Res., Vol. 45, pp. 6713-6720. [57] MONOSTORI, L., CSÁJI, B., CS., 2006, Stochastic Dynamic Production Control by Neurodynamic Programming, Annals of the CIRP, Vol. 55, pp. 473-478. [58] MONOSTORI, L., VÁNCZA, J., KIS, T., KÁDÁR, B., VIHAROS, ZS., J., 2006, Real-Time, Cooperative Enterprises: Requirements and Solution Approaches, Preprints of the 12th IFAC Symposium on Information Control Problems in Manufacturing, INCOM-2006, May 16-19, 2006, Saint Etienne, France pp. 591-596. [59] PETROVIC, D., DUENAS, A., 2006, A Fuzzy Logic Based Production Scheduling/Rescheduling in the Presence of Uncertain Discruptions, Fuzzy Sets and Systems, Vol. 157, pp. 2273-2285. [60] Production Scheduling Portal, http://www.productionscheduling.com/production_scheduling_books.html [61] QUADT, D., KUHN, H., 2007, A Taxonomy of Flexible Flow Line Scheduling Procedures, European Journal of Operational Research, Vol. 178, pp. 686698.
26
TÉZISFÜZET
[62] RANGSARITRATSAMEE, R., FERRELL, W., G., KURZ, M., B., 2004, Dynamic Rescheduling that Simultaneously Considers Efficiency and Stability, Computers and Industrial Engineering, Vol. 46, No. 1, pp. 1-15. [63] SMITH, K., L., EVERSON, R., M., FIELDSEND, J., E., 2004, Dominance Measures for Multi-Objective Simulated Annealing, Proceedings of the 2004 Congress on Evolutionary Computation, CEC 2004, June 19-23, 2004, Portland OR, USA, pp. 23-30. [64] SOMLÓ, J., 2006, Új utak a gépipari rendszerek gyártásütemezésében, Gyártás-2006 Magyar Tudományos Konferencia, pp. 155-161. [65] SOMLÓ, J., SAWKIN, A., V., 2006, Periodic and Transient Switched Serves Schedules for FMS, Robotics and Computer Integrated Manufacturing, Vol. 22, pp.93-112. [66] SOMLÓ, J., SAWKIN, A., V., ANUFRIEV, A., KONCZ, T., 2004, Pragmatic Aspects of the Solution of FMS Scheduling Problems using Hybrid Dynamical Approach, Robotics and Computer Integrated Manufacturing, Vol. 20, No. 1, pp. 35-49. [67] TÓTH, T., ERDÉLYI, F., 2006, New Consideration of Production Performance Management for Discrete Manufacturing, Proceedings of the 8th International Conference on The Modern Information Technology in the Innovation Processes of the Industrial Enterprises, September 11-12, 2006, Budapest, Hungary, pp. 435-444. [68] VAIK, ZS., 2005, On Scheduling Problems with Parallel Multi-Purpose Machines, Technical Report TR-2005-02, MTA-ELTE EGRES, Egerváry Research Group on Combinatorial Optimization. [69] VÁNCZA, J., MÁRKUS, A., 2000, An Agent Model for Incentive-based Production Scheduling, Computers in Industry, Vol. 43, No. 2, pp. 173-187. [70] VIEIRA, G., HERMANN, J., LIN, E., 2000, Predicting the Performance of Rescheduling Strategies for Paralell Machines Systems, Journal of Manufacturing Systems, Vol. 19, No. 4, pp. 256-266. [71] VIEIRA, G., HERMANN, J., LIN, E., 2003, Rescheduling Manufacturing Systems: A Framework of Strategies, Policies and Methods, Journal of Scheduling, Vol. 6, No. 1, pp. 35-58. [72] VÍZVÁRI B., 2004, Ütemezéselmélet, IVÁNYI, A., (szerk.), Informatikai algoritmusok 9. fejezete, p. 364-415, ELTE Eötvös Kiadó. [73] VÍZVÁRI, B., DÓSA, GY., 2004, Az LPT(k)’ algoritmus egyforma párhuzamos gépek ütemezésére, Alkalmazott Matematikai Lapok, Vol. 21, pp. 269-289. [74] WANG, W., 2005, Flexible Flow Shop Scheduling: Optimum, Heuristics, and Artificial Intelligence Solutions, Expert Systems, Vol. 22, No. 2, pp. 78-85. [75] YANG, Y., KREIPL, S., PINEDO, M., 2000, Heuristics for Minimizing Total Weighted Tardiness in Flexible Flow Shops, Journal of Scheduling, Vol. 3, No. 2, pp. 89-108.
TÉZISFÜZET
27
[76] ZDANSKY, M., POZIVIL, J., 2002, Combination Genetic/Tabu Search Algorithm for Hybrid Flowshops Optimization, Proceedings of ALGORITMY 2002 Conference on Scientific Computing, pp. 230-236. [77] ZHU, X., WILHELM, W., E., 2006, Scheduling and Lot Sizing with SequenceDependent Setup: A Literature review, IIE Transactions, Vol. 38, pp. 9871007.
28
TÉZISFÜZET
NEW SCIENTIFIC RESULTS Thesis 1 A new extended flexible flow shop scheduling model and its computer representation. I defined a new class suitable for solving extended flexible flow shop (EFFS) problems. I elaborated a special model representation for computer application to be developed. The novelty of this model representation is as follows: it is able to take into consideration the most important general characteristics and requirements of customized mass production (CMP). Thesis 2 Multi-phase heuristic method for solving EFFS scheduling problems. A new integrated approach based method has been developed for solving fine scheduling problems, which can be managed by the EFFS model. The method supports the decision making of joining and/or dividing the production orders, calculation of the manufacturing lot sizes dynamically, management of the alternative technological routes, allocation of the machine resources, definition of the manufacturing tasks and scheduling its execution processes. The aforementioned method uses heuristic algorithms, searching techniques and problem space transformation based on execution simulation. Thesis 3 A new method for relative qualification of the feasible solutions of a multi-objective combinatorial optimization problem. A mathematical model and a solving method have been developed for managing the objective functions and evaluating the relative quality of the feasible solutions by comparing them to each other. The model has been applied to multi-objective combinatorial optimization problems, which include objective functions characterized by dynamically varying importance, different dimension and value range. Thesis 4 An integrated fine scheduling model for supporting uncertainty management in customized mass production. A new integrated model has been developed and its computer (software) representation has been implemented for supporting the scheduling and rescheduling tasks of the shop floor control and uncertainty management at the MES level. The solution is suitable for managing some problems of shop floor control in an integrated and extended functional form.
