ROZVRHOVÁNÍ DÍLENSKÝCH ZAKÁZEK S PODPOROU

Technická univerzita v Liberci Fakulta strojní

Radek Plechač

ROZVRHOVÁNÍ DÍLENSKÝCH ZAKÁZEK S PODPOROU POČÍTAČOVÉ SIMULACE

Diplomová práce

2009

Technická univerzita v Liberci

Fakulta strojní

Katedra výrobních systémů

Studijní program:

M 2301 – Strojní inţenýrství

Studijní obor:

2301T030 – Výrobní systémy

Zaměření:

Pruţné výrobní systémy pro strojírenskou výrobu

ROZVRHOVÁNÍ DÍLENSKÝCH ZAKÁZEK S PODPOROU POČÍTAČOVÉ SIMULACE

JOB SHOP SCHEDULING WITH THE AID OF THE COMPUTER SIMULATION

KVS-VS-193

Radek Plechač

Vedoucí práce: Konzultant:

Doc. Dr. Ing. František Manlig Ing. František Koblasa

Počet stran : Počet příloh : Počet obrázků : Počet tabulek :

63 4 12 39

V Liberci 28. 5. 2009

Zadání diplomové práce

Diplomová práce

Anotace

Diplomová práce KVS-VS-193 TÉMA:

ROZVRHOVÁNÍ

DÍLENSKÝCH

ZAKÁZEK

S PODPOROU

POČÍTAČOVÉ SIMULACE ANOTACE: Tato práce se zabývá problematikou řízení a rozvrhování zakázek na úrovni dílenského mistra a hodnotí moţnost vyuţití počítačové simulace v tomto prostředí. Práce obsahuje porovnání vhodnosti pouţití optimalizačních algoritmů s prioritními pravidly, poukazuje na výhody a nevýhody spojené s vyuţitím optimalizačních algoritmů při rozvrhování výroby a představuje problémy plynoucí z nevhodné volby účelové funkce. K řešení optimalizačních problémů je v této práci vyuţit simulační systém Simcron MODELLER.

THEME:

JOB SHOP SCHEDULING WITH THE AID OF THE COMPUTER SIMULATION

ANNOTATION:

This work deals with the job shop scheduling at the level of

foreman with the aid of the computer simulation. The work includes comparison of optimization algorithms and priority rules usability, points to the advantages and disadvantages of optimization algorithms for job shop scheduling and presents problems arising from inappropriate choice of objective function. The Simcron MODELLER simulation system is used to solve optimization problems in this work.

Klíčová slova: simulace, optimalizace, rozvrhování, optimalizační metody Zpracovatel: TU v Liberci, Fakulta strojní, Katedra výrobních systémů Dokončeno: 2009 Archivní označení zprávy: Počet stran : Počet příloh : Počet obrázků : Počet tabulek :

63 4 12 39


3

Diplomová práce

Prohlášení

Prohlášení Byl jsem seznámen s tím, ţe na mou diplomovou práci se plně vztahuje zákon č. 121/2000 o právu autorském, zejména § 60 (školní dílo) a § 35 (o nevýdělečném uţití díla k vnitřní potřebě školy). Beru na vědomí, ţe TUL má právo na uzavření licenční smlouvy o uţití mé práce a prohlašuji, ţe souhlasím s případným uţitím mé práce (prodej, zapůjčení apod.). Jsem si vědom toho, ţe uţít své diplomové práce či poskytnout licenci k jejímu vyuţití mohu jen se souhlasem TUL, která má právo ode mne poţadovat přiměřený příspěvek na úhradu nákladů, vynaloţených univerzitou na vytvoření díla (aţ do jejich skutečné výše).

Datum:

Podpis


4

Diplomová práce

Místopříseţné prohlášení

Místopřísežné prohlášení Místopříseţně prohlašuji, ţe jsem diplomovou práci vypracoval samostatně s pouţitím uvedené literatury pod vedením vedoucího diplomové práce.

V Liberci 28. 5. 2009


……………………………

5

Diplomová práce

Poděkování

Poděkování Na tomto místě bych rád poděkoval Doc. Dr. Ing. Františku Manligovi za odborné vedení a konzultace, které mi pomohly při psaní této práce. Také bych chtěl poděkovat Ing. Františku Koblasovi za poskytnutí materiálů, ze kterých jsem mohl čerpat potřebné informace.


6

Diplomová práce

Obsah

Obsah Seznam použitých zkratek ............................................................................................. 9 1

2

Úvod ....................................................................................................................... 10 1.1

Úvod do problematiky...................................................................................... 10

1.2

Cíle diplomové práce ....................................................................................... 11

Dílenské řízení výroby .......................................................................................... 12 2.1

2.1.1

MRP II ...................................................................................................... 12

2.1.2

MRP III ..................................................................................................... 13

2.1.3

OPT ........................................................................................................... 13

2.1.4

APS ........................................................................................................... 14

2.1.5

Řízení výroby s vyuţitím počítačové simulace ........................................ 14

2.2

4

Rozvrhování výrobních operací ....................................................................... 15

2.2.1

Open Shop................................................................................................. 16

2.2.2

Flow Shop ................................................................................................. 17

2.2.3

Job Shop.................................................................................................... 17

2.3

3

Systémy pro dílenské řízení výroby ................................................................. 12

Druhy rozvrhů .................................................................................................. 18

2.3.1

Semiaktivní rozvrh .................................................................................... 19

2.3.2

Aktivní rozvrh ........................................................................................... 20

2.3.3

Rozvrh bez zpoţdění ................................................................................. 21

Optimalizační algoritmy....................................................................................... 22 3.1

Rozdělení optimalizačních algoritmů .............................................................. 22

3.2

Princip činnosti pouţitých optimalizačních algoritmů ..................................... 24

3.2.1

Metoda náhodného prohledávání (Blind search – BS) ............................. 24

3.2.2

Metoda hladového prohledávání (Greedy search – GS) ........................... 24

3.2.3

Metoda simulovaného ţíhání (Simulated Annealing – SA) ..................... 25

3.2.4

Metoda zakázaného prohledávání (Tabu search – TS) ............................. 25

3.2.5

Genetický algoritmus (Genetic algorithm – GA) ..................................... 26

Simcron MODELLER .......................................................................................... 27 4.1

Optimalizační algoritmy................................................................................... 27

4.2

Prioritní pravidla .............................................................................................. 28


7

Diplomová práce 4.3 5

Účelové funkce................................................................................................. 30

Teoretické modely výroby .................................................................................... 32 5.1

Optimalizace pomocí optimalizačních algoritmů ............................................ 32

5.1.1

Zadání teoretických modelů...................................................................... 33

5.1.2

Optimalizace teoretických modelů s vyuţitím rozvrhu bez zpoţdění ...... 34

5.1.3

Optimalizace teoretických modelů s vyuţitím aktivního rozvrhu ............ 38

5.2 6

Obsah

Zhodnocení dosaţených výsledků.................................................................... 42

Model lisovny......................................................................................................... 45 6.1

Řízení zakázek pomocí prioritních pravidel .................................................... 45

6.1.1

Naměřené hodnoty .................................................................................... 45

6.1.2

Zhodnocení dosaţených výsledků ............................................................ 47

6.2

Optimalizace pomocí optimalizačních algoritmů – část 1. .............................. 47

6.2.1


6.2.2


6.3

Optimalizace pomocí optimalizačních algoritmů – část 2. .............................. 51

6.3.1


6.3.2


7

Zhodnocení využitelnosti optimalizačních metod .............................................. 56

8

Závěr ...................................................................................................................... 58

Použitá literatura .......................................................................................................... 59 Seznam obrázků a tabulek ........................................................................................... 62 Seznam příloh ................................................................................................................ 63


8

Diplomová práce

Seznam pouţitých zkratek

Seznam použitých zkratek APS

Advanced planning and scheduling (pokročilé plánování a rozvrhování)

BS

Blind search (metoda náhodného prohledávání)

ERP

Enterprise resource planning (plánování celopodnikových zdrojů)

GA

Genethic algorithm (genetický algoritmus)

GS

Greedy search (metoda hladového prohledávání)

IS

Informační systém

JIT

Just in Time (= právě včas)

MRP

Material Requirements Planning (plánování materiálových poţadavků)

MRP II

Manufacturing Resource Planning (plánování výrobních zdrojů)

OPT

Optimized Production Technology (řízení úzkých míst)

SA

Simulated annealing (metoda simulovaného ţíhání)

TS

Tabu search (metoda zakázaného prohledávání)


9

Diplomová práce

Úvod

1 Úvod 1.1 Úvod do problematiky V dnešní době se výrobní firmy stále více zaměřují na přání a potřeby svých zákazníků. Musí proto rychle, pruţně a hlavně efektivně reagovat na jejich poţadavky, coţ klade zvýšené nároky na tvorbu výrobního plánu. Důleţitou oblastí se tak stává operativní řízení výroby. [2], [20], [21] V rámci operativního řízení se rozepisují výrobní úkoly na jednotlivá pracoviště. Zároveň je důleţité určit termín zahájení výroby tak, aby byly splněny dodací lhůty (přání zákazníka). Jakmile nastane jakákoliv změna (porucha stroje, změna poţadavku zákazníka), je nutné okamţitě reagovat a patřičně upravit výrobní plán. Výsledkem je výrobek dodaný zákazníkovi v termínu ve správném mnoţství a kvalitě. [22] Snaha o rozplánování jednotlivých úkolů na aktuálně dostupná pracoviště vedla k vyuţití systémů dílenského plánování a řízení výroby. Tyto systémy přebírají výrobní zakázky od systémů ERP a umoţňují jejich rozplánování do dostupných kapacit. Zároveň zajišťují zpětnou vazbu na systém ERP. V této oblasti pozorujeme následující vývojové tendence [2]: Systémy ERP obsahující vlastní modul „Dílenské řízení“ Systémy APS vyuţívající speciální plánovací algoritmy Menší systémy podporující rozhodování mistra pomocí grafických plánovacích tabulí ve formě Ganttova diagramu

V oblasti rozvrhování výroby i vlastního dílenského řízení je stále skryt velký potenciál pro zlepšování, např. plánování do omezených kapacit, určení vhodné sekvence výrobních operací pro co nejlepší vyuţití dostupných kapacit, rychlá reakce na aktuální změny v dílně (např. porucha stroje či nemoc pracovníka) apod. Diplomová práce se zabývá naznačenou problematikou plánování a řízení výrobních pracovišť a zdrojů na úrovni dílenského řízení. Pozornost věnuje moţnostem vyuţití počítačové simulace a optimalizačních algoritmů k efektivnějšímu vyuţití dostupných kapacit i k zefektivnění práce dílenských plánovačů.


10

Diplomová práce

Úvod

1.2 Cíle diplomové práce Cílem této diplomové práce je zhodnotit moţnosti vyuţití počítačové simulace při dílenském řízení výroby. K tomu je třeba posoudit efektivnost optimalizačních algoritmů, porovnat tyto algoritmy s prioritními pravidly a odhalit problémy související s pouţitím optimalizačních algoritmů. V teoretické části práce jsou tak představeny současné moţnosti dílenského řízení výroby a popsány optimalizační algoritmy pouţívané při počítačové simulaci. V kapitole „Simcron MODELLER“ jsou uvedeny parametry optimalizačních algoritmů nastavené při optimalizaci, jsou zde popsána prioritní pravidla a vysvětleno je zde pouţití účelových funkcí. V praktické části jsou nejprve na teoretických modelech výroby vyzkoušeny optimalizační algoritmy a výsledky jsou porovnány s výsledky jednoho z nejpouţívanějších prioritních pravidel. V další kapitole praktické části je model lisovny nejprve řízen prioritními pravidly systému Simcron a poté je optimalizován pomocí optimalizačních algoritmů. Poznatky získané během všech měření jsou shrnuté v závěrečném zhodnocení.


11

Diplomová práce

Dílenské řízení výroby

2 Dílenské řízení výroby Řízení výroby na úrovni dílenského mistra navazuje na plánovací aktivity v systémech řízení a plánování výroby. Zakázky naplánované v těchto systémech musí být v dílenském řízení realizovatelné. Dílenské řízení výroby řeší vztah mezi poţadavky, termíny, zdroji a mnoţstvím v krátkodobém časovém horizontu, coţ klade vysoké poţadavky na rychlost hledání řešení a pruţnost řízení s ohledem na měnící se situaci ve výrobě. [4], [10]

2.1 Systémy pro dílenské řízení výroby Podle [4] můţeme systémy pro dílenské řízení výroby dělit do dvou skupin. Tlakový systém (Push), je takový systém, ve kterém je výroba řízena pevným plánem a vysokou prioritu zde mají podnikové cíle (např. maximalizace vyuţití podnikových zdrojů). V tahovém systému (Pull) je začátek zpracování nového výrobku podmíněn ukončením práce na předchozím výrobku a vysokou prioritu zde mají trţní cíle (např. pruţné dodávky výrobků na trh). V současné době se vyuţívá celá řada systémů pro plánování a řízení výroby. Mezi nejčastěji pouţívané patří [8]: 1. MRP II – Manufacturing Resource Planning (Plánování výrobních zdrojů) 2. MRP III – Synchro MRP II 3. OPT – Optimized Production Technology (Řízení úzkých míst) 4. APS – Advanced planning and scheduling (Pokročilé plánování a rozvrhování)

2.1.1

MRP II

Systém MRP II vznikl rozšířením funkcí systému pro plánování materiálových poţadavků (MRP). Jde o tlakový systém, jehoţ nejvhodnější vyuţití najdeme v oblasti kusové a malo aţ středně sériové výroby. Nevýhodou systémů MRP II je plánování na jednotlivých úrovních do neomezených kapacit. Aţ po naplánování se kontroluje, zdali jsou dostupné kapacity pro splnění


12

Diplomová práce


plánu. Pokud poţadavky na kapacitu zdrojů převyšují aktuální dostupnou kapacitu, je nutné tento problém řešit (např. rozšířením kapacit, přeplánováním poţadavku na méně vytíţený termín nebo změnou původního plánu). Aţ po vyváţení poţadavků na kapacity s aktuální kapacitou je moţné určit velikost výrobních objednávek a prioritní pravidla pro řízení. [4], [18] Výstupem ze systému bývá fronta operací pro aktuální a následující plánovací období. [8] 2.1.2

MRP III

Jde o tahový systém, který vznikl kombinací zásad JIT a systému MRP II. Také tento systém plánuje do neomezených kapacit. [29] Výstupem ze systému bývá fronta operací pro aktuální plánovací období. [8]

2.1.3

OPT

Princip činnosti systému OPT spočívá v analýze a optimalizaci úzkých míst v systému. Úzká místa mají výrazný vliv na průběh výroby, a proto můţe být optimálním vyuţitím úzkých kapacit docíleno zlepšení průměrného vyuţití pracovišť. [4] Systém OPT lze shrnout do devíti pravidel [10]: 1. Vyvaţuje se tok výrobků a nikoliv kapacita 2. Kapacitní moţnosti úzkých míst systému udávají úroveň vyuţití systému 3. Snaha o maximální vyuţití kapacit „neúzkých“ pracovišť není vţdy přínosem pro maximální vyuţití celého systému 4. Hodina ztráty na „úzkém“ pracovišti je hodinou ztráty celého systému 5. Hodina ušetřená na pracovišti, které není úzkým místem, nemá s ohledem na celý systém význam 6. Úzká místa ovlivňují jak průběţnou dobu výroby, tak i výši zásob 7. Velikost výrobní dávky se nerovná velikosti transportní dávky 8. Výrobní dávka by neměla být fixní, ale proměnlivá 9. Po sestavení plánů je nutné všechny předpoklady současně přezkoumat


13

Diplomová práce


Systém nejprve zjistí potřebné informace (informace o objednávkách, předpovědi poptávky, kusovníky apod.), poté identifikuje úzká místa, dále rozčlení pracoviště na běţná a úzká a nakonec navrhne rozvrh pro úzká místa. Zároveň jsou tvořeny rozvrhy pro běţná pracoviště tak, aby se tato nestala úzkými místy. [10] Výstupem ze systému bývá rozvrh pro úzká místa a místa předcházející vzhledem k technologickému postupu zakázek. [8]

2.1.4

APS

Systém APS je systém, který dokáţe plánovat do omezených kapacit. Je zaloţen na principu, podle kterého jsou výrobní kapacity a vstupní materiál optimálně vyuţity pro potřeby zákazníka. Systémy APS tak současně plánují jak poţadavky na materiál, tak i poţadavky na výrobní kapacitu. Nejčastěji najdou uplatnění v prostředích splňujících následující podmínky [25]: Výroba na zakázku Široký sortiment výrobků Výrobky se sloţitými kusovníky a technologickými postupy Častá změna výrobního plánu z důvodu nepředvídatelných změn Výhodou těchto systémů je vyuţití optimalizačních metod pro tvorbu výrobního plánu s ohledem na aktuální stav priorit. Výstupem ze systému bývá rozvrh prací pro všechna pracoviště. [8]

2.1.5

Řízení výroby s využitím počítačové simulace

Mocným nástrojem pro vyzkoušení různých variant nebo metod řízení je počítačová simulace. Dílenští plánovači mohou relativně snadno sledovat „co se stane, kdyţ…“ a tím odhadnout budoucí chování systému. Mají tak moţnost porovnávat jednotlivé scénáře výroby, hledat a odkrývat další rezervy ve výrobě a naleznout tak optimální řešení řešeného problému. [2], [22]


14

Diplomová práce


Do simulačního modelu lze zahrnout mnoho omezení (např. rozpracované zakázky, omezení počtu pracovníků, poţadavky na seřizování, stochastické vlivy apod.), coţ řada systémů ERP neumoţňuje. Výsledkem je tak mnoho důleţitých a kvalitních informací o analyzovaném procesu (např. údaje o vytíţení jednotlivých pracovišť, Ganttův diagram rozvrţených dílenských zakázek apod.), jejichţ analýzou lze získat např. detailní přehled o stavu zakázek, rozpis práce pro jednotlivé pracovníky, termíny seřizování strojů apod. Velikou výhodou řízení výroby pomocí počítačové simulace je plánování do omezených kapacit. Plánovač tak můţe při výskytu nečekané události (např. porucha stroje, nemoc pracovníka apod.) relativně snadno a rychle přeplánovat výrobu podle aktuální situace. [2]

2.2 Rozvrhování výrobních operací Rozvrhování výrobních operací se zabývá přiřazováním jednotlivých operací k pracovištím a tvorbou pořadí, ve kterém mají být operace prováděny. Mezi hlavní cíle patří [13]: Zajištění včasných dodávek Minimalizace průběţných časů výroby Maximalizace vyuţití pracovišť Minimalizace zásob a rozpracovanosti Mezi uvedenými cíly ovšem existuje konflikt (např. maximální vyuţití pracovišť vede k vysokým výrobním dávkám a zásobám). Proto je třeba stanovit takový vzájemný vztah mezi operacemi (rozvrh), který zajišťuje co moţná nejoptimálnější fungování celého systému. [4], [5], [6], [10] Úlohy rozvrhování jsou kombinatorickými problémy a počet moţných řešení je konečný. Klasické metody pro řešení kombinatorických problémů (např. dynamické programování nebo metoda větví a mezí) dokáţou poskytnout optimální řešení, ovšem u rozsáhlých problémů není moţné tyto metody v reálném čase vyuţít. [12] Tyto problémy je nutné řešit pomocí optimalizačních algoritmů, které jsou popsány ve třetí kapitole této práce.


15

Diplomová práce


Základní pojmy pouţívané při rozvrhování výrobních operací [12]: Operace – základní technologický úkon, který nelze dále rozdělit na více technologických úkonů Zakázka – skládá se z operací, které je nutné vykonat k dokončení zakázky Pracoviště – místo, kde je moţné vykonávat operace Při rozvrhování výrobních operací se rozlišují tři základní rozhodovací problémy [8], [11], [17]: 1. Otevřený problém (Open shop) 2. Sekvenční problém (Flow shop) 3. Rozvrhovací problém (Job shop)

2.2.1

Open Shop

Kaţdá zakázka se skládá z tolika operací, kolik je pracovišť Kaţdá operace se provádí na jiném pracovišti Pořadí, v jakém jsou operace prováděny na jednotlivých pracovištích, je libovolné Na kaţdém pracovišti můţe být v jednom okamţiku vykonávána pouze jedna operace jedné zakázky Příklad problému typu open shop: záruční prohlídka auta

Obr. 2.1: Model výroby typu Open shop


16

Diplomová práce 2.2.2


Flow Shop

Kaţdá zakázka se skládá z tolika operací, kolik je pracovišť Kaţdá operace se provádí na jiném pracovišti Pořadí, v jakém jsou operace prováděny na jednotlivých pracovištích, je pevně dané Toto pořadí je pro všechny zakázky stejné Na kaţdém pracovišti můţe být v jednom okamţiku vykonávána pouze jedna operace jedné zakázky Příklad problému typu flow shop: pásová výroba

Obr. 2.2: Model výroby typu Flow shop

2.2.3

Job Shop

Kaţdá zakázka se obecně skládá z nestejného počtu operací Pro provedení kaţdé operace je zapotřebí jednoznačně přidělené pracoviště Pořadí, v jakém jsou operace prováděny na jednotlivých pracovištích, je specifikováno technologií Na kaţdém pracovišti můţe být v jednom okamţiku vykonávána pouze jedna operace jedné zakázky Příklad problému typu job shop: kusová výroba na zakázku


17

Diplomová práce


Obr. 2.3: Model výroby typu Job shop

2.3 Druhy rozvrhů Rozvrh je dán rozmístěním operací v čase na jednotlivých pracovištích. Optimální rozvrh je takový, ve kterém je rozmístění operací optimální vzhledem k zadanému optimalizačnímu kritériu (např. čas dokončení všech zakázek – tzv. makespan). [17] Ke grafickému znázornění rozvrhu se pouţívá Ganttův diagram, který ukazuje naplánované posloupnosti operací v čase na jednotlivých pracovištích. V praxi se můţeme setkat se třemi druhy rozvrhů [14]: 1. Semiaktivní rozvrh 2. Aktivní rozvrh 3. Rozvrh bez zpoţdění

Obr. 2.4: Rozdělení rozvrhů [1] Optimální rozvrh patří vţdy do skupiny aktivních rozvrhů.


18



Semiaktivní rozvrh

Rozvrh je semiaktivní, pokud neexistuje ţádná operace, která by mohla být rozvrhována dříve, aniţ by došlo ke změně pořadí operací na jednotlivých pracovištích. [14]

Obr. 2.5: Porovnání neaktivního a semiaktivního rozvrhu [8]


19



Aktivní rozvrh

Rozvrh je aktivní, pokud neexistuje ţádná operace, která by mohla být rozvrhována dříve změnou pořadí operací na jednotlivých pracovištích, aniţ by došlo ke zpoţdění jiné operace. [14]

Obr. 2.6: Porovnání semiaktivního a aktivního rozvrhu [8]

Aktivní rozvrhy jsou podmnoţinou rozvrhů semiaktivních. Nevýhodou oproti rozvrhům bez zpoţdění je, ţe jich je velké mnoţství a hledání řešení tak můţe trvat dlouho. Výhodou ovšem je, ţe mezi aktivními rozvrhy se vţdy nachází rozvrh optimální. [3]


20



Rozvrh bez zpoždění

Rozvrh je bez zpoţdění, pokud není volné pracoviště v době, kdy je dostupná jakákoliv operace. [14]

Obr. 2.7: Porovnání aktivního rozvrhu a rozvrhu bez zpoždění [8]

Rozvrhy bez zpoţdění jsou podmnoţinou rozvrhu aktivních. Je jich tak méně a hledání řešení trvá kratší dobu neţ u rozvrhů aktivních. V mnoţině rozvrhů bez zpoţdění se ovšem nemusí nacházet rozvrh optimální. [3]


21

Diplomová práce

Optimalizační algoritmy

3 Optimalizační algoritmy Optimalizační algoritmy se pouţívají pro řešení problémů v inţenýrské praxi, kde je řešení daného problému analytickou cestou silně nevhodné anebo nereálné. Velké mnoţství problémů inţenýrské praxe lze definovat jako optimalizační problém (např. optimální trajektorie, optimální tloušťka stěny tlakové nádoby apod.), tzn., ţe řešený problém se můţe převést na matematický problém daný vhodným funkčním předpisem. Jeho optimalizace poté vede k nalezení argumentů tzv. účelové funkce, coţ je cílem optimalizace. [24]

3.1 Rozdělení optimalizačních algoritmů Optimalizační algoritmy lze rozdělit podle principu jejich činnosti tak, jak je to uvedeno na obr. 3.1.

Obr. 3.1: Možné uspořádání optimalizačních algoritmů [30]


22

Diplomová práce


Vlastnosti jednotlivých tříd algoritmů jsou následující [24]: 1) Deterministické optimalizační algoritmy Skupina deterministických algoritmů vyuţívá rigorózních (přesných) metod klasické matematiky. Tyto algoritmy většinou vyţadují předběţné předpoklady, které dovolí této metodě podávat efektivní výsledky. Mezi zmíněné předpoklady patří např.: problém je lineární prohledávaný prostor moţných řešení je malý účelová funkce by měla být unimodální (má pouze jeden extrém) problém je definován v analytickém tvaru Výsledkem deterministického algoritmu je jediné řešení

2) Stochastické optimalizační algoritmy Skupina stochastických algoritmů je zaloţena na vyuţití náhody. V podstatě se jedná pouze o náhodné hledání hodnot argumentů účelové funkce. Výsledkem hledání je pouze nejlepší řešení, které bylo během cyklu náhodného hledání nalezeno. Algoritmy tohoto typu bývají: pomalé vhodné pro malý rozsah argumentů účelové funkce vhodné pro hrubý odhad

3) Enumerativní optimalizační algoritmy Skupina enumerativních algoritmů počítá veškerá moţná řešení daného problému. Tento přístup je vhodné vyuţívat u problémů, jejichţ argumenty účelové funkce jsou diskrétního charakteru a nabývají malého mnoţství hodnot. Pokud by byla tato metoda vyuţita obecně, mohla by na své dokončení potřebovat čas, který je delší neţli existence vesmíru.


23

Diplomová práce


3.2 Princip činnosti použitých optimalizačních algoritmů V této práci se vyuţilo pěti různých optimalizačních algoritmů: 1) Metoda náhodného prohledávání 2) Metoda hladového prohledávání 3) Metoda simulovaného ţíhání 4) Metoda zakázaného prohledávání 5) Genetický algoritmus

3.2.1

Metoda náhodného prohledávání (Blind search – BS)

Náhodné

prohledávání

(někdy označováno

jako

slepý algoritmus)

je

nejjednodušším stochastickým algoritmem pro hledání globálního minima. Tento algoritmus opakovaně generuje náhodné řešení z oblasti D, které si zapamatuje pouze v tom případě, ţe je toto řešení lepší, neţ řešení zaznamenané v předchozí historii algoritmu. Tato metoda prohledávání neobsahuje ţádnou strategii konstrukce řešení na základě předchozích řešení. Kaţdé řešení je tak nezávislé na předcházejícím řešení. Výstupním parametrem po ukončení procedury je to řešení, které během procedury poskytlo nejniţší funkční hodnotu. [9], [16], [19]

3.2.2

Metoda hladového prohledávání (Greedy search – GS)

Metoda hladového prohledávání je další metodou vhodnou pro řešení optimalizačních problémů. Hledání optimálního řešení se provádí tak, ţe se hledá lokální optimum dílčích podproblémů, přičemţ existuje šance, ţe se podaří nalézt optimum globální. Určení lokálního optima můţe vycházet z dříve nalezených optim, avšak nesmí se opírat o odhad řešení budoucích podproblémů. Metoda hladového prohledávání se uplatní tehdy, pokud je třeba z mnoţiny řešení vybrat takové, které splňuje předem dané poţadavky. [26], [28]


24



Metoda simulovaného žíhání (Simulated Annealing – SA)

Metoda simulovaného ţíhání patří mezi stochastické algoritmy, které vycházejí ze základů fyziky. Metoda simulovaného ţíhání vychází z analogie mezi ţíháním tuhých těles a procesem řešení optimalizačních problémů. Ţíhání označuje ve fyzice proces, při kterém je do pece vyhřáté na vysokou teplotu umístěné těleso a pomalým sniţováním teploty (ţíháním) dochází k zániku defektů krystalové mříţky. Částice tělesa jsou při vysoké teplotě náhodně uspořádány v prostoru (těleso je roztopené). Vysoká teplota zvyšuje pravděpodobnost zániku defektů krystalické mříţky, pomalé ochlazování sniţuje pravděpodobnost vzniku nových defektů. Při ţíhání se částice tělesa snaţí dostat do rovnováţné polohy (energie tělesa je minimální) – tj. krystal bez defektů. [12], [16]

3.2.4

Metoda zakázaného prohledávání (Tabu search – TS)

Metoda zakázaného prohledávání je upravenou verzí horolezeckého algoritmu. Ten funguje tak, ţe se na začátku optimalizace zvolí náhodné řešení z prostoru moţných řešení, pro které se generuje pomocí konečné mnoţiny transformací určité okolí a funkce se minimalizuje pouze v tomto okolí. Takto získané lokální řešení se pouţije jako střed nového okolí, ve kterém se lokální optimalizace opakuje. Počet lokálních optimalizací je předepsán. V průběhu procesu optimalizace se zaznamenává nejlepší řešení, které slouţí jako výsledné optimální řešení. Základní nevýhodou horolezeckého algoritmu je, ţe se po určitém počtu iterací vrací k lokálnímu optimálnímu řešení nalezenému v dřívějším průběhu a tím dochází k zacyklení. [16], [24] Metoda zakázaného prohledávání je doplněna o tzv. krátkodobou paměť, do které se ukládají inverzní transformace k lokálně optimálním transformačním řešením. Výsledkem je, ţe nedochází k zacyklení z důvodu zakázání transformací obsaţených v krátkodobé paměti. [16], [24]


25



Genetický algoritmus (Genetic algorithm – GA)

Genetický algoritmus vyuţívá principů evoluční biologie pro nalezení řešení sloţitých optimalizačních problémů. K tomu pouţívá techniky napodobující evoluční procesy (dědičnost, mutace, přirozený výběr a kříţení) pro „šlechtění“ řešení zadané úlohy. Princip genetického algoritmu spočívá v postupné tvorbě generací různých řešení zadaného problému, kde kaţdá generace obsahuje tzv. populaci, jejíţ kaţdý jedinec představuje jedno řešení problému. V první generaci je populace sloţena z náhodně vybraných členů. Při přechodu do další generace je pro všechny jedince vypočtena tzv. fitness funkce určující kvalitu řešení představované daným jedincem. Podle fitness funkce jsou poté vybráni jedinci, kteří jsou modifikováni kříţením a mutací. Tím vznikne nová, kvalitnější populace. Algoritmus se ukončí buď po předem dané době, nebo po dosaţení postačující kvality řešení. [16], [19], [27]


26

Diplomová práce

Simcron MODELLER

4 Simcron MODELLER Na trhu existuje celá řada simulačních systémů, které umoţňují vyuţití optimalizačních algoritmů (např. Witness, ARENA, SIMUL8 a další). V této práci byl k jednotlivým optimalizacím pouţit simulační systém Simcron MODELLER. Tato kapitola se proto zabývá pouţitými optimalizačními algoritmy, prioritními pravidly a účelovými funkcemi v tomto systému.

4.1 Optimalizační algoritmy U optimalizačních algoritmů je nutné nastavit mnoho parametrů daného algoritmu, jejichţ popis je uveden v nápovědě systému Simcron MODELLER. [31] Nastavené parametry jednotlivých algoritmů: Metoda náhodného prohledávání o rozteč prohledávacího kroku

50 %

Metoda hladového prohledávání o o o o

počet povolených chybných pokusů velikost kroku na začátku velikost kroku na konci velikost tabu listu

10 000 100 % 0% 10

Metoda simulovaného žíhání o o o o

počet povolených chybných pokusů počáteční teplota konečná teplota odstupňování teplot

250 100 0 10 000

Metoda zakázaného prohledávání o o o o

iterace rozteč prohledávacího kroku velikost tabu listu lokální prohledávací krok na iteraci

1 000 1 10 50

Genetický algoritmus o počet generací o velikost populace o typ výběru


400 200 Ruletové pravidlo

27

Diplomová práce

Simcron MODELLER

Většina těchto parametrů je v systému Simcron nastavena standardně, avšak aby optimalizace nekončila předčasně, bylo nutné některé parametry nastavit ručně. Konkrétně jde o počet povolených chybných pokusů v metodě hladového prohledávání, odstupňování teplot v metodě simulovaného ţíhání, iterace v metodě zakázaného prohledávání a počet generací a velikost populace u genetického algoritmu. Tyto parametry byly nastaveny tak, aby bylo prohledáno alespoň 10 000 moţných řešení.

4.2 Prioritní pravidla Řízení pomocí prioritních pravidel je důleţitým nástrojem pro řízení výrobních procesů. V praxi bývají prioritní pravidla často nasazována, aniţ by při tom musel být zřejmý jejich vědecký základ. Jedná se právě o zkušenosti, které se více méně v minulosti osvědčily. Prioritní pravidlo se stává účinným tehdy, pokud by se několik zakázek současně přesouvalo mezi jednotlivými stanovišti. Nastavené pravidlo pak rozhodne, v jakém pořadí se má transfer uskutečnit. Pokud jsou jednotlivá stanoviště přetíţena, vytvoří se fronta sestávající se z dočasně odstavených zakázek. [31] Podle toho, jaké prioritní pravidlo bylo nastaveno, jsou nově příchozí zakázky následně řazeny do fronty. V praxi se můţeme setkat s celou řadou prioritních pravidel, která jsou popsána např. v [15], [18]. Systém Simcron však vyuţívá pouze 14 následujících prioritních pravidel [31]: Inverzní – zařazení zakázky před všechny čekající zakázky (LIFO fronta – Last In First Out). Priorita – zařazení zakázky před všechny zakázky s menší prioritou a za všechny zakázky s prioritou větší nebo stejnou (pokud není hodnota priority v pracovním sledu uvedena, bude priorita ohodnocena). Priorita inverzní – zařazení zakázky za všechny zakázky s menší nebo stejnou prioritou a před všechny zakázky s prioritou větší (pokud není hodnota priority v pracovním sledu uvedena, bude priorita ohodnocena).


28

Diplomová práce

Simcron MODELLER

Nejdříve možný termín požadovaného dohotovení – zařazení zakázky za všechny zakázky s dřívějším nebo stejným termínem dokončení a před všechny zakázky s pozdějším termínem dokončení. Nejmenší diference mezi termínem dodání a zbývajícím časem práce – zařazení zakázky před všechny zakázky s menším nebo stejným skluzem a za všechny zakázky s větším skluzem. Nejkratší operační čas – zařazení zakázky za všechny zakázky s kratším nebo stejným operačním časem a před všechny zakázky s delším operačním časem. Nejkratší zbývající čas práce – zařazení zakázky za všechny zakázky s kratším nebo stejným zbývajícím časem práce a před všechny zakázky s delším zbývajícím časem práce (= suma výrobních časů na všech následujících strojích). Nejkratší celkový čas práce – zařazení zakázky za všechny zakázky s kratším nebo stejným celkovým časem práce a před všechny zakázky s delším celkovým časem práce (= suma výrobních časů na všech strojích). Nejméně zbývajících operací k provedení – zařazení zakázky za všechny zakázky s menším nebo stejným počtem zbývajících operací k provedení a před všechny zakázky s větším počtem zbývajících operací k provedení. Nejdelší operační čas – zařazení zakázky za všechny zakázky s delším nebo stejným operačním časem a před všechny zakázky s kratším operačním časem. Nejvyšší zbývající čas práce – zařazení zakázky za všechny zakázky s vyšším nebo stejným zbývajícím časem práce a před všechny zakázky s niţším zbývajícím časem práce (= suma výrobních časů na všech následujících strojích). Nejdelší celkový čas práce – zařazení zakázky za všechny zakázky s delším nebo stejným celkovým časem práce a před všechny zakázky s kratším celkovým časem práce (= suma výrobních časů na všech strojích). Nejvíce zbývajících operací k provedení – zařazení zakázky za všechny zakázky s větším nebo stejným počtem zbývajících operací k provedení a před všechny zakázky s menším počtem zbývajících operací k provedení. Normální – zařazení zakázky za všechny čekající zakázky (FIFO fronta – First In First Out).


29

Diplomová práce

Simcron MODELLER

4.3 Účelové funkce Účelové funkce slouţí jako měřítko, podle kterého můţeme hodnotit efektivitu procesu. V systému Simcron MODELLER lze vyuţít následujících objektů pro stanovení účelové funkce: [31]. 1. Dodrţení termínu 2. Průběţná doba 3. Vytíţení strojů 4. Obsazení strojů Průběţná doba – doba mezi přípravou, příp. prvním opracováním zakázky a jejím dokončením.

t1 – čas, kdy jsou k výrobě připraveny zakázky J1 a J4 t2 – čas, kdy jsou k výrobě připraveny zakázky J2 a J3 t1 – začátek obrábění zakázky J1 t5 – dokončení zakázky J1 t3 – začátek obrábění zakázky J2 t6 – dokončení zakázky J2 t4 – začátek obrábění zakázky J3 t8 – dokončení zakázky J3 t7 – začátek obrábění zakázky J4 t9 – dokončení zakázky J4 wjm – doba čekání zakázky Jj na stroji Mm (v tomto případě j = 1 – 4, m = 1 – 2) bjm – doba obrábění zakázky Jj na stroji Mj (v tomto případě j = 1 – 4, m = 1 – 2) Obr. 4.1: Ganttův diagram - průběžná doba výroby [31]


30

Diplomová práce

Simcron MODELLER

Celková průběţná doba výroby – doba mezi přípravou první ze sledovaných zakázek a dokončením poslední ze sledovaných zakázek. Např. zakázky J2 a J3, zobrazené v Ganttově diagramu na obr. 4.1, jsou připraveny v čase t2 a dokončení poslední zakázky nastane v čase t8. Celková průběţná doba výroby Tt zakázek J2 a J3 se pak vypočítá podle vztahu Tt = t8 – t2. Střední celková průběţná doba výroby – střední hodnota celkových průběţných dob výroby jednotlivých zakázek. Jako příklad opět poslouţí zakázky J2 a J3 z obr. 4.1. Celková průběţná doba výroby zakázky J2 se vypočítá ze vztahu T2 = t6 – t2, celková průběţná doba výroby zakázky J3 se vypočítá ze vztahu T3 = t8 – t2. Střední celková průběţná doba výroby se pak vypočítá podle vztahu Tm = (T2 + T3) / J, kde J je počet sledovaných zakázek (v tomto případě J = 2). Střední doba čekání – střední hodnota čekání jednotlivých zakázek. Doba čekání zakázky J2 se vypočítá podle vztahu W2 = w21 + w22, doba čekání zakázky J3 se vypočítá podle vztahu W3 = w31 + w32. Střední doba čekání se pak vypočítá podle vztahu Wm = (W2 + W3) / J, kde J je počet sledovaných zakázek (v tomto případě J = 2). Vytíţení strojů – poměr aktivně obsazené pracovní kapacity k dostupné výrobní kapacitě, anebo k celkové výrobní kapacitě strojů. V této práci jde o poměr aktivně obsazené pracovní kapacity k dostupné výrobní kapacitě. Zpoţdění - Časové rozpětí mezi posledním termínem dokončení zakázky a skutečným dokončením zakázky. V této práci byla pouţita účelová funkce „suma všech zpoţdění“, coţ je součet zpoţdění veškerých sledovaných zakázek.


31

Diplomová práce

Teoretické modely výroby

5 Teoretické modely výroby Jedním z cílů této diplomové práce je posouzení efektivnosti optimalizačních algoritmů. K tomu byly vyuţity teoretické modely výroby, coţ jsou příklady, jejichţ výsledek je předem známý (výsledkem se rozumí hodnota nejkratší celkové průběţné doby výroby – tzv. globální optimum), a proto slouţí k testování jednotlivých optimalizačních metod a jejich nastavení v optimalizačních systémech. Tato kapitola se zabývá modely výroby typu job shop. Tyto modely byly optimalizovány s vyuţitím pěti různých optimalizačních algoritmů (metoda náhodného prohledávání, metoda hladového prohledávání, metoda simulovaného ţíhání, metoda zakázaného prohledávání, genetický algoritmus) a dosaţené výsledky byly porovnány se známými optimy těchto modelů.

5.1 Optimalizace pomocí optimalizačních algoritmů Celkem byla provedena optimalizace u deseti různých teoretických modelů (ft06, ft10, ft20, la02, la19, la21, la27, la30, la40, sw11). Kaţdý model se liší v počtu strojů a v počtu zakázek, které se mají na všech strojích zpracovat. Kaţdý příklad byl optimalizován s vyuţitím všech pěti algoritmů, přičemţ optimalizace pomocí jednotlivých algoritmů proběhla vţdy pětkrát a nakonec byla vypočtena průměrná hodnota z těchto pěti dosaţených hodnot. Tato měření byla prováděna pro dva různé druhy rozvrhů: Rozvrh bez zpoţdění Aktivní rozvrh Celkem tedy bylo provedeno 500 měření (10 příkladů × 5 algoritmů × 2 rozvrhy × 5 měření kaţdého algoritmu). Jak jiţ bylo řečeno dříve, úlohy rozvrhování patří mezi kombinatorické problémy a počet moţných řešení je konečný. V úlohách typu job shop je to celkem (n!)m řešení („n“ odpovídá počtu zakázek, „m“ představuje počet pracovišť). [23] I kdyţ různá omezení (např. technologií) mnoţinu rozvrhů značně redukují, není moţné v přípustné době prohledat veškerá moţná řešení. Maximální počet prohledávaných iterací byl proto


32

Diplomová práce


nastaven na 10 000 a maximální doba optimalizace byla nastavena na 15 minut. Zaznamenávány byly následující údaje: výsledek optimalizace (minimální hodnota celkové průběţné doby výroby) doba optimalizace pořadí iterace, při které byl výsledek nalezen počet iterací (pokud nebylo prohledáno 10 000 řešení během 15 minut) 5.1.1

Zadání teoretických modelů

Zadání jednotlivých příkladů je uvedeno v tabulkách v Příloze I. Jednotlivé řádky ve zmíněných tabulkách představují jednotlivé zakázky a sloupce v těchto tabulkách udávají tok těchto zakázek mezi jednotlivými pracovišti, kdy kaţdý lichý sloupec označuje číslo stroje, na němţ je daná zakázka právě zpracovávána, a kaţdý sudý sloupec představuje dobu zpracování zakázky na daném stroji. Pokud je tedy v prvním řádku uvedeno např. 3 9 2 4…, tak to znamená, ţe zakázka č. 1 bude nejprve zpracovávána na stroji 3 po dobu devíti časových jednotek. Poté zakázka přejde ke stroji 2, kde bude zpracovávána 4 časové jednotky atd. V následující tabulce jsou uvedeny známé výsledky jednotlivých teoretických modelů výroby, se kterými jsou dále porovnávány výsledky optimalizace: Tab. 5.1: Známá optima teoretických modelů výroby Příklad ft06 ft10 ft20 la02 la19 la21 la27 la30 la40 sw11


počet zakázek 6 10 20 10 10 15 20 20 15 50

počet strojů 6 10 5 5 10 10 10 10 15 10

optimum [s] 55 930 1 165 655 842 1 046 1 235 1 355 1 222 2 983

33



Optimalizace teoretických modelů s využitím rozvrhu bez zpoždění

Teoretické modely výroby byly vytvořeny v systému Simcron MODELLER. Vyuţilo se přitom čtyř základních prvků systému Simcron – stroj, zásobník, zakázka a technologie, přičemţ počet strojů a zakázek je dán zadáním příkladu, počet technologií odpovídá počtu zakázek (kaţdá zakázka se vyrábí podle vlastní technologie) a počet zásobníků je dán počtem strojů, ke kterému je nutné připočítat dva zásobníky navíc (zásobník zakázek u kaţdého stroje plus zásobník vstupní a výstupní).

Na následujícím obrázku je ukázka simulačního modelu v systému Simcron MODELLER:

Obr. 5.1: Model příkladu ft06

Na obrázku je vidět 6 strojů (prvky označené M0 – M5), 8 zásobníků (prvky označené B0 – B5, vstup a vystup) a 6 pouţitých technologií (prvky označené tech1 – tech6). Šest zakázek, které nejsou na obrázku vidět, je jiţ zaplánováno, a proto má vstupní zásobník jinou barvu neţ zásobníky ostatní. Jedním z nejčastěji vyuţívaných prioritních pravidel v systémech ERP je prioritní pravidlo „nejkratší operační čas“. [7] Proto bylo provedeno nejprve řízení


34

Diplomová práce


zakázek teoretických modelů s vyuţitím tohoto pravidla. Výsledkem byla hodnota celkové průběţné doby výroby. Tyto výsledky jsou uvedeny v následující tabulce: Tab. 5.2: Dosažené výsledky při řízení zakázek prioritním pravidlem Příklad ft06 ft10 ft20 la02 la19

Výsledek [s] 88 1074 1267 821 940

doba simulace [s] 1 1 1 1 1

Příklad la21 la27 la30 la40 sw11

Výsledek [s] 1324 1784 1792 1476 3668


Po provedení optimalizace pomocí prioritního pravidla následovala optimalizace pomocí optimalizačních algoritmů, která probíhala na dvou různě výkonných počítačích, aby byl zjištěn vliv výkonu PC na dobu optimalizace. Méně výkonné PC:

Intel Pentium 4, 2 GHz, 512 MB RAM

Více výkonné PC:

Intel Core2Duo, 3 GHz, 3 GB RAM

Na méně výkonném PC byla provedena 2 měření, na více výkonném PC byla provedena 3 měření.

Naměřené hodnoty jsou uvedeny v Příloze II, v následujících tabulkách jsou uvedeny průměrné hodnoty naměřených hodnot. V jednotlivých sloupcích následujících deseti tabulek jsou uvedeny tyto údaje: 1. Průměrný výsledek optimalizace (z pěti měření) 2. Chyba vůči známému optimu 3. Zlepšení výsledku vůči výsledku prioritního pravidla 4. Průměrná doba optimalizace na méně výkonném PC (ze dvou měření) 5. Průměrná doba optimalizace na více výkonném PC (ze tří měření) 6. Průměrné pořadí iterace, při které byl nalezen výsledek 7. Průměrný počet prohledaných iterací – pouze u modelu sw11 (ze dvou měření)


35

Diplomová práce


Tab. 5.3: Průměrné hodnoty - model ft06 - rozvrh bez zpoždění Známé optimum [s]: 55 Použitý algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus

1. [s] 57 57 58 57 57

2. [%] 3,6 3,6 5,5 3,6 3,6

3. [%] 35,2 35,2 34,1 35,2 35,2

4. [mm:ss] 04:40 05:41 06:04 04:59 05:00

5. [mm:ss] 01:22 01:38 01:49 01:22 01:26

6. [-] 3261 820 3053 1092 244

5. [mm:ss] 01:54 02:24 02:13 01:57 02:25

6. [-] 5673 7175 6911 3065 6633

5. [mm:ss] 02:18 02:53 02:34 02:21 03:04

6. [-] 3995 9120 7857 4047 7224

5. [mm:ss] 01:33 01:55 01:53 01:34 01:58

6. [-] 5370 5678 6307 2689 6619

Tab. 5.4: Průměrné hodnoty - model ft10 - rozvrh bez zpoždění Známé optimum [s]: 930 Použitý algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus

1. [s] 1012 980 1013 998 984

2. [%] 8,8 5,4 8,9 7,3 5,8

3. [%] 5,8 8,7 5,7 7,1 8,4

4. [mm:ss] 07:01 08:21 07:34 07:07 08:20

Tab. 5.5: Průměrné hodnoty - model ft20 - rozvrh bez zpoždění Známé optimum [s]: 1 165 Použitý algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus

1. [s] 1240 1195 1231 1236 1196

2. [%] 6,4 2,5 5,6 6,1 2,7

3. [%] 2,2 5,7 2,9 2,5 5,6

4. [mm:ss] 08:31 10:17 09:18 08:42 11:04

Tab. 5.6: Průměrné hodnoty - model la02 - rozvrh bez zpoždění Známé optimum [s]: 655 Použitý algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus


1. [s] 700 679 696 690 680

2. [%] 6,9 3,6 6,3 5,4 3,8

3. [%] 14,7 17,3 15,2 15,9 17,2

4. [mm:ss] 06:08 07:22 06:26 05:43 06:46

36

Diplomová práce


Tab. 5.7: Průměrné hodnoty - model la19 - rozvrh bez zpoždění Známé optimum [s]: 842 Použitý algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus

1. [s] 875 875 878 876 875

2. [%] 4,0 4,0 4,3 4,0 3,9

3. [%] 6,9 6,9 6,6 6,9 6,9

4. [mm:ss] 06:53 08:31 08:13 07:33 08:24

5. [mm:ss] 01:54 02:24 02:13 01:57 02:22

6. [-] 5558 2254 7217 4271 4847

5. [mm:ss] 02:27 03:08 02:38 02:31 03:05

6. [-] 4985 9067 8553 3964 7616

5. [mm:ss] 03:26 03:59 03:11 03:10 03:52

6. [-] 4671 9454 8477 6794 8043

5. [mm:ss] 03:13 03:59 03:12 03:09 03:51

6. [-] 5784 9457 6936 3878 7115

Tab. 5.8: Průměrné hodnoty - model la21 - rozvrh bez zpoždění Známé optimum [s]: 1 046 Použitý algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus

1. [s] 1153 1117 1146 1131 1118

2. [%] 10,2 6,8 9,6 8,2 6,9

3. [%] 12,9 15,6 13,4 14,5 15,6

4. [mm:ss] 08:39 11:13 09:13 09:11 10:51


1. [s] 1395 1337 1372 1356 1337

2. [%] 13,0 8,2 11,1 9,8 8,3

3. [%] 21,8 25,1 23,1 24,0 25,1

4. [mm:ss] 11:04 14:20 11:20 11:23 13:20



1. [s] 1456 1417 1441 1412 1402

2. [%] 7,4 4,6 6,3 4,2 3,5

3. [%] 18,8 20,9 19,6 21,2 21,8

4. [mm:ss] 11:03 14:19 11:26 11:35 13:47

37

Diplomová práce



1. [s] 1333 1303 1335 1313 1302

2. [%] 9,1 6,6 9,2 7,4 6,6

3. [%] 9,7 11,7 9,6 11,1 11,8

4. [mm:ss] 11:04 14:27 11:19 11:30 13:22

5. [mm:ss] 03:07 04:02 03:15 03:11 03:54

6. [-] 6039 8389 6727 4332 7104

Tab. 5.12: Průměrné hodnoty - model sw11 - rozvrh bez zpoždění Známé optimum [s]: 2 983 Použitý algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus

1. [s] 3531 3570 3487 3435 3499

2. [%] 18,4 19,7 16,9 15,2 17,3

3. [%] 3,7 2,7 4,9 6,3 4,6

4. [mm:ss] 15:00 15:00 15:00 15:00 15:00

5. [mm:ss] 08:43 11:32 08:27 09:02 11:27

6. [-] 4254 6737 4925 3137 6364

7. [-] 4856 3182 4828 4867 3791

Při pohledu na uvedené výsledky jsou patrné rozdíly mezi pouţitými metodami optimalizace (prioritní pravidlo vs. optimalizační algoritmy). Optimalizační algoritmy poskytnou sice přesnější výsledek neţli pouţité prioritní pravidlo, avšak za mnohem delší dobu. U optimalizačních algoritmů je navíc důleţitý výkon PC, zatímco u prioritního pravidla nebyl vliv výkonu PC pozorován. Nejvíce je tento jev patrný na příkladu

sw11,

čili

na

nejnáročnějším

příkladu.

Optimalizace

s vyuţitím

optimalizačních algoritmů trvala na méně výkonném počítači přesně 15 minut (coţ byla maximální povolená doba optimalizace), a i přesto nebylo prohledáno maximální mnoţství řešení (10 000).

5.1.3

Optimalizace teoretických modelů s využitím aktivního rozvrhu

Aby bylo moţné teoretické modely optimalizovat podle aktivního rozvrhu, bylo nutné je nejprve na aktivní rozvrh převést. K tomu byly vyuţity modely vytvořené pro rozvrh bez zpoţdění, do kterých byl nahrán skript „aktivní plán“ poskytnutý výrobcem systému Simcron. Tento skript ovšem obsahuje určitá zjednodušení, kvůli kterým nejsou pokryty veškeré aktivní rozvrhy, a tak neposkytuje všechna moţná řešení.


38

Diplomová práce


Optimalizace probíhala stejně jako v předchozí části (optimalizace s vyuţitím rozvrhu bez zpoţdění). Tzn. nejdříve řízení zakázek podle prioritního pravidla, poté pět měření pomocí optimalizačních algoritmů. Všech těchto pět měření proběhlo na výkonnějším PC. Tab. 5.13: Dosažené výsledky při řízení zakázek prioritním pravidlem Příklad ft06 ft10 ft20 la02 la19

Výsledek [s] 91 1305 1771 935 1203


Příklad la21 la27 la30 la40 sw11

Výsledek [s] 1600 1981 2069 1679 4565


Naměřené hodnoty pomocí optimalizačních algoritmů jsou uvedeny v Příloze III, v následujících tabulkách jsou uvedeny průměrné hodnoty naměřených hodnot. V jednotlivých sloupcích následujících deseti tabulek jsou uvedeny tyto údaje: 1. Průměrný výsledek optimalizace 2. Chyba vůči známému optimu 3. Zlepšení výsledku vůči výsledku prioritního pravidla 4. Průměrná doba optimalizace 5. Průměrné pořadí iterace, při které byl nalezen výsledek Tab. 5.14: Průměrné hodnoty - model ft06 - aktivní rozvrh Známé optimum [s]: 55 Použitý algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus


1. [s] 60 57 61 59 59

2. [%] 8,4 4,4 10,9 6,5 6,5

3. [%] 34,5 36,9 33,0 35,6 35,6

4. [mm:ss] 00:57 01:05 00:55 01:07 01:07

5. [-] 4526 3629 3178 4629 4518

39

Diplomová práce


Tab. 5.15: Průměrné hodnoty - model ft10 - aktivní rozvrh Známé optimum [s]: 930 Použitý algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus

1. [s] 1157 1086 1152 1149 1063

2. [%] 24,4 16,7 23,9 23,6 14,3

3. [%] 11,4 16,8 11,7 11,9 18,5

4. [mm:ss] 02:06 02:37 02:21 02:15 03:25

5. [-] 5894 9497 8321 5595 8354

3. [%] 21,3 23,2 22,1 20,9 24,0

4. [mm:ss] 02:33 03:04 02:42 02:30 03:09

5. [-] 3784 9303 5285 2923 8203

3. [%] 20,8 24,5 20,6 21,0 24,8

4. [mm:ss] 01:42 02:04 01:55 01:44 02:09

5. [-] 5334 8490 8662 4307 8065

3. [%] 16,4 21,0 16,8 18,6 21,9

4. [mm:ss] 02:07 02:35 02:21 02:14 02:43

5. [-] 7472 9481 6262 4272 7496

Tab. 5.16: Průměrné hodnoty - model ft20 - aktivní rozvrh Známé optimum [s]: 1 165 Použitý algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus

1. [s] 1395 1360 1380 1400 1346

2. [%] 19,7 16,8 18,5 20,2 15,5

Tab. 5.17: Průměrné hodnoty - model la02 - aktivní rozvrh Známé optimum [s]: 655 Použitý algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus

1. [s] 740 706 742 739 703

2. [%] 13,0 7,8 13,3 12,8 7,4

Tab. 5.18: Průměrné hodnoty - model la19 - aktivní rozvrh Známé optimum [s]: 842 Použitý algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus


1. [s] 1006 950 1001 979 940

2. [%] 19,4 12,8 18,9 16,2 11,6

40

Diplomová práce


Tab. 5.19: Průměrné hodnoty - model la21 - aktivní rozvrh Známé optimum [s]: 1 046 Použitý algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus

1. [s] 1367 1308 1356 1327 1301

2. [%] 30,7 25,0 29,7 26,9 24,4

3. [%] 14,6 18,3 15,2 17,1 18,7

4. [mm:ss] 02:57 03:20 02:53 02:48 03:24

5. [-] 3127 9524 6616 3445 7532

3. [%] 14,7 18,2 14,8 17,5 20,2

4. [mm:ss] 03:28 04:28 03:47 03:27 04:21

5. [-] 5860 9424 7123 4613 8280

3. [%] 16,6 19,9 16,5 19,6 21,2

4. [mm:ss] 03:28 04:27 03:42 03:28 04:09

5. [-] 3718 9759 5058 6178 8058

3. [%] 4,0 9,4 6,5 8,1 11,9

4. [mm:ss] 03:37 04:19 03:34 03:40 04:14

5. [-] 5303 8913 7963 4823 8591


1. [s] 1690 1621 1688 1634 1580

2. [%] 36,8 31,3 36,7 32,3 27,9


1. [s] 1725 1658 1728 1663 1630

2. [%] 27,3 22,4 27,5 22,7 20,3



1. [s] 1612 1522 1570 1543 1479

2. [%] 31,9 24,5 28,5 26,3 21,0

41

Diplomová práce


Tab. 5.23: Průměrné hodnoty - model sw11 - aktivní rozvrh Známé optimum [s]: 2 983 Použitý algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus

1. [s] 4075 4238 4054 4081 4141

2. [%] 36,6 42,1 35,9 36,8 38,8

3. [%] 10,7 7,2 11,2 10,6 9,3

4. [mm:ss] 09:14 11:17 09:12 08:59 12:23

5. [-] 2140 8426 4935 3843 9217

U optimalizace aktivního rozvrhu teoretických modelů se opět projevily rozdíly mezi jednotlivými druhy optimalizace. Na straně jedné jsou výsledky přesnější, ovšem za cenu delší doby optimalizace (optimalizační algoritmy), na straně druhé jsou výsledky méně uspokojivé, avšak k dispozici během několika mála okamţiků (prioritní pravidla).

5.2 Zhodnocení dosažených výsledků V Tab. 5.25 jsou bodově ohodnoceny jednotlivé optimalizační algoritmy, u kterých se bodovaly tři parametry: 1. chyba výsledku vůči optimu 2. doba optimalizace 3. pořadí iterace, při které byl nalezen výsledek Bodovány byly průměrné hodnoty naměřených hodnot. Bodování bylo následující: Tab. 5.24: Bodování optimalizačních algoritmů počet bodů 5 bodů 4 body 3 body 2 body 1 bod

chyba vůči optimu [%] 0–5 5,1 – 10 10,1 – 15 15,1 – 20 20,1 a více


doba optimalizace [mm:ss] 0:00 – 3:00 3:01 – 6:00 6:01 – 9:00 9:01 – 12:00 12:01 – 15:00

pořadí iterace [-] 0. – 2 000. 2 001. – 4 000. 4 001. – 6 000. 6 001. – 8 000. 8 001. – 10 000.

42

Diplomová práce


Jednotlivé parametry měly různou váhu: 1. chyba výsledku vůči optimu: 60 % 2. doba optimalizace:

30 %

3. pořadí iterace:

10 %

Celkovým maximem je 100 bodů.

pořadí iterace aktivní bez zpožď.

doba optimalizace aktivní bez zpožď.

chyba výsledku aktivní bez zpožď.

Tab. 5.25: Počet dosažených bodů Algoritmus náhodné proh. hladové proh. simulované žíh. zakázané proh. genetický alg. náhodné proh. hladové proh. simulované žíh. zakázané proh. genetický alg. náhodné proh. hladové proh. simulované žíh. zakázané proh. genetický alg. náhodné proh. hladové proh. simulované žíh. zakázané proh. genetický alg. náhodné proh. hladové proh. simulované žíh. zakázané proh. genetický alg. náhodné proh. hladové proh. simulované žíh. zakázané proh. genetický alg.

ft06 5 5 4 5 5 4 4 3 4 4 5 5 5 5 5 5 5 5 5 5 4 5 4 5 5 3 4 4 3 3


ft10 4 4 4 4 4 1 2 1 1 3 5 5 5 5 5 5 5 5 5 4 3 2 2 4 2 3 1 1 3 1

ft20 4 5 4 4 5 2 2 2 1 2 5 5 5 5 4 5 4 5 5 4 4 1 2 3 2 4 1 3 4 1

la02 4 5 4 4 5 3 4 3 3 4 5 5 5 5 5 5 5 5 5 5 3 3 2 4 2 3 1 1 3 1

la19 5 5 5 5 5 2 3 2 2 3 5 5 5 5 5 5 5 5 5 5 3 4 2 3 3 2 1 2 3 2

la21 3 4 4 4 4 1 1 1 1 1 5 4 5 5 4 5 4 5 5 4 3 1 1 4 2 4 1 2 4 2

la27 3 4 3 4 4 1 1 1 1 1 4 4 4 4 4 4 4 4 4 4 3 1 1 2 1 3 1 2 3 1

la30 4 5 4 5 5 1 1 1 1 1 4 4 4 4 4 4 4 4 4 4 3 1 2 4 2 4 1 3 2 1

la40 4 4 4 4 4 1 1 1 1 1 4 4 4 4 4 4 4 4 4 4 2 1 2 3 2 3 1 2 3 1

sw11 2 2 2 2 2 1 1 1 1 1 3 2 3 2 2 2 2 2 3 1 3 2 3 4 2 4 1 3 4 1

43

Diplomová práce


Tab. 5.26: Celkový počet dosažených bodů Algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus

Body celkem 60% 30% 10% 55 89 64 63 85 34 54 89 44 57 89 68 64 82 37

přepočet podle váhy 33,0 26,7 6,4 37,8 25,5 3,4 32,4 26,7 4,4 34,2 26,7 6,8 38,4 24,6 3,7

výsledek 66,1 66,7 63,5 67,7 66,7

Podle uvedeného bodování se nejlepší metodou stala metoda zakázaného prohledávání se ziskem 67,7 bodů ze 100 a naopak nejhorší metodou se stala metoda simulovaného ţíhání se ziskem 63,5 bodů. Ačkoliv nejvyššího počtu bodů dosáhla metoda zakázaného prohledávání, tak bych jako vítěze označil genetický algoritmus, který ztratil body především kvůli nejméně důleţitému parametru (pořadí iterace, při které byl nalezen výsledek), na kterém naopak metoda zakázaného prohledávání nejvíce „vydělala“.


44

Diplomová práce

Model lisovny

6 Model lisovny Tento příklad je modelem dílny, ve které je 22 strojů (lisů). Tyto stroje obsluhuje dohromady 10 lidí (3 seřizovači lisů a 7 pracovníků obsluhy lisů), jejichţ úkolem je co nejefektivněji zpracovat všechny zakázky. Kaţdá zakázka se vyrábí vţdy na jednom stroji. Seřizovači lisů musí nastavit kaţdý stroj k práci před kaţdou zakázkou, pracovníci obsluhy lisů zajišťují plynulý chod práce na strojích. Tito pracovníci obsluhují v jednu chvíli vţdy pouze jeden stroj – není tedy moţné zahájit práci na jednom stroji a mezitím jít pracovat ke stroji druhému. Cílem modelu lisovny je zoptimalizovat zpracovávání jednotlivých zakázek tak, aby výroba probíhala co nejefektivněji podle poţadované účelové funkce. K optimalizaci pracovního cyklu byl pouţit model lisovny, který byl vytvořen v systému Simcron. Optimalizace probíhala dvěma způsoby: 1. Řízení zakázek pomocí prioritních pravidel 2. Optimalizace pomocí optimalizačních algoritmů

6.1 Řízení zakázek pomocí prioritních pravidel Řízení zakázek pomocí prioritních pravidel je nejrychlejší optimalizační metodou v systému Simcron, jelikoţ optimalizace proběhne vţdy během jedné vteřiny a výsledky jsou tak k dispozici téměř okamţitě (k celkové době simulace je třeba ještě přičíst dobu nastavení daného prioritního pravidla, coţ je přibliţně 10 sekund – změřeno pomocí stopek). Při řízení zakázek pomocí prioritních pravidel v systému Simcron je výsledkem optimalizace hodnota účelové funkce, kterých lze v systému Simcron nastavit mnoho, avšak v tomto příkladě (model lisovny) bylo pouţito pouze pěti z nich (celková průběţná doba výroby, střední celková průběţná doba výroby, střední doba čekání, suma všech zpoţdění, vytíţení strojů). 6.1.1

Naměřené hodnoty

Řízení modelu lisovny pomocí prioritních pravidel předcházela simulace modelu bez pouţití prioritních pravidel (pořadí zakázek pocházelo z IS řízení výroby). Tím byl získán výsledek neoptimalizovaného modelu. Po této simulaci se prováděly


45

Diplomová práce

Model lisovny

optimalizace s vyuţitím jednotlivých prioritních pravidel, přičemţ byly zaznamenány výsledky všech pěti sledovaných účelových funkcí.

V následující tabulce jsou uvedeny tyto údaje: 1. výsledek účelové funkce „celková průběţná doba výroby“ 2. výsledek účelové funkce „střední celková průběţná doba výroby“ 3. výsledek účelové funkce „střední doba čekání“ 4. výsledek účelové funkce „suma všech zpoţdění“ 5. výsledek účelové funkce „vytíţení strojů“ 6. doba optimalizace

Tab. 6.1: Výsledky účelových funkcí při řízení prioritními pravidly Prioritní pravidla bez pravidla Inverzní Priorita Priorita inverzní Nejdříve možný termín požadovaného dohotovení Nejmenší diference mezi termínem dodání a zbývajícím časem práce Nejkratší operační čas Nejkratší zbývající čas práce Nejkratší celkový čas práce Nejméně zbývajících operací k provedení Nejdelší operační čas Nejvyšší zbývající čas práce Nejdelší celkový čas práce Nejvíce zbývajících operací k provedení Normální


1. [d:h:mm:ss] 6:15:42:06 8:00:48:09 6:15:42:06 6:15:42:06

Účelové funkce 2. 3. [d:h:mm:ss] [d:h:mm:ss] 2:10:17:33 0:21:31:53 2:10:19:00 0:21:43:33 2:10:17:33 0:21:31:53 2:10:17:33 0:21:31:53

4. [d:h:mm:ss] 10:22:29:12 33:08:43:29 10:22:29:12 10:22:29:12

5. [%] 41,6 34,2 41,6 41,6

6. [s] 1 1 1 1

6:15:42:06

2:10:17:33

0:21:31:53

10:22:29:12

41,6

1

8:22:23:09

2:14:47:35

1:02:12:07

17:13:09:34

30,6

1

6:15:42:06

2:10:17:33

0:21:31:53

10:22:29:12

41,6

1

7:11:20:08

2:03:18:12

0:14:32:31

15:21:58:34

36,9

1

7:11:20:08

2:03:18:12

0:14:32:31

15:21:58:34

36,9

1

6:15:42:06

2:09:41:19

0:20:55:38

10:04:02:36

41,6

1

6:15:42:06

2:10:17:33

0:21:31:53

10:22:29:12

41,6

1

8:18:23:09

2:17:59:21

1:05:23:53

30:21:15:00

31,2

1

8:18:23:09

2:17:59:21

1:05:23:53

30:21:15:00

31,2

1

6:21:45:20

2:15:00:13

1:02:04:20

18:19:35:23

39,9

1

6:15:42:06

2:10:17:33

0:21:31:53

10:22:29:12

41,6

1

46


Model lisovny

Zhodnocení dosažených výsledků

V tab. 6.1 jsou zelenou barvou označeny výsledky, které byly řízením pomocí prioritních pravidel zlepšeny, červenou barvou jsou označeny výsledky, které byly naopak zhoršeny. Nezvýrazněné výsledky jsou shodné s výsledkem bez vyuţití prioritního pravidla. Z výsledků je patrné, ţe řízením pomocí různých prioritních pravidel lze dosáhnout určitých zlepšení výsledků, nicméně nevhodně zvolené pravidlo můţe mít za následek i výrazné zhoršení výsledků. Pokud přehlédneme pravidla, u kterých nedošlo ani u jedné ze sledovaných účelových funkcí ke změně výsledku, tak pouze u jediného pravidla nedošlo u ţádné účelové funkce ke zhoršení výsledku – nejméně zbývajících operací k provedení – a tím se toto pravidlo stává pomyslným vítězem této části měření. Naproti tomu u pěti prioritních pravidel došlo ke zhoršení výsledků všech sledovaných účelových funkcí. Prioritní pravidla tak určitě mají své opodstatnění, nicméně je nutné tyto pravidla volit s rozvahou a určitým povědomím o moţnostech, které nabízejí.

6.2 Optimalizace pomocí optimalizačních algoritmů – část 1. Optimalizace modelu lisovny pomocí optimalizačních algoritmů probíhala stejným způsobem jako optimalizace teoretických modelů výroby (pět měření pomocí kaţdého algoritmu) s tím rozdílem, ţe oproti teoretickým modelům výroby byly u modelu lisovny sledovány výsledky pěti účelových funkcí (celková průběţná doba výroby, střední celková průběţná doba výroby, střední doba čekání, suma všech zpoţdění, vytíţení strojů).


47


Model lisovny

Naměřené hodnoty

Naměřené hodnoty jsou uvedeny v Příloze IV. V následujících tabulkách jsou uvedeny průměrné hodnoty naměřených hodnot a v jednotlivých sloupcích jsou uvedeny tyto údaje: 1. Průměrný výsledek optimalizace 2. Průměrná doba optimalizace 3. Průměrné pořadí iterace, při které byl nalezen výsledek 4. Zlepšení vůči neoptimalizovanému modelu Tab. 6.2: Průměrné hodnoty - celková průběžná doba výroby Výsledek neoptimalizovaného modelu [d:hh:mm:ss]: 6:15:42:06 Použitý algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus

1. [d:hh:mm:ss] 6:13:15:46 6:13:15:46 6:13:15:46 6:13:15:46 6:13:15:46

2. [mm:ss] 05:28 05:47 05:46 05:18 06:36

3. [-] 72 23 88 131 55

4. [%] 1,5 1,5 1,5 1,5 1,5

Tab. 6.3: Průměrné hodnoty - střední celková průběžná doba výroby Výsledek neoptimalizovaného modelu [d:hh:mm:ss]: 2:10:17:33 Použitý algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus

1. [d:hh:mm:ss] 2:01:34:38 1:23:28:49 1:23:10:49 1:23:28:05 2:00:28:18

2. [mm:ss] 05:30 05:45 05:28 05:16 07:05

3. [-] 5 725 9 596 8 018 5 196 8 318

4. [%] 15,0 18,5 19,1 18,6 16,8

3. [-] 4 312 9 685 6 251 8 586 8 105

4. [%] 39,0 48,6 49,7 48,5 43,2

Tab. 6.4: Průměrné hodnoty - střední doba čekání Výsledek neoptimalizovaného modelu [hh:mm:ss]: 21:31:53 Použitý algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus


1. [hh:mm:ss] 13:07:27 11:04:21 10:50:22 11:05:19 12:13:23

2. [mm:ss] 05:31 05:45 05:28 05:13 07:03

48

Diplomová práce

Model lisovny

Tab. 6.5: Průměrné hodnoty - suma všech zpoždění Výsledek neoptimalizovaného modelu [d:hh:mm:ss]: 10:22:29:12 Použitý algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus

1. [d:hh:mm:ss] 10:20:30:20 8:22:10:58 8:19:11:31 8:22:09:46 9:15:20:17

2. [mm:ss] 05:28 05:26 04:57 04:35 07:01

3. [-] 1 719 9 791 6 071 5 725 8 144

4. [%] 0,8 18,4 19,5 18,4 11,9

Tab. 6.6: Průměrné hodnoty - vytížení strojů Výsledek neoptimalizovaného modelu: 41,56 % Použitý algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus

6.2.2

1. [s] 42,38 42,47 42,38 42,46 42,39

2. [mm:ss] 05:30 05:59 05:58 05:42 07:01

3. [-] 7 432 9 603 5 914 4 376 7 537

4. [%] 1,97 2,19 1,96 2,18 1,99


V tab. 6.8 jsou bodově ohodnoceny jednotlivé optimalizační algoritmy. Bodovány byly dva stejné parametry, jako u teoretických modelů výroby a jeden jiný: 1. zlepšení vůči neoptimalizovanému modelu 2. doba simulace 3. pořadí iterace, při které byl nalezen výsledek Bodování je u druhého a třetího parametru shodné s bodováním teoretických modelů výroby, u prvního parametru je bodování následující: Tab. 6.7: Bodování optimalizačních algoritmů počet bodů 1 bod 2 body 3 body 4 body 5 bodů

zlepšení [%] 0–5 5,1 – 10 10,1 – 15 15,1 – 20 20,1 a více


Váha jednotlivých parametrů je shodná s váhou u teoretických modelů výroby (60:30:10). Maximální počet dosaţených bodů je v tomto případě 25.

49

Diplomová práce

Model lisovny

Ve sloupcích A – E následující tabulky jsou uvedeny účelové funkce, jeţ byly jednotlivými optimalizačními algoritmy optimalizovány: A. Celková průběţná doba výroby B. Střední celková průběţná doba výroby C. Střední doba čekání D. Suma všech zpoţdění E. Vytíţení strojů

pořadí iterace

doba optimalizace

zlepšení

Tab. 6.8: Počet dosažených bodů Algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus

A 1 1 1 1 1 4 4 4 4 3 5 5 5 5 5

B 3 4 4 4 4 4 4 4 4 3 3 1 1 3 1

C 5 5 5 5 5 4 4 4 4 3 3 1 2 1 1

D 1 4 4 4 3 4 4 4 4 3 5 1 2 3 1

E 1 1 1 1 1 4 4 4 4 3 2 1 3 3 2

Tab. 6.9: Celkový počet dosažených bodů Algoritmus Metoda náhodného prohledávání Metoda hladového prohledávání Metoda simulovaného žíhání Metoda zakázaného prohledávání Genetický algoritmus

Body celkem 60% 30% 10% 11 20 18 15 20 9 15 20 13 15 20 15 14 15 10

přepočet podle váhy 6,6 6,0 1,8 9,0 6,0 0,9 9,0 6,0 1,3 9,0 6,0 1,5 8,4 4,5 1,0

výsledek 14,4 15,9 16,3 16,5 13,9

Podle uvedeného bodování se nejlepší metodou stala metoda zakázaného prohledávání. Z maximálního dosaţitelného počtu bodů (25) získala 16,5 bodu. Naopak nejhoršího výsledku dosáhl genetický algoritmus se ziskem 13,9 bodů.


50

Diplomová práce

Model lisovny

6.3 Optimalizace pomocí optimalizačních algoritmů – část 2. Cílem tohoto měření bylo poukázat na jednu z nevýhod optimalizačních algoritmů – optimalizace můţe poskytnout několik stejných výsledků (nejlepších řešení), avšak aţ na obsluze je výběr toho správného ze všech správných výsledků. Pro dokázání této nevýhody bylo nutné sledovat výsledky všech pouţitých účelových funkcí současně (tzn., ţe při optimalizaci podle jedné účelové funkce měly ostatní účelové funkce také nějaký výsledek, který byl zaznamenán). Dohromady byl model lisovny optimalizován podle tří zvolených účelových funkcí: 1. střední celková průběţná doba výroby 2. suma všech zpoţdění 3. celková průběţná doba výroby Pro tuto část práce byla zvolena metoda zakázaného prohledávání, jelikoţ v předešlém měření poskytla nejlepší výsledky.

6.3.1

Naměřené hodnoty

Naměřené hodnoty jsou uvedeny v následujících tabulkách a v jednotlivých sloupcích jsou uvedeny tyto údaje (tučně zvýrazněny jsou výsledky té funkce, podle které bylo zrovna optimalizováno): 1. výsledek účelové funkce „celková průběţná doba výroby“ 2. výsledek účelové funkce „střední celková průběţná doba výroby“ 3. výsledek účelové funkce „střední doba čekání“ 4. výsledek účelové funkce „suma všech zpoţdění“ 5. výsledek účelové funkce „vytíţení strojů“ Tab. 6.10: Výsledky optimalizace podle střední celkové průběžné doby výroby Měření

1. [d:hh:mm:ss]

2. [d:hh:mm:ss]

3. [d:hh:mm:ss]

4. [d:hh:mm:ss]

5. [%]

1. 2. 3. 4. 5.

8:01:38:08 8:15:12:56 7:23:38:08 8:01:38:08 8:13:12:56

1:23:21:15 1:23:25:06 1:23:28:48 1:23:38:32 1:23:42:05

0:10:56:00 0:10:59:51 0:11:03:33 0:11:13:17 0:11:16:50

14:04:56:57 13:05:21:24 12:17:18:18 14:00:48:34 13:08:34:19

34,0 31,7 34,4 34,0 32,0


51

Diplomová práce

Model lisovny

Tab. 6.11: Výsledky optimalizace podle sumy všech zpoždění Měření

1. [d:hh:mm:ss]

2. [d:hh:mm:ss]

3. [d:hh:mm:ss]

4. [d:hh:mm:ss]

5. [%]

1. 2. 3. 4. 5.

6:13:15:46 6:13:15:46 6:13:15:46 6:13:15:46 6:13:15:46

2:07:34:55 2:06:40:13 2:07:34:46 2:07:21:30 2:05:57:41

0:18:39:02 0:17:54:32 0:18:38:52 0:18:15:24 0:17:01:48

8:19:11:27 8:22:34:01 8:21:44:47 8:20:34:01 8:22:34:01

42,3 42,3 42,3 42,3 42,3

Tab. 6.12: Výsledky optimalizace podle celkové průběžné doby výroby Měření

1. [d:hh:mm:ss]

2. [d:hh:mm:ss]

3. [d:hh:mm:ss]

4. [d:hh:mm:ss]

5. [%]

1. 2. 3. 4. 5.

6:13:15:46 6:13:15:46 6:13:15:46 6:13:15:46 6:13:15:46

2:09:13:02 2:08:47:01 2:12:04:01 2:13:19:09 2:12:22:55

0:20:27:22 0:20:01:21 0:23:08:08 1:00:13:03 0:23:27:02

13:04:34:52 11:00:19:31 15:15:18:12 11:13:06:02 10:09:46:11

42,3 42,3 42,3 42,3 42,3

Nevýhoda zmiňovaná v úvodu tohoto měření je patrná z tab. 6.12. Optimalizací podle celkové průběţné doby výroby bylo dosaţeno ve všech pěti pokusech stejného výsledku této účelové funkce, avšak ostatní účelové funkce mají výsledek pokaţdé jiný. Je proto nutné ze všech pěti správných řešení vybrat to „nejsprávnější“. Zároveň je tato nevýhoda zřejmá z následujících dvou obrázků (Obr. 6.1, Obr. 6.2), na kterých jsou znázorněny Ganttovy diagramy měření dva a čtyři, zaznamenané při optimalizaci podle celkové průběţné doby výroby. Tyto diagramy znázorňují vyuţití jednotlivých pracovišť během pracovního cyklu. Vodorovná osa znázorňuje celkovou průběţnou dobu jednoho pracovního cyklu, svislá osa znázorňuje jednotlivá pracoviště. Na obou obrázcích můţeme pozorovat stejný termín dokončení pracovního cyklu, avšak obsazení strojů a čekání na jednotlivých pracovištích je různé.


52

Diplomová práce

Model lisovny

Obr. 6.1: Využití pracovišť 12 – 22 Nejvíce zřetelným rozdílem na tomto obrázku je vyuţití pracoviště 22.


53

Diplomová práce

Model lisovny

Obr. 6.2: Využití pracovišť 1 – 11 Na tomto obrázku je nejviditelnějším rozdílem čekání na pracovišti 4. Vysvětlivky k Obr. 6.1 a Obr. 6.2: stroj pracuje stroj čeká

seřízení stroje neobsazená kapacita

Během měření se projevila i další nevýhoda optimalizačních algoritmů. Při optimalizaci podle střední celkové průběţné doby výroby a podle sumy všech zpoţdění vyšel v kaţdém měření jiný výsledek dané účelové funkce. Z toho je zřejmé, ţe optimalizační algoritmy nemusí vţdy poskytnout nejlepší moţné řešení.


54


Model lisovny


K hodnocení výsledků optimalizace podle různých účelových funkcí pouţijeme tabulku průměrných hodnot naměřených výsledků:

Tab. 6.13: Průměrné hodnoty při optimalizaci podle různých účelových funkcí Sledované Optimalizofunkce váno podle neoptimal. model stř. celková průb. doba suma všech zpoždění celková průb. doba

celková průb. doba [d:hh:mm:ss] 6:15:42:06

stř. celková průb. doba [d:hh:mm:ss] 2:10:17:33

střední doba čekání [d:hh:mm:ss] 0:21:31:53

suma všech zpoždění [d:hh:mm:ss] 10:22:29:12

vytížení strojů [%] 41,6

8:06:16:03 6:13:15:46 6:13:15:46

1:23:31:09 2:07:01:49 2:11:09:14

0:11:05:54 0:18:05:56 0:22:15:23

13:12:11:54 8:21:52:59 12:08:36:58

33,2 42,3 42,3

Zelenou barvou jsou v tabulce uvedeny hodnoty zlepšené vůči neoptimalizovanému modelu (6.1.1), červenou barvou jsou uvedeny hodnoty vůči neoptimalizovanému modelu zhoršené. Z takto barevně upravené tabulky vyplývají tři závěry: 1. Optimalizace podle jednoho parametru můţe negativně ovlivnit posuzování z hlediska jiného parametru. 2. Nejlepšího výsledku bylo dosaţeno při optimalizaci podle sumy všech zpoţdění, jelikoţ byly zlepšeny všechny sledované parametry. 3. Zajímavé výsledky ovšem získáme i při optimalizaci podle střední celkové průběţné doby výroby, kde obě zlepšení jsou velmi výrazného charakteru.


55

Diplomová práce

Zhodnocení vyuţitelnosti optimalizačních metod

7 Zhodnocení využitelnosti optimalizačních metod Z naměřených hodnot modelu lisovny a teoretických modelů výroby plynou rozdíly mezi optimalizačními algoritmy a prioritními pravidly: Prioritní pravidla:

Optimalizační algoritmy:

Výhody: krátká doba optimalizace

vyšší schopnost dosaţení optima

nenáročné na hardware snadné nastavení pravidla Nevýhody: niţší schopnost dosaţení optima

delší doba optimalizace doba optimalizace závislá na výkonu počítače (a velikosti problému) sloţitější

nastavení

parametrů

jednotlivých algoritmů

Z uvedených výhod a nevýhod porovnávaných metod se prioritní pravidla jeví jako správná volba – přijatelný výsledek velmi rychle a s nutností výběru pouze poţadovaného pravidla. Při pohledu na výsledky optimalizačních algoritmů však zaujme výrazné zlepšení výsledků oproti prioritním pravidlům. Zlepšení je přitom moţné získat v relativně krátkém čase (cca 12 minut), který se s pouţitím dostatečně výkonného počítače ještě sniţuje. Další zmiňovaná nevýhoda (sloţitější nastavení parametrů jednotlivých algoritmů) můţe být eliminována dvěma způsoby: 1. ponecháním přednastavených hodnot jednotlivých parametrů 2. vyuţitím zkušeností s různými nastaveními jednotlivých parametrů Jelikoţ schopnost dosahovat optima závisí mj. na nastavení parametrů optimalizačních algoritmů, můţe dojít při ponechání přednastavených hodnot ke zhoršení této


56

Diplomová práce

Zhodnocení vyuţitelnosti optimalizačních metod

schopnosti. Nicméně výsledky jsou i přesto dostatečné, téměř okamţitě k dispozici a navíc bez potřeby hlubší znalosti optimalizačních algoritmů.

Další poznatky o optimalizačních metodách plynoucí z provedených měření jsou následující: Optimalizační algoritmy nemusí poskytnout optimální výsledek řešeného problému, avšak mohou nabídnout řešení lepší neţ IS (viz kapitoly 5.1.2, 5.1.3 a 6.2.1). Rozdíly ve výsledcích při pouţití různých optimalizačních algoritmů jsou minimální, proto je sloţité určit konkrétní algoritmus jako nejlepší (viz kapitoly 5.2 a 6.2.2). Problémem u optimalizačních algoritmů můţe být výběr vhodného hodnotícího parametru (účelové funkce) pro řešený problém. Volba nevhodného parametru můţe negativně ovlivnit ostatní hodnotící parametry (viz kapitola 6.3.2). Při pouţití prioritních pravidel můţe nastat problém s volbou vhodného pravidla. Při pouţití nevhodného pravidla totiţ opět můţe dojít k negativnímu ovlivnění hodnotících parametrů (viz kapitoly 6.1.1 a 6.1.2).


57

Diplomová práce

Závěr

8 Závěr Diplomová práce měla za cíl zhodnotit moţnosti vyuţití počítačové simulace při rozvrhování dílenských zakázek. K tomuto účelu byly vyuţity jak teoretické příklady, tak i praktický model lisovny. V úvodních kapitolách byl popsán současný stav v oblasti řízení dílenských zakázek a byly představeny optimalizační algoritmy a moţnosti simulačního systému Simcron. V rámci vlastního experimentování byla provedena celá řada simulací, která odhalila jak nedostatky optimalizačních algoritmů, tak i jejich přednosti. Přínosy plynoucí z pouţití těchto algoritmů jsou nepřehlédnutelné. Prakticky v reálném čase lze získat řešení blízké optimu řešeného problému. Za hlavní problém, který brání výraznějšímu vyuţívání optimalizačních algoritmů, lze označit zejména volbu hodnotícího parametru (účelové funkce). Riziko nevhodného nastavení optimalizačního kritéria je vhodné minimalizovat pilotním projektem, při kterém se vyzkouší různé algoritmy i různá nastavení optimalizační funkce. Výsledkem můţe být doporučení „nejlepšího“ nastavení – např. pro naši lisovnu se jako vhodné ukazuje vyuţití metody zakázaného prohledávání v kombinaci s účelovou funkcí „suma všech zpoţdění“.

Oblast rozvrhování zakázek skrývá nevyuţitý potenciál, jehoţ vyuţití můţe znamenat náskok před konkurencí. Výsledky získané v této práci ukázaly na nutnost vyuţívání optimalizačních algoritmů i přes celou řadu problémů, které s jejich vyuţitím souvisejí.


58

Diplomová práce

Pouţitá literatura

Použitá literatura [1]

BAKER, Kenneth R. Introduction to Sequencing and Scheduling. 1974. 305 s.

[2]

DUŠÁKOVÁ, Alice, MANLIG, František, VAVRUŠKA, Jan. Podpora rozvrhování výroby pomocí počítačové simulace. Strojírenská technologie: Časopis pro vědu, výzkum a výrobu. 2007, roč. XII, zvláštní číslo, s. 157-160.

[3]

FRENCH, Simon. Sequencing and scheduling: An Introduction to the Mathematics of the Job-Shop. 1982. 245 s. ISBN 0-85312-299-7.

[4]

GREGOR, Milan, et al. Dynamické plánovanie a riadenie výroby. 1. vyd. Ţilinská univerzita v Ţilině, 2000. 284 s. ISBN 80-7100-607-6.

[5]

KAVAN, Michal. Výrobní a provozní management. 2002. 410 s. ISBN 80-2470199-5.

[6]

KLUSÁČEK, Dalibor. Plánování úloh v paralelním a distribuovaném prostředí. 2006. 55 s. Masarykova univerzita. Vedoucí diplomové práce Mgr. Hana Rudová, PhD.

[7]

KOBLASA F., DIAS L.S., OLIVEIRA J.A., PEREIRA G. : Heuristic Approach as a way to Improve Scheduling in ERP/APS Systems. Proceedings of 15th European Concurrent Engineering Conference (ECEC2008). Eds. A. Brito and J.M. Teixeira, 47-51, Porto April 2008. EUROSIS-ETI Publication. ISBN 9789077381-399-7. (All EUROSIS Proceedings are ISI-Thomson and INSPEC referenced).

[8]

KOBLASA, František. Uplatnění optimalizačních metod v dílenském rozvrhování výrobních zakázek. In Výrobní systémy dnes a zítra 2008. 2009.

[9]

KODĚROVÁ, Lucie. Heuristiky. 2008. 45 s. Univerzita Palackého v Olomouci. Vedoucí bakalářské práce Mgr. Jaroslav Marek, PhD.

[10]

KOŠTURIAK, Ján, GREGOR, Milan. Podnik v roce 2001 : Revoluce v podnikové kultuře. Grada, 1993. 320 s. ISBN 80-7169-003-1.

[11]

LAŢANSKÝ, Jiří. Podklady k přednáškám z předmětu X33SDU [online]. CVUT, [2008] [cit. 2009-03-19]. Dostupný z WWW: .

[12]

MAJER, Petr. Moderní metody rozvrhování výroby. 2003. 90 s. Vysoké učení technické v Brně. Vedoucí dizertační práce RNDr. Jiří Dvořák, CSc. Dostupný z WWW: <majer.czweb.org/scheduling/>.

[13]

MAŠÍN, Ivan. Výroba velkého sortimentu v malých sériích: Principy výrobních systémů pro 21. století. 1. vyd. Institut technologií a managementu, 2004. 101s. ISBN 80-903533-0-4.


59

Diplomová práce


[14]

MITSUO, Gen, RUNWEI, Cheng. Genetic algorithms and engineering design. 1997. 411 s. ISBN 0-471-12741-8.

[15]

PANWALKAR,, S. S., ISKANDER, Wafik. A Survey of Scheduling Rules. OPERATIONS RESEARCH. 1977, no. 1, s. 45-61.

[16]

POSPÍCHAL, Jiří. Www prednášky o evolučných algoritmoch [online]. 2007 [cit. 2009-04-05]. Dostupný z WWW: .

[17]

RUDOVÁ, Hana. Učební materiály k předmětu PA167 Rozvrhování [online]. 2008 [cit. 2009-03-29]. Dostupný z WWW: .

[18]

TOMEK, Gustav, VÁVROVÁ, Věra. Řízení výroby. 1. vyd. Grada Publishing, 1999. 440 s. ISBN 80-7169-578-5.

[19]

TVRDÍK, Josef. Evoluční algoritmy. 2004. 73 s.

[20]

VAVRUŠKA, Jan. Problémy plánování a řízení výroby v omezených kapacitách a prostředí malých a středních podniků. Strojírenská technologie: Časopis pro vědu, výzkum a výrobu. 2007, roč. XII, zvláštní číslo, s. 252-255.

[21]

VAVRUŠKA, Jan. Rozvrhování výroby na úrovni supervisora. In Výrobní systémy dnes a zítra. 2008. s. 10. ISBN 978-80-7372-295-1.

[22]

VEGNEROVÁ, Petra. Operativní plánování a řízení výroby s vyuţitím simulací. In Logistika v teorii a praxi. 1. vyd. Technická univerzita v Liberci, 2004. s. 164168. ISBN 80-7083-813-2.

[23]

WATSON, Jean-Paul. Empirical Modeling and Analysis of Local Search Algorithms for the Job-Shop Scheduling Problem. 2003. 295 s. Dizertační práce.

[24]

ZELINKA, Ivan. Umělá inteligence v problémech globální optimalizace. 1. vyd. BEN - technická literatura, 2002. 192 s. ISBN 80-7300-069-5.

[25]

APS. IPA Slovakia [online]. 2009 [cit. 2009-04-29]. Dostupný z WWW: .

[26]

ČVUT FEL VT SZZ [online]. [2004] [cit. 2009-04-25]. Dostupný z WWW: .

[27]

Genetický algoritmus. Wikipedie : Otevřená encyklopedie [online]. 2009 [cit. 2009-04-25]. Dostupný z WWW: .

[28]

Hladový algoritmus. Wikipedie : Otevřená encyklopedie [online]. 2009 [cit. 2009-04-25]. Dostupný z WWW: .


60

Diplomová práce


[29]

MRP III. IPA Slovakia [online]. 2009 [cit. 2009-04-29]. Dostupný z WWW: .

[30]

Optimalizační algoritmy [online]. [2006] [cit. 2009-02-12]. Dostupný z WWW: .

[31]

Nápověda systému Simcron.


61

Diplomová práce

Seznam obrázků a tabulek

Seznam obrázků a tabulek Obr. 2.1: Model výroby typu Open shop ........................................................................ 16 Obr. 2.2: Model výroby typu Flow shop ........................................................................ 17 Obr. 2.3: Model výroby typu Job shop ........................................................................... 18 Obr. 2.4: Rozdělení rozvrhů [1] ...................................................................................... 18 Obr. 2.5: Porovnání neaktivního a semiaktivního rozvrhu [8] ....................................... 19 Obr. 2.6: Porovnání semiaktivního a aktivního rozvrhu [8] ........................................... 20 Obr. 2.7: Porovnání aktivního rozvrhu a rozvrhu bez zpoţdění [8] ............................... 21 Obr. 3.1: Moţné uspořádání optimalizačních algoritmů [30] ......................................... 22 Obr. 4.1: Ganttův diagram - průběţná doba výroby [31] ............................................... 30 Obr. 5.1: Model příkladu ft06 ......................................................................................... 34 Obr. 6.1: Vyuţití pracovišť 12 – 22 ................................................................................ 53 Obr. 6.2: Vyuţití pracovišť 1 – 11 .................................................................................. 54 Tab. 5.1: Známá optima teoretických modelů výroby .................................................... 33 Tab. 5.2: Dosaţené výsledky při řízení zakázek prioritním pravidlem .......................... 35 Tab. 5.3: Průměrné hodnoty - model ft06 - rozvrh bez zpoţdění ................................... 36 Tab. 5.4: Průměrné hodnoty - model ft10 - rozvrh bez zpoţdění ................................... 36 Tab. 5.5: Průměrné hodnoty - model ft20 - rozvrh bez zpoţdění ................................... 36 Tab. 5.6: Průměrné hodnoty - model la02 - rozvrh bez zpoţdění .................................. 36 Tab. 5.7: Průměrné hodnoty - model la19 - rozvrh bez zpoţdění .................................. 37 Tab. 5.8: Průměrné hodnoty - model la21 - rozvrh bez zpoţdění .................................. 37 Tab. 5.9: Průměrné hodnoty - model la27 - rozvrh bez zpoţdění .................................. 37 Tab. 5.10: Průměrné hodnoty - model la30 - rozvrh bez zpoţdění ................................ 37 Tab. 5.11: Průměrné hodnoty - model la40 - rozvrh bez zpoţdění ................................ 38 Tab. 5.12: Průměrné hodnoty - model sw11 - rozvrh bez zpoţdění ............................... 38 Tab. 5.13: Dosaţené výsledky při řízení zakázek prioritním pravidlem ........................ 39 Tab. 5.14: Průměrné hodnoty - model ft06 - aktivní rozvrh ........................................... 39 Tab. 5.15: Průměrné hodnoty - model ft10 - aktivní rozvrh ........................................... 40 Tab. 5.16: Průměrné hodnoty - model ft20 - aktivní rozvrh ........................................... 40 Tab. 5.17: Průměrné hodnoty - model la02 - aktivní rozvrh .......................................... 40 Tab. 5.18: Průměrné hodnoty - model la19 - aktivní rozvrh .......................................... 40 Tab. 5.19: Průměrné hodnoty - model la21 - aktivní rozvrh .......................................... 41 Tab. 5.20: Průměrné hodnoty - model la27 - aktivní rozvrh .......................................... 41 Tab. 5.21: Průměrné hodnoty - model la30 - aktivní rozvrh .......................................... 41 Tab. 5.22: Průměrné hodnoty - model la40 - aktivní rozvrh .......................................... 41 Tab. 5.23: Průměrné hodnoty - model sw11 - aktivní rozvrh ......................................... 42 Tab. 5.24: Bodování optimalizačních algoritmů ............................................................ 42 Tab. 5.25: Počet dosaţených bodů.................................................................................. 43 Tab. 5.26: Celkový počet dosaţených bodů ................................................................... 44


62

Diplomová práce

Seznam obrázků a tabulek

Tab. 6.1: Výsledky účelových funkcí při řízení prioritními pravidly ............................. 46 Tab. 6.2: Průměrné hodnoty - celková průběţná doba výroby ....................................... 48 Tab. 6.3: Průměrné hodnoty - střední celková průběţná doba výroby ........................... 48 Tab. 6.4: Průměrné hodnoty - střední doba čekání ......................................................... 48 Tab. 6.5: Průměrné hodnoty - suma všech zpoţdění ...................................................... 49 Tab. 6.6: Průměrné hodnoty - vytíţení strojů ................................................................. 49 Tab. 6.7: Bodování optimalizačních algoritmů .............................................................. 49 Tab. 6.8: Počet dosaţených bodů.................................................................................... 50 Tab. 6.9: Celkový počet dosaţených bodů .................................................................... 50 Tab. 6.10: Výsledky optimalizace podle střední celkové průběţné doby výroby .......... 51 Tab. 6.11: Výsledky optimalizace podle sumy všech zpoţdění ..................................... 52 Tab. 6.12: Výsledky optimalizace podle celkové průběţné doby výroby ...................... 52 Tab. 6.13: Průměrné hodnoty při optimalizaci podle různých účelových funkcí ........... 55

Seznam příloh Příloha I: Příloha II: Příloha III: Příloha IV:

Zadání teoretických modelů výroby......................................................... I Teoretické modely – naměřené hodnoty (rozvrh bez zpoţdění) ........... VI Teoretické modely – naměřené hodnoty (aktivní rozvrh) ...................... X Model lisovny – naměřené hodnoty ................................................... XIV


63

Diplomová práce

Přílohy

Příloha I: Příklad ft06 (6×6) 2 1 0 3 1 6 3 1 8 2 5 4 10 5 2 5 3 4 5 8 0 1 5 0 5 2 5 3 2 9 1 3 4 5 5 1 3 3 3 5 9 0

Zadání teoretických modelů výroby

7 10 9 3 4 10

5 0 1 4 0 4

3 10 1 8 3 4

4 3 4 5 3 2

6 4 7 9 1 1

5 1 5 8 4 9 5 6 9 9

Příklad ft10 (10×10) 0 29 1 78 2 9 3 0 43 2 90 4 75 9 1 91 0 85 3 39 2 1 81 2 95 0 71 4 2 14 0 6 1 22 5 2 84 1 2 5 52 3 1 46 0 37 3 61 2 2 31 0 86 1 46 5 0 76 1 69 3 76 5 1 85 0 13 2 61 6

36 11 74 99 61 95 13 74 51 7

4 3 8 6 3 8 6 4 2 8

49 69 90 9 26 48 32 32 85 64

Příklad ft20 (20×5) 0 29 1 9 2 49 0 43 1 75 3 69 1 91 0 39 2 90 1 81 0 71 4 9 2 14 1 22 0 26 2 84 1 52 4 48 1 46 0 61 2 32 2 31 1 46 0 32 0 76 3 76 2 85 1 85 2 61 0 64 1 78 3 36 0 11 2 90 0 11 1 28 0 85 2 74 1 10 2 95 0 99 1 52 0 6 1 61 4 69 1 2 0 95 3 72 0 37 2 13 1 21 0 86 1 74 4 88 1 69 2 51 0 11 0 13 1 7 2 76

62 46 12 85 21 47 32 19 40 47 56 46 89 98 49 65 89 48 89 52

4 4 3 3 4 3 4 4 4 4 2 4 4 4 3 2 4 3 4 4

44 72 45 22 72 6 30 36 26 90 21 30 33 43 53 25 55 79 74 45

3 2 4 2 3 0 3 3 1 3 4 3 3 3 2 4 3 2 3 3


11 28 10 52 69 72 21 88 11 76

6 6 7 7 8 0 9 8 6 5

62 46 12 85 21 47 32 19 40 47

7 5 6 3 7 6 8 9 7 3

56 46 89 98 49 65 89 48 89 52

8 7 9 9 9 4 7 7 4 4

44 72 45 22 72 6 30 36 26 90

9 8 4 5 6 7 4 3 8 7

21 30 33 43 53 25 55 79 74 45

I

Diplomová práce Příklad la02 (10×5) 0 20 3 87 1 31 4 25 2 32 0 24 1 72 2 23 4 28 2 86 1 76 4 97 4 27 0 42 3 48 1 67 0 98 4 48 4 28 1 12 3 19 1 63 0 94 2 98 4 14 0 75 2 50 4 72 2 18 1 37

Přílohy

4 1 0 0 2 3 0 3 1 3

76 18 58 45 17 27 80 50 41 79

2 3 3 3 1 2 2 4 3 0

17 81 99 90 46 62 50 80 55 61

Příklad la19 (10×10) 2 44 3 5 5 58 4 4 15 7 31 1 87 8 9 82 6 22 4 10 3 1 91 2 17 7 62 5 6 71 1 90 3 75 0 7 70 5 93 8 77 2 6 87 1 63 4 26 5 0 36 5 15 8 41 9 5 88 2 81 3 13 6 9 88 4 54 6 64 7

97 57 70 75 64 29 6 78 82 32

0 0 1 8 2 4 2 3 4 0

9 77 49 47 94 58 82 76 54 52

7 3 0 4 8 6 3 6 7 2

84 85 40 11 15 93 27 84 13 6

8 2 8 3 4 3 7 4 8 8

77 81 34 7 12 68 56 30 29 54

9 5 2 6 7 1 8 7 9 5

96 39 48 72 67 57 48 76 40 82

1 9 7 9 9 9 9 2 1 3

58 73 80 35 20 7 36 36 78 6

6 6 5 0 5 0 0 1 0 1

89 21 71 55 50 52 95 8 75 26

Příklad la21 (15×10) 2 34 3 55 5 95 9 3 39 2 31 0 12 1 1 19 0 83 3 34 4 4 60 2 87 8 24 5 8 79 9 77 2 98 4 8 35 7 95 6 9 9 4 28 5 59 3 16 9 5 9 4 20 2 39 6 1 28 5 33 0 78 3 2 94 5 84 6 78 9 1 31 4 24 0 20 2 5 28 9 97 0 58 4 5 27 9 48 8 27 7 1 12 8 50 0 80 2 4 61 3 55 6 37 5

16 42 92 77 96 10 43 54 26 81 17 45 62 50 14

4 9 6 3 3 2 0 1 2 1 9 6 4 9 2

21 79 54 69 17 35 46 45 37 74 25 76 98 80 50

6 8 9 7 0 1 8 7 7 3 8 3 6 3 8

71 77 79 38 44 7 50 71 8 27 81 99 67 19 79

0 6 8 1 7 5 6 0 8 8 5 2 3 5 1

53 77 62 87 43 28 52 87 66 69 76 23 48 28 41

8 5 5 6 6 4 7 3 6 0 3 1 0 6 9

52 98 37 41 75 61 27 41 89 69 87 72 42 63 72

1 4 2 9 1 0 2 9 9 7 7 8 1 4 7

21 55 64 83 49 95 59 43 42 45 32 90 46 94 18

7 7 7 0 5 3 1 8 4 4 6 7 2 7 0

26 66 43 93 25 76 91 14 33 96 18 86 17 98 75


II

Diplomová práce

Přílohy

Příklad la27 (20×10) 3 60 4 48 5 95 0 7 37 6 34 0 97 5 4 45 2 73 1 24 8 0 53 2 12 9 12 1 4 90 2 49 9 27 7 3 85 4 25 2 84 6 5 88 6 67 4 14 0 1 78 5 64 4 63 6 1 11 0 64 6 97 9 3 93 2 95 7 43 1 2 61 3 41 5 49 4 4 13 7 7 1 98 8 9 86 6 76 4 14 3 1 40 2 53 7 97 5 6 33 1 33 3 87 0 7 92 5 91 8 79 2 6 82 1 41 4 28 5 0 52 5 42 8 24 9 5 82 2 76 3 86 6 9 77 4 8 6 42 7

87 55 28 37 65 64 41 46 38 65 23 57 41 87 18 54 64 91 93 64

1 2 0 8 5 9 1 3 2 8 0 0 1 8 2 4 2 3 4 0

72 21 28 33 7 13 73 84 17 32 66 73 85 96 55 69 78 47 84 70

9 3 3 3 6 1 7 0 4 0 7 3 0 4 8 6 3 6 7 2

5 20 25 71 23 66 57 84 85 59 49 73 37 84 13 79 76 88 38 45

8 4 5 6 0 7 2 8 5 6 8 2 8 3 4 3 7 4 8 8

35 59 23 55 48 46 53 28 73 85 70 68 19 16 77 33 6 91 95 45

7 9 7 5 3 8 3 9 3 5 9 5 2 6 7 1 8 7 9 5

39 46 83 29 83 59 80 52 10 46 99 40 17 66 60 61 49 52 37 28

6 8 9 7 8 0 9 7 8 9 1 9 7 9 9 9 9 2 1 3

54 19 5 87 17 62 47 26 95 85 90 98 54 52 42 39 47 28 21 67

2 1 6 4 1 5 8 2 7 4 6 6 5 0 5 0 0 1 0 1

66 46 78 38 40 19 74 41 67 60 17 9 79 95 74 16 58 35 23 86

Příklad la30 (20×10) 6 32 3 16 1 33 8 8 39 4 81 3 91 5 3 84 2 57 7 41 5 4 20 5 6 2 15 8 9 24 6 49 5 16 4 1 86 8 50 2 77 6 5 86 6 90 3 78 9 2 59 3 18 9 31 4 3 47 4 79 6 76 0 0 59 2 89 4 10 7 5 63 6 9 4 77 3 0 74 1 32 2 61 7 2 85 9 51 0 61 5 0 51 3 24 5 8 6 1 71 5 42 8 68 2 1 28 5 38 4 51 7 0 18 2 90 4 25 6 5 67 2 96 1 38 4 2 92 8 51 4 59 6 3 98 7 80 5 78 0

12 56 73 19 11 54 88 41 59 45 37 53 99 30 31 70 92 86 52 82

7 9 4 1 3 9 2 7 1 3 2 4 4 7 6 2 8 0 5 2

70 69 81 30 60 48 57 20 72 8 5 92 37 12 29 33 85 97 8 7

4 1 0 0 7 0 0 5 2 5 8 9 6 8 3 8 5 3 9 9

10 45 88 94 5 93 32 83 8 54 13 20 94 23 63 78 35 94 70 89

9 6 8 6 8 3 7 8 9 6 9 8 1 2 4 9 7 7 1 1

75 59 38 45 63 32 57 65 30 88 79 10 98 7 65 45 29 86 75 69

0 0 9 7 1 7 8 0 5 8 1 3 8 4 9 3 1 6 3 4

82 86 17 17 25 92 86 54 73 20 24 5 65 17 70 90 81 35 54 51

5 2 6 3 2 5 4 6 7 9 7 6 3 9 7 6 9 9 7 8

88 36 83 18 15 45 71 94 57 7 10 45 33 35 27 54 80 82 60 79

2 7 1 9 0 4 1 1 8 1 0 5 7 1 0 0 3 8 0 6

20 68 5 88 45 71 39 69 84 62 82 23 75 81 93 72 59 45 33 62


III

Diplomová práce

Přílohy

Příklad la40 (15×15) 9

65 10 28

0

4

74 12 33 2

2

51 14 75

5

73

8

32

6

81

1

35

7

59 13 38 11 55

0

27

8

7

13 90 12 21

6

23

3

10 10 39

7

2

93 13 77

64

1

53 11 83

33

4

6

9

52 14 72

14 73

3

82

1

23 12 62

6

88

5

21

8

65 11 70

1

13

3

53 10 81

0

5

49

7

72

61

9

28

4

78

12

6

51

7

33

4

15 14 72 10 98

9

94

5

12 11 42

2

24 13 15

8

28

3

6

12 99

0

41

12 97

5

7

9

96

4

15 14 73 13 43

0

32

8

22 11 42

1

94

23

7

86

6

78 10 24

3

31

1

72

5

88

2

93 13 13

4

44 14 66

6

63

7

14

67 10 17 11 85

0

35

3

68 12

5

8

49

9

15

7

82

6

21 14 53

3

72 13 49

2

99

4

26 12 56

8

45

68 10 51

0

8

5

27 11 96

3

54

7

24

4

14

8

38

5

36

2

52 14 55 12 37 11 48

0

93 13 60 10 70

1

23

6

23

9

83

3

12

8

69

6

26

9

23 14 28

1

82

5

33

7

15 11

12 73 10 59

2

37

0

62

0

87

5

12

7

80

4

50 10 48 12 90

1

72 13 24

8

71 11 44

2

54

0

22

6

61

4

46

3

73

5

16 12

10 92 14 36

4

22

9

9

3

47

1

77 12 79 13 36

0

3

73

6

82

1

82 14 92 11 73

10 98 12 34 13 52

4

26

1

28

3

39

8

80

90 12 67

4

14

8

23

3

21

1

49 13 83

70 10 17

6


6

4

9

9

45 13 64 6

14

94 14 93 13 67 6

2

1

8

9

9

46

15 14 61

3

92

54

7

75 11 32 10 40

2

1

97

0

30

30

8

98 11 79

7

7

5

55

2

6

4

31 10 35

9

54

5

7

8

37

7

72

2

52 12 76

5

29

0

43

6

48

7

58

2

45 14 94 11 96

7

18 13 43 11 84

5

26

9

36

2

93 14 84

9

70

0

42

IV

Diplomová práce Příklad sw11 (50×10) 0 92 4 47 3 56 0 86 2 100 1 75 1 4 4 94 3 44 4 87 0 48 1 59 0 83 1 78 4 76 3 49 0 15 1 100 0 28 3 53 4 84 2 61 4 71 3 54 0 85 2 75 1 33 2 24 3 20 1 65 2 48 3 27 4 1 2 79 0 4 4 61 0 16 4 31 3 77 1 40 0 39 4 15 4 48 0 93 2 8 3 70 1 8 2 65 0 21 2 28 1 26 1 50 2 60 0 51 1 21 3 3 2 47 3 57 4 26 2 36 1 20 0 20 4 6 3 71 1 40 0 86 4 83 0 61 3 27 4 68 1 94 3 46 4 33 1 13 2 91 4 58 3 30 0 24 2 62 1 47 4 5 4 100 0 21 1 53 1 8 0 3 2 88 3 33 4 72 0 83 4 63 2 36 3 70 2 28 1 37 4 24 3 15 0 46 2 14 4 89 3 78 2 51 4 26 1 69 2 92 1 38 2 44 3 47 3 42 4 85 1 29 3 99 0 46 4 74 1 15 3 80 4 47 0 90 2 51 3 66 0 59 1 50 4 40 1 62 2 72 4 30 2 20 4 14 3 85 0 49 3 49 4 46 4 74 1 55 2 73 3 13 2 96 1 8 4 73 1 97 3 39 3 43 2 67 0 38 0 35 2 68 1 5 2 68 1 81 0 2

Přílohy

2 3 2 2 3 4 2 1 4 4 0 3 2 2 3 0 3 4 4 0 3 2 1 2 3 2 3 3 3 2 0 0 4 1 3 4 0 2 2 4 3 0 1 1 0 0 0 1 3 3

91 92 40 92 64 18 47 34 72 33 23 46 3 93 50 32 91 90 34 48 74 23 86 60 27 12 39 74 54 17 97 30 18 63 15 23 35 96 25 5 23 21 4 89 25 15 22 77 46 4


1 4 0 3 2 2 1 0 3 0 1 1 1 3 1 4 4 3 0 1 2 4 2 0 0 1 0 2 4 1 1 3 1 0 0 0 2 1 0 1 2 3 0 2 3 4 2 4 4 4

49 90 92 35 44 24 85 13 49 75 66 69 25 48 5 84 58 93 53 11 48 29 99 33 38 38 75 3 18 23 99 55 99 29 23 10 66 48 8 86 93 15 2 64 16 97 90 11 4 59

5 5 8 6 8 6 7 9 7 9 6 7 8 6 6 8 9 7 9 9 9 7 7 7 8 8 7 8 9 6 6 8 9 7 8 9 9 5 9 5 7 5 9 9 7 6 9 7 7 9

39 11 53 99 12 92 100 47 23 47 35 10 88 63 48 9 90 20 67 44 77 99 31 46 82 2 60 34 4 24 71 38 48 70 42 63 46 52 61 59 61 77 33 72 19 95 64 61 51 53

9 7 6 7 9 9 5 8 5 6 7 8 7 9 7 6 6 9 8 7 8 8 5 5 7 9 9 6 6 8 9 5 6 9 6 7 8 6 7 6 9 6 7 8 9 7 6 5 6 8

63 85 40 46 91 65 34 2 12 84 46 88 97 74 46 43 43 33 8 25 15 56 60 86 31 37 65 6 34 60 92 9 41 7 95 65 25 13 70 97 96 13 90 6 38 2 65 7 44 69

7 8 9 9 6 5 6 6 8 8 9 9 9 8 9 7 8 8 5 5 5 6 8 9 6 5 8 7 5 9 5 9 5 5 5 6 5 7 8 9 8 7 5 5 6 5 8 9 5 5

12 54 5 27 31 26 35 97 90 44 29 19 49 46 35 10 64 27 68 30 80 100 40 63 23 59 61 91 54 96 41 77 10 14 47 21 90 88 23 28 63 2 48 83 22 66 31 95 58 69

6 9 5 8 7 7 8 7 6 7 5 6 6 7 5 5 5 6 7 8 7 9 9 6 9 6 6 9 8 7 8 7 7 8 9 5 7 8 6 7 6 8 8 6 5 8 5 8 9 6

1 100 68 83 98 29 90 27 87 74 63 50 79 91 88 72 39 12 1 92 27 77 84 70 27 37 77 80 59 78 73 17 47 84 83 70 85 4 93 85 34 22 90 13 26 57 98 97 69 14

8 6 7 5 5 8 9 5 9 5 8 5 5 5 8 9 7 5 6 6 6 5 6 8 5 7 5 5 7 5 7 6 8 6 7 8 6 9 5 8 5 9 6 7 8 9 7 6 8 7

37 38 27 91 63 24 88 97 42 29 44 34 22 51 97 60 93 89 71 57 10 28 26 89 87 36 31 28 42 70 97 51 80 32 56 56 75 30 5 9 14 22 62 66 63 46 85 69 98 21

V

Diplomová práce

Přílohy

Příloha II: Teoretické modely – naměřené hodnoty (rozvrh bez zpoždění) V jednotlivých sloupcích tabulek jsou uvedeny následující údaje: Po – hodnota výsledku po optimalizaci čas – doba optimalizace iter. – iterace, při které byl nalezen výsledek poč – počet prohledaných iterací (pouze u příkladu sw11)

ft06 (6×6) Rozvrh bez zpoždění Náhodné prohledávání Hladové prohledávání Simulované žíhání Zakázané hledání Genetický algoritmus

Po 57 57 58 57 57

Náhodné prohledávání Hladové prohledávání Simulované žíhání Zakázané hledání Genetický algoritmus

57 57 57 57 57


Po 1027 987 1034 982 1010


1002 968 997 1001 968


Měření 1 čas 04:45 05:43 06:09 05:07 05:12 Měření 4 01:21 01:38 01:52 01:22 01:26 Měření 1 čas 07:06 08:13 07:33 07:17 08:15 Měření 4 01:59 02:29 02:18 02:00 02:29

iter. 2560 1163 4829 706 375

Po 57 57 59 57 57

1914 472 6104 1433 98

57 57 59 57 57

iter. 9116 8029 3752 8306 7085

Po 1004 988 1007 984 989

800 6521 9768 1503 9232

1015 995 1018 1010 984


iter. 6780 1454 18 463 355

Po 57 57 57 57 57

Měření 3 čas 01:21 01:38 01:48 01:22 01:26

iter. 200 751 4301 1541 161

Po 1013 964 1010 1013 968

Měření 3 čas 01:53 02:22 02:11 01:55 02:22

iter. 9850 8576 9744 1886 7962

4851 260 15 1317 231

iter. 1643 8235 4884 1959 1196 6955 4512 6406 1672 7690

VI

Diplomová práce

Přílohy


Po 1255 1185 1234 1250 1203


1233 1195 1240 1227 1190

la02 (10×5) Rozvrh bez zpoždění Náhodné prohledávání Hladové prohledávání Simulované žíhání Zakázané hledání Genetický algoritmus

Po 707 685 715 687 675


694 668 703 682 676


Po 875 875 875 877 875


875 875 877 875 875


Měření 1 čas 08:45 10:13 09:24 08:41 11:16 Měření 4 02:20 02:54 02:35 02:20 03:03 Měření 1 čas 06:07 06:39 06:28 05:51 06:50 Měření 4 01:33 01:55 01:53 01:34 01:58 Měření 1 čas 06:56 08:26 07:42 07:22 08:28 Měření 4 01:54 02:24 02:13 01:57 02:22

iter. 3185 9725 5244 793 5340

Po 1226 1190 1213 1243 1219

8074 9187 7653 9305 7190

1250 1200 1233 1226 1185

iter. 2686 4870 222 522 7721

Po 703 672 695 694 685

1760 7075 7121 302 7411

694 694 675 694 676

iter. 4710 2022 8124 9816 3629

Po 875 875 880 875 875

727 3213 5643 6554 7194

875 875 880 875 875


iter. 1319 9369 8893 3546 8627

Po 1234 1203 1233 1232 1185

Měření 3 čas 02:17 02:52 02:34 02:20 03:05

iter. 2862 8717 9383 726 8581

Po 702 675 694 694 687

Měření 3 čas 01:33 01:55 01:53 01:35 01:58

iter. 7521 8150 8266 521 5612

Po 877 877 880 876 875

Měření 3 čas 01:55 02:23 02:13 01:56 02:22

iter. 6491 713 8817 2827 2952

4533 8604 8112 5864 6382

iter. 9364 6564 7565 6719 3373 5521 1729 8363 5381 8980

iter. 8833 4328 5476 1336 2894 7029 996 8024 822 7566

VII

Diplomová práce

Přílohy


Po 1163 1112 1159 1126 1132


1149 1116 1138 1132 1112


Po 1392 1375 1355 1382 1330


1396 1315 1372 1345 1334


Po 1479 1441 1447 1400 1415


1442 1404 1433 1403 1392



iter. 5135 9385 7787 5286 8554

Po 1159 1100 1140 1147 1119

4253 9416 8191 2476 8865

1143 1129 1142 1118 1123

iter. 4006 9531 8917 8081 8230

Po 1406 1314 1374 1367 1338

5265 9649 9972 9460 7107

1381 1340 1390 1339 1347

iter. 918 9143 3827 2275 5592

Po 1450 1407 1432 1440 1416

9987 9524 5257 989 8375

1446 1402 1433 1397 1408


iter. 6196 8209 9054 9579 6160

Po 1151 1128 1151 1134 1103

Měření 3 čas 02:26 03:07 02:38 02:31 03:06

iter. 8132 8947 8028 1421 8784

Po 1402 1340 1368 1346 1336

Měření 3 čas 03:26 03:59 03:11 03:11 03:52

iter. 7649 8927 9879 5216 9836

Po 1461 1433 1460 1419 1380

Měření 3 čas 03:15 04:01 03:12 03:09 03:51

iter. 9690 9450 8578 6754 6221

1208 9377 9706 1060 5718

iter. 4473 9859 6666 3289 6369 1964 9302 6949 7922 8672

iter. 4305 9587 8527 4906 6702 4020 9583 8491 4466 8687

VIII

Diplomová práce

Přílohy


Po 1344 1321 1340 1300 1299


1320 1315 1338 1315 1306

sw11 (50×10) bez zpoždění Náhodné pr. Hladové pr. Simulované ž. Zakázané hl. Genetický a.

Po 3546 3663 3496 3411 3537

Náhodné pr. Hladové pr. Simulované ž. Zakázané hl. Genetický a.

3495 3657 3501 3468 3592

Měření 1 čas 11:04 14:33 11:14 11:23 13:18 Měření 4 03:04 04:02 03:15 03:11 04:05

Měření 1 čas poč 15:00 4946 15:00 3192 15:00 4829 15:00 4787 15:00 3775 Měření 2 15:00 4765 15:00 3171 15:00 4826 15:00 4947 15:00 3807


iter. 9085 8410 3270 2598 8994

Po 1347 1278 1337 1312 1310

5282 9374 7857 1167 9241

1317 1285 1329 1317 1293

iter. 2737 2971 4028 1974 3543

Po 3543 3507 3490 3436 3427

4265 2192 2764 739 2913

3533 3538 3472 3430 3442



iter. 7371 9387 4856 9168 2267

Po 1337 1316 1330 1319 1304

Měření 3 čas 03:08 04:05 03:16 03:12 03:48

iter. 5176 6875 8807 6594 5579

3282 7900 8844 2132 9437

iter. 5425 9809 8773 3793 9311

Po 3536 3484 3475 3431 3499

Měření 4 čas 08:53 12:01 08:23 09:02 11:59

iter. 2945 8899 7312 2604 6868

5900 9816 1750 6575 9183

IX

Diplomová práce

Přílohy

Příloha III: Teoretické modely – naměřené hodnoty (aktivní rozvrh) V jednotlivých sloupcích tabulek jsou uvedeny následující údaje: Po – hodnota výsledku po optimalizaci čas – doba optimalizace iter. – iterace, při které byl nalezen výsledek

ft06 (6×6) aktivní rozvrh Náhodné prohledávání Hladové prohledávání Simulované žíhání Zakázané hledání Genetický algoritmus

Po 60 58 63 60 58


59 58 63 58 59


Po 1172 1077 1169 1141 1042


1143 1043 1160 1161 1048



iter. 7232 2275 1690 3427 9027

Po 61 58 59 58 59

7212 4761 5722 5061 3489

60 55 60 58 58

iter. 9877 9436 9463 8115 9097

Po 1159 1112 1123 1134 1073

6878 9314 9648 9288 9154

1154 1094 1169 1154 1086


iter. 2658 2380 698 262 5832

Po 58 58 60 59 59

Měření 3 čas 00:57 01:06 00:55 01:07 01:06

iter. 1599 2841 1432 4738 3110

Po 1156 1102 1139 1157 1068

Měření 3 čas 02:05 02:36 02:21 02:14 05:50

iter. 7211 9082 6570 9772 9546

3927 5889 6349 9656 1133

iter. 1242 9977 6636 481 9070 4260 9676 9286 319 4904

X

Diplomová práce

Přílohy


Po 1408 1303 1375 1399 1350


1391 1366 1370 1396 1361

la02 (10×5) aktivní rozvrh Náhodné prohledávání Hladové prohledávání Simulované žíhání Zakázané hledání Genetický algoritmus

Po 761 677 737 767 720


730 692 755 738 704


Po 1004 932 1008 976 931


1017 945 1011 986 972



iter. 2174 9810 6134 221 9841

Po 1394 1392 1381 1414 1339

3330 9990 3268 549 6296

1381 1386 1395 1389 1338

iter. 2867 8213 9170 850 9314

Po 722 717 751 733 685

9690 9718 9154 5420 7472

712 719 729 738 709

iter. 9173 9568 2736 533 4910

Po 994 929 1008 991 947

3920 9152 8931 7176 8348

1003 960 987 968 924


iter. 5869 9979 8637 5199 7337

Po 1399 1355 1381 1403 1342

Měření 3 čas 02:34 03:02 02:42 02:29 03:10

iter. 4736 9710 6145 8482 7543

Po 777 724 738 717 699

Měření 3 čas 01:42 02:04 01:55 01:44 02:09

iter. 2328 9257 8194 9628 9166

Po 1010 983 992 973 925

Měření 3 čas 02:07 02:36 02:21 02:13 02:43

iter. 5033 9438 9654 7568 8911

2812 7025 2241 164 9998

iter. 6598 8031 8754 5337 7909 5188 7230 8039 299 6462

iter. 9329 9995 5114 3176 5449 9904 9250 4877 2908 9864

XI

Diplomová práce

Přílohy


Po 1382 1307 1361 1345 1301


1359 1293 1354 1350 1319


Po 1700 1624 1702 1599 1579


1679 1627 1682 1595 1622


Po 1733 1685 1740 1644 1656


1650 1707 1705 1678 1660



iter. 1573 9748 3413 2609 6134

Po 1390 1339 1373 1334 1276

2083 9578 9008 460 9900

1370 1261 1336 1299 1302

iter. 3540 9733 8806 4466 8795

Po 1651 1580 1672 1663 1532

7143 9574 4556 8795 7457

1701 1605 1697 1666 1548

iter. 2258 9636 2929 7279 7449

Po 1743 1632 1686 1651 1620

1285 9408 8788 2147 8824

1744 1599 1758 1650 1629


iter. 5242 9102 6094 3747 9812

Po 1332 1338 1358 1308 1308

Měření 3 čas 02:59 03:14 02:53 02:42 03:24

iter. 717 9249 7659 5830 3791

Po 1717 1670 1688 1645 1619

Měření 3 čas 03:30 04:27 03:45 03:24 04:23

iter. 5434 9665 6534 3653 8578

Po 1753 1668 1752 1690 1584

Měření 3 čas 03:22 04:27 03:40 03:30 04:15

iter. 6825 9880 2470 6892 5144

6018 9941 6908 4579 8021

iter. 4848 9977 9550 5349 9153 8335 8173 6168 804 7416

iter. 7993 9879 9392 9184 9512 229 9994 1713 5389 9362

XII

Diplomová práce

Přílohy


Po 1609 1529 1571 1581 1462


1627 1478 1581 1529 1504

sw11 (50×10) aktivní rozvrh Náhodné prohledávání Hladové prohledávání Simulované žíhání Zakázané hledání Genetický algoritmus

Po 4083 4247 4060 4134 4095


4083 4252 4083 4083 4107



iter. 3499 7938 9986 7796 7138

Po 1636 1578 1580 1547 1460

6614 9901 9173 2963 9427

1607 1526 1544 1527 1474

iter. 732 9999 3035 9405 9737

Po 4044 4129 4037 4057 4131

2115 9924 2279 1691 8310

4083 4349 4037 4059 4222


iter. 7544 7055 9524 4421 9360

Po 1582 1498 1575 1532 1494

Měření 3 čas 03:40 04:18 03:35 03:34 04:23

iter. 2004 9904 3762 7831 7808

Po 4083 4215 4052 4074 4151

Měření 3 čas 09:35 11:22 08:58 09:13 12:24

iter. 814 9749 8388 371 9154

6852 9765 7369 1105 9224

iter. 4362 9959 1043 5408 8888 2679 2497 9930 2338 9998

XIII

Diplomová práce

Přílohy

Příloha IV: Model lisovny – naměřené hodnoty V jednotlivých sloupcích tabulek jsou uvedeny následující údaje: Po – hodnota výsledku po optimalizaci čas – doba optimalizace iter. – iterace, při které byl nalezen výsledek

Celková průběžná doba výroby Náhodné prohledávání Hladové prohledávání Simulované žíhání Zakázané hledání Genetický algoritmus Náhodné prohledávání Hladové prohledávání Simulované žíhání Zakázané hledání Genetický algoritmus Střední celková průběžná doba výroby Náhodné prohledávání Hladové prohledávání Simulované žíhání Zakázané hledání Genetický algoritmus Náhodné prohledávání Hladové prohledávání Simulované žíhání Zakázané hledání Genetický algoritmus

Měření 1 Po čas 566146 05:28 566146 05:51 566146 05:44 566146 04:59 566146 06:37 Měření 4 566146 05:28 566146 05:47 566146 05:47 566146 05:10 566146 06:39 Měření 1 Po čas 178616 05:29 171456 05:40 169931 05:30 170436 05:19 175850 07:03 Měření 4 179682 05:30 170988 05:41 169942 05:27 170814 05:22 172837 07:03


iter. 58 35 83 203 8 49 6 125 63 121

iter. 6716 9704 7922 6188 5844 9008 9647 8673 4055 9132


iter. 180 39 49 114 34

Měření 3 Po čas iter. 566146 05:28 12 566146 05:46 35 566146 05:44 12 566146 05:22 209 566146 06:35 12

63 2 169 65 102

iter. 7800 9392 5969 9355 8706

Měření 3 Po čas 176944 05:30 170342 05:44 169762 05:23 170985 05:22 174879 07:06

iter. 1122 9922 9892 3023 9657

3979 9317 7635 3358 8250

XIV

Diplomová práce

Střední doba čekání Náhodné prohledávání Hladové prohledávání Simulované žíhání Zakázané hledání Genetický algoritmus Náhodné prohledávání Hladové prohledávání Simulované žíhání Zakázané hledání Genetický algoritmus

Vytížení strojů Náhodné prohledávání Hladové prohledávání Simulované žíhání Zakázané hledání Genetický algoritmus Náhodné prohledávání Hladové prohledávání Simulované žíhání Zakázané hledání Genetický algoritmus

Suma všech zpoždění

Přílohy Měření 1 Po čas 48435 05:30 39199 05:48 39492 05:22 39364 05:20 42935 07:08 Měření 4 46600 05:31 39051 05:54 39177 05:28 39377 05:21 42843 07:04 Měření 1 Po čas 944952 05:27 771720 05:22 738559 04:52 769487 04:38 828351 06:59 Měření 4 944952 05:28 771593 05:30 760287 04:55 770679 04:32 846757 07:01


Po 42,5 42,5 42,4 42,5 42,4


42,4 42,5 42,3 42,5 42,4



iter. 4145 9731 9761 7025 8754 6241 9731 2842 9798 6114

iter. 1 9820 6561 5255 8586 1 9662 9085 5584 6379


iter. 4906 9411 3729 8377 4475

Po 42,4 42,4 42,4 42,5 42,4

7739 9688 8594 5043 8925

42,4 42,4 42,4 42,5 42,4


iter. 6726 9257 7250 6917 7549

Měření 3 Po čas 46823 05:31 40976 05:39 38744 05:31 39540 05:08 45978 07:05

iter. 2664 9923 7680 9268 8248

Měření 3 Po čas 944952 05:28 770894 05:26 760287 05:00 770679 04:28 825972 07:01

iter. 1 9622 1369 7363 7609

Měření 3 čas 05:30 06:03 05:57 05:35 06:46

iter. 6830 9506 6781 1877 9016

1786 9784 3721 9921 9862

iter. 8590 9993 8787 8366 9134 1 9858 4552 2059 9014

iter. 8892 9418 907 949 6280

Po 42,3 42,5 42,3 42,4 42,3

8791 9993 9561 5632 8987

XV

ROZVRHOVÁNÍ DÍLENSKÝCH ZAKÁZEK S PODPOROU

Recommend Documents