OPTIMALIZACE DYNAMICKÝCH VÝROBNÍCH DÁVEK OPTIMIZATION OF DYNAMIC LOT SIZES

VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ BRNO UNIVERSITY OF TECHNOLOGY

FAKULTA STROJNÍHO INŽENÝRSTVÍ ÚSTAV AUTOMATIZACE A INFORMATIKY FACULTY OF MECHANICAL ENGINEERING INSTITUTE OF AUTOMATION AND COMPUTER SCIENCE

OPTIMALIZACE DYNAMICKÝCH VÝROBNÍCH DÁVEK OPTIMIZATION OF DYNAMIC LOT SIZES

BAKALÁŘSKÁ PRÁCE BACHELOR'S THESIS

AUTOR PRÁCE

ZBYNĚK DOLEŽAL

AUTHOR

VEDOUCÍ PRÁCE SUPERVISOR

BRNO 2007

RNDR. JIŘÍ DVOŘÁK, CSC.

Strana 5

ZADÁNÍ ZÁVĚREČNÉ PRÁCE (na místo tohoto listu vložte originál a nebo kopii zadání Vaš práce)

Strana 7

LICENČNÍ SMLOUVA (na místo tohoto listu vložte vyplněný a podepsaný list formuláře licenčního ujednání)

Strana 9

ABSTRAKT Tato práce se zabývá vícestupňovým vícevýrobkovým problémem dynamických dávek pro obecné výrobně montážní struktury a více kapacitně omezených zdrojů. Výrobní struktura je reprezentována orientovaným acyklickým grafem, v němž každý uzel může mít několik bezprostředních předchůdců, a/nebo několik bezprostředních následníků. Předpokládáme konečný plánovací horizont složený z diskrétních časových period, známou pevně danou poptávku po jednotlivých výrobcích v každé periodě a časově proměnné nákladové parametry. Cílem je minimalizace celkových nákladů (seřizovacích, výrobních, skladovacích) při dodržení kapacitních omezení a uspokojení poptávky po výrobcích. Cílem práce je implementovat do existujícího programu další genetické operátory, provést a vyhodnotit srovnávací experimenty.

ABSTRACT This work deals with the multi-stage, multi-item lot-sizing problem for general production assembly structures and multiple constrained resources. The product structure can be presented as an acyclic directed network, where every node can have more than one immediate predecessor and/or more than one immediate successor. We suppose a finite planning horizon consisting of discrete time periods, firmly given demands for all items in each period and time-varying cost parameters. The objective of the problem is to minimize the total costs (setup, production, inventory holding) under satisfying the capacity constraints and the demands for items. The purpose of this work is implementing new genetic operators into existing program, performing comparative experiments and evaluating them.

KLÍČOVÁ SLOVA Dynamické dávky, obecná výrobní struktura, více kapacitně omezených zdrojů, genetické algoritmy.

KEYWORDS Dynamic lot sizing, general product structure, multiple constrained resources, genetic algorithms.

Strana 10

Abstrakt

Poděkování Na tomto místě bych rád vyjádřil své poděkování RNDr. Jiřímu Dvořákovi, CSc. za jeho odborné vedení, podněty a teoretické poznatky nezbytné k vyhotovení této diplomové práce.

Strana 11

Obsah: Zadání závěrečné práce...................................................................................................5 Licenční smlouva.............................................................................................................7 Abstrakt............................................................................................................................9 Seznam použitých symbolů...........................................................................................13 1. Úvod................................................................................................................................15 2. Popis problematiky výrobních dávek..........................................................................17 2.1 Plánování výroby...........................................................................................................17 2.2 Výrobní dávky...............................................................................................................17 2.3 Model systému..............................................................................................................17 2.3.1. Plánovací horizont.........................................................................................................18 2.3.2. Poptávka........................................................................................................................18 2.3.3. Výrobní struktura..........................................................................................................18 2.3.4. Účelová funkce..............................................................................................................19 2.4 Omezení zdrojů.............................................................................................................19 3. Matematický model.......................................................................................................21 3.1 Předpoklady matematického modelu............................................................................21 4. Metody řešení.................................................................................................................23 4.1 Genetické algoritmy......................................................................................................23 4.2 Simulované žíhání.........................................................................................................25 4.3 Zakázané hledání...........................................................................................................25 5. Aplikace genetických algoritmů...................................................................................27 5.1 Omezující podmínky.....................................................................................................27 5.2 Implementace genetického algoritmu...........................................................................29 5.2.1. 5.2.2. 5.2.3. 5.2.4.

Datový model......................................................................................................... ...............29 Kapacitně neomezený model......................................................................................... ........29 Algoritmus zachovávající přípustnost z hlediska zásob – posuv dopředu(PZ3)....................30 Algoritmus zachovávající přípustnost z hlediska zásob – posuv dopředu a dozadu (PZ2) 31 5.2.5. Algoritmus zachovávající přípustnost z hlediska zásob – posuv dozadu a dopředu (PZ4). .33

6. 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 7. 7.1 7.2 7.3 7.4 8. 8.1 8.2 8.3

Popis genetických operátorů.........................................................................................35 Operátor křížení „výměna celých sloupců“..................................................................35 Operátor křížení „výměna celých řádků“......................................................................35 Jednobodové křížení ve sloupcích.................................................................................36 Jednobodové křížení v řádcích......................................................................................37 Křížení výměnou podstruktur – uzlu a jeho předchůdců..............................................38 Křížení výměnou podstruktur – uzlu a jeho následníků................................................38 Mutace sousedních period.............................................................................................39 Mutace sousedních výrobků..........................................................................................39 Realizace programu.......................................................................................................41 Hlavní okno programu..................................................................................................41 Submenu „Soubor“........................................................................................................41 Submenu „Konfigurace“...............................................................................................41 Submenu „Výpočet“......................................................................................................42 Porovnání použitých metod..........................................................................................45 Parametry testů..............................................................................................................45 Porovnání způsobů křížení............................................................................................46 Porovnání ruletové a turnajové selekce.........................................................................55

Strana 12

Abstrakt

8.4 Porovnání způsobů mutací............................................................................................56 8.5 Porovnání časových hodnot..........................................................................................58 9. Závěr...............................................................................................................................59 10. Seznam použité literatury.............................................................................................61

Strana 13

SEZNAM POUŽITÝCH SYMBOLŮ

N ... počet výrobků T ... počet časových period K ... počet zdrojů S(i) ... množina bezprostředních následníků výrobku i P(i)... množina bezprostředních předchůdců výrobku i dit ... vnější poptávka po výrobku i v periodě t rij ... počet jednotek výrobku i potřebných k vyrobení jedné jednotky výrobku j sit ... seřizovací náklady výrobku i v periodě t cit ... jednotkové výrobní náklady výrobku i v periodě t hit ... jednotkové skladovací náklady výrobku i v periodě t Ckt ... množství zdroje k dostupné v periodě t fikt ... pevné množství zdroje k nezbytné pro vyrobení výrobku i v periodě t vikt ... množství zdroje k nutné k produkci jednotky výrobku i v periodě t Xit ... množství výrobku i vyrobené v periodě t (výrobní dávka) X‘it ... množství výrobku i vyrobené v periodě t‘ ∆ Xit... množství výrobku i přesunuté z periody t Yit ... binární proměnná označující, zda je dovolena produkce výrobku i v periodě t ( Yit = 1 jestliže X it > 0 , Yit = 0 v opačném případě) Y‘it ... binární proměnná označující, zda je dovolena produkce výrobku i v periodě t‘ ( Y ' it = 1 jestliže Yit ' = 0 ) Iit ... zásoba výrobku i v periodě t; (počáteční zásoba I i 0 a konečná zásoba I iT výrobku i jsou dány) B ... velké kladné číslo PZ2 ... přípustnost z hlediska zásob - posuv dopředu + dozadu PZ4 ... přípustnost z hlediska zásob - posuv dozadu + dopředu VCS … výměna celých sloupců VCR … výměna celých řádků 1bS ... 1-b křížení ve sloupcích 1bR ... 1-b křížení v řádcích VPN … křížení výměnou podstruktur – uzlu a jeho následníků VPP … křížení výměnou podstruktur – uzlu a jeho předchůdců MSP … mutace sousedních period MSVP … mutace sousedních výrobků – předchůdců MSVN … mutace sousedních výrobků - následníků

Strana 15

1. ÚVOD Tato diplomová práce se zabývá řešením problematiky optimalizace dynamických výrobních dávek pomocí genetických algoritmů. Výrobně-montážní systém je vícestupňový, vícevýrobkový s obecnou síťovou strukturou a více kapacitně omezenými zdroji. Cílem je určení takového množství, ve kterém budou výrobky vyráběny a skladovány, aby výrobní, seřizovací a skladovací náklady byly minimální. Touto prací navazuji na práce [6], [7] a [8], jejichž autoři řešili uvedený problém pomocí stochastických heuristických metod (genetické algoritmy, simulované žíhání a zakázané hledání). Ze srovnávacích experimentů vyšly jako nejlepší genetické algoritmy. Mým úkolem bylo tyto algoritmy doplnit o další operátory křížení a provést vyhodnocení. Druhá kapitola obsahuje popis problematiky optimalizace výrobních dávek. Třetí kapitola obsahuje matematickou formulaci tohoto problému, předpoklady a vzorce. Čtvrtá kapitola obsahuje stručný přehled metod řešení a popis problematiky genetických algoritmů. Pátá kapitola popisuje algoritmy PZ2 a PZ4, které byly použity v této práci, omezující podmínky a implementaci genetického algoritmu. Šestá kapitola obsahuje popis zkoumaných genetických operátorů křížení a mutace. V sedmé kapitole je stručně popsán program a práce s ním. V osmé kapitole jsou popsány experimenty a jejich vyhodnocení. Poslední devátá kapitola obsahuje závěr, kde jsem shrnul obsah práce a zjištěné výsledky.

Strana 17

2. POPIS PROBLEMATIKY VÝROBNÍCH DÁVEK 2.1

Plánování výroby

Plánování výroby probíhá na základě objednávek od zákazníka, určuje druh a množství výrobků které mají být vyráběny a jejich časové rozvržení. Cíle plánování: ● externí – např. termín zhotovení, množství vyrobeného zboží, jeho kvalita, stanovené náklady na výrobu. ● interní – dodržení termínů výroby, maximální využití zdrojů, materiálová dostupnost, rozpracování výrobků

V současné době se za nejdůležitější cíle pokládá: ● ● ● ●

2.2

vysoké vytížení strojů co nejnižší skladovací zásoby minimální reakční doba na požadavky výroby minimální průběžné časy

Výrobní dávky

Výrobní dávka je určité množství výrobků, které jsou zároveň zadávány do výroby nebo opouští výrobu, jsou upravovány v těsných časových intervalech nebo současně. Zároveň je přesně dané místo pracoviště, vynaložené náklady na přípravu a ukončení výrobu jsou konstantní. Výrobní dávka je v průběhu výroby i při převodu na sklad nebo mezisklad evidována jako celek, je společně vydáván materiál a polotovary. Rozdíl mezi výrobní dávkou a sérií je ten, že série se skládá z řady výrobků jednoho provedení a je tvořena výrobními dávkami. Čím větší jsou výrobní dávky, tím menší jsou náklady na přípravu a dokončení výroby, jednodušší řízení výroby a větší produktivita práce, ale na druhé straně se také zvyšují skladovací náklady, podnikový majetek(obratový kapitál). Cílem optimalizace výrobních dávek je tedy stanovení takových výrobních dávek, aby celkové náklady na výrobu byly minimální a současně byla splněna poptávka ze strany zákazníka. Podrobnější pojednání viz [6].

2.3

Model systému

V minulosti vzniklo mnoho modelů pro různé typy problémů výrobních dávek, se kterými se můžeme setkat v průmyslové praxi. Tyto modely můžeme rozdělit podle: ● ● ● ● ● ●

plánovacího horizontu – konečný, nekonečný poptávky – pevná, dynamická počtu výrobků počtu omezených zdrojů počtu výrobních stupňů struktury montážního systému(lineární, čistě montážní, obecná montážní struktura)

V této práci se zaměříme na obecný dynamický problém výrobních dávek při omezených

Strana 18

2. Popis problematiky výrobních dávek

zdrojích. Výrobně-montážní systém je tedy vícestupňový, vícevýrobkový, s obecnou síťovou strukturou, ve které každý stupeň může mít více bezprostředních předchůdců i následníků. Poptávka, výrobní, skladovací a seřizovací náklady se v čase mění.

2.3.1. Plánovací horizont Plánovací horizont je časové období, ve kterém se plánuje určitá činnost, je daný poptávkou. Existují dva základní typy: ● ●

konečný – dělí se do period a v každé je obecně jiná poptávka nekonečný – poptávka se v čase nemění

2.3.2. Poptávka Poptávka je objem a druh zboží, které zákazník požaduje. Podle toho, jestli se v čase mění, rozeznáváme stacionární a dynamickou poptávku

2.3.3. Výrobní struktura Pohyb zboží je možné znázornit pomocí orientované síťové struktury. Výrobní struktura může být: jednoúrovňová – síť obsahuje pouze izolované uzly víceúrovňová – alespoň jedna dvojice uzlů je spojena hranou. Hrana (i, j) existuje, jestliže výrobek i je nutný k sestavení výrobku j. Počet jednotek výrobků i nutných k sestavení jedné jednotky výrobku j určuje ohodnocení této hrany. ● ●

Víceúrovňové struktury se dále dělí na: ● sériové – každý uzel má jednu vstupní hranu (kromě počátečního uzlu) a jednu výstupní hranu (kromě posledního uzlu). Viz obr. 1.

Obr. 1 : Sériová struktura ● čistě montážní (stromové) – každý uzel má jednu vstupní hranu (s výjimkou počátečního uzlu) a může mít jednu nebo více výstupních hran - viz obr. 2.

2. Popis problematiky výrobních dávek

Strana 19

Obr. 2 : Stromová struktura ● obecně montážní – každý uzel může mít víc než jednu vstupní a víc než jednu výstupní hranu - viz obr. 3.

Obr. 3 : Obecná montážní struktura

2.3.4. Účelová funkce Účelová funkce se používá k vyhodnocení údajů získaných během výpočtu, většinou odpovídá nákladům(seřizovací, výrobní, skladovací).

2.4

Omezení zdrojů

Jestliže nejsou dána žádná kapacitní omezení, jedná se o model s neomezenou kapacitou. Pokud jsou kapacitní omezení dána, jedná se o kapacitní model. Kapacita může být jednoznačně dána, nebo nějakým způsobem určena. Kapacita je obvykle určena na úrovni volby aktivit nebo úrovni celkového plánování.

Strana 21

3. MATEMATICKÝ MODEL 3.1

Předpoklady matematického modelu •

Výrobní struktura je popsána orientovaným acyklickým grafem, kde každý uzel může mít jednoho nebo více bezprostředních předchůdců, ale i jednoho nebo více bezprostředních následníků. Uzly jsou číslovány tak, že číslo bezprostředního předchůdce je větší než číslo aktuálního uzlu, a číslo bezprostředního následníka je menší než číslo aktuálního uzlu.

•

Výrobní časy jsou považovány za nulové

•

Plánovací horizont je konečný s T časovými periodami

•

Je zadána dynamická vnější poptávka po N výrobcích

•

Produkce výrobků je okamžitá, bez ohledu na vyráběné množství

•

Skluzy při uspokojování poptávky po výrobcích nejsou povoleny

•

Výrobní, seřizovací a skladovací náklady se s časem mění

•

Jsou dány výrobní kapacity pro všechny zdroje

Cílem řešení optimalizace dynamických výrobních dávek je určit takové výrobní dávky, aby suma seřizovacích, výrobních a skladovacích nákladů výrobního systému byla minimální a zároveň aby byla splněna poptávka a všechna kapacitní omezení. Tento úkol lze formulovat jako následující model smíšeně celočíselného programování: Minimalizovat

F ( Y , X, I ) =

N T

∑ ∑ ( sit Yit + cit X it + i= 1 t = 1

hit I it )

(1)

za podmínek:

I i , t − 1 + X it − I it = d it + N

∑ (f i= 1

ikt

∑

rij j∈ S (i )

Yit + vikt X it ) ≤ C kt X it ≤ B Yit , I it , X it ≥ 0, Yit ∈ { 0, 1} ,

X jt ,

i = 1, , N, t = 1, ,T

k = 1, , K, t = 1, ,T i = 1, , N, t = 1, ,T i = 1, , N, t = 1, ,T i = 1, , N, t = 1, ,T

(2) (3) (4) (5) (6)

Účelová funkce (1) vyjadřuje celkové seřizovací, výrobní a skladovací náklady. Omezení (2) zaručuje rovnováhu zásob. Omezení (3) je podmínka kapacitní přípustnosti. Omezení (4) zajišťuje, že

Strana 22

3. Matematický model

seřizovací náklady sit jsou započítány, když X it je kladné. Podmínka nezápornosti zásob I it v (5) zaručuje, že poptávka bude vždy uspokojena. Tento problém je možné řešit metodami operační analýzy, vzhledem k velké složitosti je ale výhodnější použít heuristické metody, které budou popsány v následující kapitole.

Strana 23

4. METODY ŘEŠENÍ V této kapitole bude uveden krátký přehled heuristických metod řešení optimalizace dynamických výrobních dávek. Slovo heuristika pochází z řeckého heuriskein, což znamená nalézt, objevit. Heuristické metody se používají k hledání takových řešení, která jsou blízko optimálnímu řešení pomocí intuitivních postupů a v přijatelném čase. Heuristické metody mají tu výhodu, že je možné pomocí nich řešit úlohy s velkým množstvím dat nebo složitou strukturou, které by pomocí exaktních metod nebylo možné v přijatelném čase vyřešit. Hlavní nevýhoda je, že není zaručeno nalezení globálního optima ani chyba výpočtu.

4.1

Genetické algoritmy

Genetický algoritmus je heuristický postup, který se snaží nalézt řešení pomocí aplikací poznatků evoluční biologie. Za zakladatele evoluční biologie je považován Charles Darwin, který jako první uvedl evoluční teorii. Stručný popis genetického algoritmu: 1) 2) 3) 4) 5)

Vytvoření počáteční množiny prvků - jedinců(populace) Výběr nejlepších jedinců(rodičů pro křížení) Křížením těchto rodičů vzniknou potomci(pro novou populaci) Náhodná mutace potomků Vytvoření nové populace

Kroky 2 - 5 se opakují dokud není nalezeno optimální řešení, nebo časové omezení, atd. Podobně jako v Darvinově evoluční teorii přežívají jen nejlépe vybavení jedinci, i genetický algoritmus pracuje tak, že data s nejlepším ohodnocením jsou vybírána k dalším operacím. Vlastnosti jedince jsou zaznamenány v chromozomech. Ty se skládají z genů. Datový model Aby mohl genetický algoritmus řešit zkoumaný problém, je nutné tento problém matematicky vyjádřit. K zápisu se nejčastěji používá vektor obsahující například binární hodnoty, tedy takové, které mohou nabývat dvou hodnot, 0 nebo 1. Hodnota 1 může napříkad znamenat, že se daný výrobek vyrábí, 0 může znamenat, že se nevyrábí. Vytvoření počáteční množiny jedinců(populace) Na začátku běhu programu se vytvoří počáteční množina dat - rodičů, jinými slovy populace. Jednotlivé geny jsou inicializovány náhodnými hodnotami. Výběr nejlepších jedinců(rodičů pro křížení) Každý jednotlivý jedinec je charakterizován kvalitou své genové výbavy, neboli fitness. V této práci jsou to například mj. výrobní náklady. Na správné implementaci této funkce závisí výsledky celého genetického algoritmu. Výběr nejlepších prvků se nazývá selekce. Existují 2 základní typy selekce: ●

ruletová – pravděpodobnost výběru jedince pro vytvoření nové populace je přímo úměrná hodnotě jeho fitness. Graficky to lze znázornit na ruletě, kde jednotlivé výseče mají na rozdíl od klasické rulety různou plochu, právě podle hodnoty fitness. Čím vyšší hodnotu fitness má jedinec, tím má jeho výseč větší plochu a tím větší je pravděpodobnost, že bude vybrán k selekci.

Strana 24 ●

4. Metody řešení

turnajová – vybere se náhodně několik jedinců a z nich se dále vybírá podle hodnoty fitness.

Křížení Křížení se používá k vytvoření nových jedinců z rodičů vybraných selekcí, probíhá s určitou pravděpodobností. Základní typy křížení: ●

jednobodové – oba chromozomy rodičů se rozdělí na 2 části o náhodné velikosti, další postup viz obr.4. Výměna probíhá od dělicího bodu do konce.

Obr. 4 : Jednobodové křížení

vícebodové – podobné jako jednobodové, chromozom se rozdělí na víc částí a výměna probíhá od prvního dělicího bodu do druhého atd. ● uniformní – křížení probíhá podle předem vytvořené masky o velikosti shodné s chromozomem jedince, s náhodně inicializovanými hodnotami. Např. při binární reprezentaci 0 může znamenat, že odpovídající gen nebude vyměněn, 1 může znamenat, že odpovídající gen bude vyměněn. ●

4. Metody řešení

Strana 25

Mutace Mutace znamená, že určité geny jedinců se změní. Používá se proto, aby byla zaručena určitá rozmanitost populace a genetický algoritmus neuvázl v lokálním extrému. Pravděpodobnost je velmi malá, méně než 1 %.

4.2

Simulované žíhání

Tento algoritmus napodobuje proces žíhání - tuhnutí materiálu v horké lázni. Nejprve je těleso zahřáto na vysokou teplotu, atomy a molekuly jsou náhodně uspořádány v prostoru. Ochlazováním se snižuje vnitřní energie tělesa, atomy a molekuly se dostávají do rovnovážné polohy. Metoda simulovaného žíhání simuluje změny energie systému, dokud není dosaženo ustáleného stavu. Analogie mezi procesem žíhání a prvky optimalizačního problému je uvedena v tabulce 1. Termodynamická simulace stav systému energie změna stavu teplota zmrazený stav

Kombinatorická optimalizace přípustné řešení hodnota účelové funkce přechod k sousednímu řešení řídící parametr heuristické řešení

Tabulka 1: Analogie mezi procesem žíhání a prvky optimalizačního problému

V průběhu výpočtu metodou simulovaného žíhání jsou dovoleny i kroky směřující k horšímu řešení. Frekvence těchto kroků je řízena pravděpodobnostní funkcí. Tato funkce vyjadřuje zákony termodynamiky, podle nichž při teplotě t je pravděpodobnost růstu energie o δE dána vztahem:

 − δE P( δ E ) = exp   k⋅t 

(7)

kde E je energie [J], t je teplota [K], a k je Boltzmannova konstanta [1.38 10-23 J.K-1]. V Metropolisově algoritmu se při změně stavu systému vypočítá odpovídající změna energie. Jestliže dojde k poklesu energie, systém přejde do nového stavu. Jestliže dojde k vzrůstu energie, systém přejde do nového stavu s jistou pravděpodobností danou vzorcem (7).

4.3

Zakázané hledání

Metoda zakázaného hledání je založena na horolezeckém algoritmu. Ten pracuje na principu náhodného prohledávání okolí určitého řešení. Lokální minimum, které je takto nalezeno, se dále použije jako bod pro nové hledání. Tento algoritmus se snaží zabránit uváznutí v lokálním optimu zavedením krátkodobé a dlouhodobé paměti. Krátkodobá paměť (tabu list) Krátkodobá paměť obsahuje inverzní transformace k použitým transformacím v předcházejících iteracích. Jestliže je transformace obsažena v tabu listu, potom se nemůže použít k sestrojení okolí aktuálního řešení. Při inicializaci algoritmu je tabu list prázdný, po každé iteraci se do tabu listu dodá transformace, která poskytla lokální optimální řešení.

Strana 26

4. Metody řešení

Dlouhodobá paměť Dlouhodobá paměť pracuje tak, že znevýhodňuje (penalizuje) ty transformace, které sice nejsou obsaženy v tabu listu, ale často se vyskytovaly v předcházející historii algoritmu.

Strana 27

5. APLIKACE GENETICKÝCH ALGORITMŮ 5.1

Omezující podmínky

Při výpočtu je možné použít některé omezující podmínky. Rovnice (1)-(6) obsahují tyto základní typy omezení: ●

zajišťující rovnováhu stavu zásob mezi periodami

●

zajišťující kapacitní přípustnosti

Přístup zachovávající přípustnost jen z hlediska kapacit Tuto metodu zpracoval Král [6] podle algoritmu Xieho [5]. Xieho algoritmus provádí pouze přesuny dozadu, tzn. výroba z periody t, u které byla překročena kapacita, se přesouvá do předchozí periody t – 1. Postupně se prochází jednotlivé periody v pořadí t = T, T-1, …, 1. V každé periodě se vypočte kapacita CNkt zdroje k nutná k produkci všech výrobků i v periodě t, zatížení zdroje ρkt a zbývající kapacit CRkt zdroje k v periodě t podle následujících vzorců:

CN kt =

ρ

N

∑ (f i= 1

kt

kit

Yit + v kit X it ) ,

= CN kt / C kt ,

CR kt = C kt − CN kt ,

k = 1,..., K, t = 1,..., T

k = 1,..., K, t = 1,..., T

(8) (9)

k = 1,..., K, t = 1,..., T

(10)

V této práci bude použita metoda zachovávající přípustnost z hlediska zásob podle [3], [6] a [7]. Přístup zachovávající přípustnost jen z hlediska zásob Přesouvá se jen takové množství výrobků, které nenaruší rovnováhu zásob (2). Kapacitní nepřípustnost je dána vztahem (11):

  N  β ∑ ∑  max  0, ∑ ( f ikt Yit + vikt X it ) − C kt   k = 1 t= 1   i= 1  K

T

Jsou dvě možnosti posuvu: ●

posuv dozadu – výroba se přesouvá do předchozí periody t – 1

●

posuv dopředu – výroba se přesouvá do následující periody t + 1

Posuv dozadu

2

(11)

Strana 28

5. Aplikace genetických algoritmů

Při posuvu dozadu se provádí kontrola jednotlivých period (v pořadí t = T, T – 1, ,…, 2). V každé periodě se vypočítá zatížení všech zdrojů ρkt . Vybere se ten zdroj, jehož kapacita je překročena nejvíce. Postupně se přesouvá produkce výrobků (v pořadí i = N, N – 1,…,1). Aby byla splněna rovnice rovnováhy zásob (2), musí platit:

X it − ∆ X it −

∑ r (X

j∈ S ( i )

ij

jt

− ∆ X jt ) + I i ,t − 1 + ∆ I i ,t − 1 − I it = d it

(12)

i = 1,..., N , t = 1,..., T

za podmínek:

0 ≤ ∆ X it ≤ X it I i ,t − 1 + ∆ I i ,t − 1 ≥ 0

Potom množství ∆Xit, které je možné přesunout se vypočítá podle následujícího vztahu:

    ∆ X it = min  X it ,− CRkt / v kit , min   I j ,t − 1 + ∆ X jt − j∈ P ( i )    

    r jm ∆ X mt  / r ji   ∑ m∈ S ( j )   m< i  

(13)

i = 1,..., N , t = 1,..., T Po úpravě čerpání k-tého zdroje v dané periodě t je nutné přepočítat zásoby v periodě t – 1.

I i ,t − 1 = I i ,t − 1 + ∆ X it −

∑

rij ∆ X jt ,

i = 1,..., N

j∈ S ( i )

(14)

Posuv dopředu Kontrola jednotlivých period se provádí v pořadí (t = 1,2,..,T – 1). Výpočet a výběr přetíženého zdroje je stejný jako při posuvu dozadu, ale přesun produkce výrobků se provádí v opačném pořadí (i = 1,2,…, N). Aby byla splněna rovnice rovnováhy zásob (2), musí platit:

X it − ∆ X it − za podmínek:

∑ r (X

j∈ S ( i )

ij

jt

− ∆ X jt ) + I i ,t − 1 − ∆ I i ,t − I it = d it

(15)

i = 1, , N , t = 1,..., T 0 ≤ ∆ X it ≤ X it I it + ∆ I it ≥ 0

Potom množství ∆Xit, které lze přesunout se vypočítá podle následujícího vztahu:

 ∆ X it = min  X it ,− CR kt / v kit , I it + 

∑ ( )r

j∈ S i

ij

 ∆ X jt  

(16)

i = 1,..., N , t = 1,..., T Podobně jako u posuvu dozadu, musí se i zde po úpravě čerpání k-tého zdroje v dané periodě t


Strana 29

přepočítat zásoby. Na rozdíl od posuvu dozadu, kde se přepočet zásob prováděl v periodě t – 1, zde se přepočet provádí v periodě t.

I i ,t = I i ,t − ∆ X it +

5.2

∑

rij ∆ X jt ,

j∈ S ( i )

i = 1,..., N

(17)

Implementace genetického algoritmu

5.2.1. Datový model Protože plánovací horizont výroby se skládá z určitého počtu diskrétních časových period, jako datový model pro jeden prvek populace je použita matice Y, jejíž řádky odpovídají výrobkům a sloupce periodám. příklad.: 5 výrobků, 4 časové periody(zobrazení jednoho prvku populace):

Obr. 5 : Zobrazení datového modelu hodnota 0: výrobek se nevyrábí hodnota 1: výrobek se vyrábí Tomu odpovídá obecný zápis:

Y g, j

 Y11g , j ,..., Y1Tg , j   g, j   Y21 ,..., Y2gT, j  =      Y g , j ,..., Y g , j  NT   N1

j = 1,2,…,MAXPOP, g = 1,2,…, MAXGEN

Chromozom můžeme také vyjádřit jako následující posloupnost: Y = (Yit, i = 1,2,…, N; t = 1, 2,…, T) 5.2.2. Kapacitně neomezený model V případě kapacitně neomezeného modelu uvažujeme proměnné Xit, Iit jako závislé na Yit. Jejich hodnoty tedy mohou být vypočteny z Yit a známých parametrů problému. Pro kapacitně neomezený problém dynamických výrobních dávek existuje optimální řešení pro které platí podmínka (18). Tato

Strana 30


vlastnost se nazývá „zero switch“.

X it I i , t − 1 = 0

(18)

Výrobní dávky Xit jsou vypočteny podle následujících pravidel: 1. Jestliže Yit = 0 , pak X it = 0 . 2. Jestliže Yiτ 1 = 1 , Yiτ 2 = 1 , τ 1 < τ 2 ≤ T , a Yit = 0 pro τ 1 < t < τ 2 (nebo Yit = 0 pro τ 1 < t < T a τ 2 = T + 1) potom

X iτ 1 =

τ 2 −1

∑

t= τ 1

d +  it 

 r X ∑ ij jt  j∈ S (i ) 

(19)

Zásoby I it jsou určeny rovnicí

I it = I i , t − 1 + X it − d it −

∑

rij X jt

j∈ S ( i )

(1 ≤

t ≤ T)

(20)

5.2.3. Algoritmus zachovávající přípustnost z hlediska zásob – posuv dopředu(PZ3) Odstraň resp. sniž kapacitní nepřípustnosti pro všechny zdroje následovně. Začni v periodě 1 a pokračuj v pořadí t = 1,2,…, T – 1. Pro každou periodu vypočítej zatížení zdroje ρkt podle (9). Jestliže pro všechny zdroje je ρkt <= 1, pokračuj na další periodu, jinak vyber zdroj s největší hodnotou ρkt a vypočítej hodnotu CRkt (10). Dokud platí CRkt < 0 a dokud je možné něco přesouvat, přesuň část nebo celou produkci výrobku i do následující periody t + 1 v pořadí i = 1, 2,…, N. Potom proveď příkazy:

X it = X it − ∆ X it X i ,t + 1 = X i ,t + 1 + ∆ X it Yi ,t + 1 = 1

kde množství ∆Xit urči dle vztahu (16). jestliže ∆Xit < Xit potom:

CRkt = CRkt + v kit ∆ X it jestliže ∆Xit = Xit potom:

Yi ,t = 0


Strana 31

CRkt = CRkt + f kit + v kit X it Po úpravě čerpání k-tého zdroje v dané periodě t je nutné přepočítat zásoby. Na rozdíl od posuvu dozadu, kde se přepočet zásob prováděl v periodě t – 1, zde se přepočet provádí v periodě t – viz (17). 5.2.4. Algoritmus zachovávající přípustnost z hlediska zásob – posuv dopředu a (PZ2)

dozadu

1. Náhodně vygeneruj počáteční populaci oldpop = { Y0,j, j = 1,2,…, MAXPOP}. 2. Pokud je počet generací menší nebo roven MAXGEN a počet přijatých prvků je menší než zadaný počet prvků a čas je menší než zadaný čas, proveď následující kroky, v opačném případě ukonči algoritmus a vypiš řešení. 2.1 Vypočítej počáteční řešení bez ohledu na kapacitní omezení. Urči hodnotu Xit odpovídající hodnotě Yit způsobem popsaným v předchozí kapitole. 2.2 Oprav hodnoty Yit a Xit tak, aby byla splněna rovnice rovnováhy zásob (2). Yit = 0 pro t = 1, 2,…,τ1 – 1, Yiτ 1 = 1 kde

 τ 1 = min  τ | I i 0 <  kde

Dit = d it +

 Dit  t= 1  τ

∑

(21)

∑

rij D jt j∈ S (i )

X it = 0 pro t = 1, 2, ..., τ 1 − 1, a X iτ 1 =

  d it +  t= 1 

τ 2−1

∑

 rij X jt  − I i 0 j∈ S ( i ) 

∑

(22)

kde τ 2 = min{ t | t > τ 1, Yit = 1} . Předpokládáme, že počáteční zásoby Ii0 = 0. 2.3 Pro všechny výrobky a všechny periody urči zásoby Iit odpovídající hodnotám Xit, jak již bylo uvedeno ve vztahu (20)

2.4 Proveď posuv dopředu(viz kapitola 5.2.3). Odstraň resp. sniž kapacitní nepřípustnosti pro všechny zdroje následovně. Začni v periodě T a pokračuj v pořadí t = T, T – 1, …, 2. Pro každou periodu vypočítej zatížení zdroje ρkt – viz vztahy (8), (9). Jestliže pro všechny zdroje je ρkt <= 1, pokračuj na další periodu, jinak vyber zdroj s největší hodnotou ρkt a vypočítej hodnotu CRkt dle (10). Dokud platí CRkt < 0 a dokud je možné něco přesouvat tak přesuň část nebo celou produkci výrobku i do předcházející periody t – 1 v pořadí i = N, N – 1,…, 1: Potom proveď příkazy:

Strana 32


X it = X it − ∆ X it X i ,t − 1 = X i ,t − 1 + ∆ X it Yi ,t − 1 = 1 kde množství ∆Xit určíme podle 13. jestliže ∆Xit < Xit potom:

CRkt = CRkt + v kit ∆ X it jestliže ∆Xit = Xit potom:

Yi ,t = 0 CRkt = CRkt + f kit + v kit X it Po úpravě čerpání k-tého zdroje v dané periodě t je nutné přepočítat zásoby v periodě t – 1, toto proveď dle vztahu (14). 2.5 Urči hodnotu účelové funkce odpovídající hodnotám Y, X, I.

COSTP ( Υ , Χ , Ι ) =

N

T

∑ ∑ ( s it Yit + c it i= 1 t= 1

X it + hit I it ) + β

K

T

∑ ∑ [ max{ 0, − CR } ]

2

kt

k= 1 t= 1

(23)

3. Vytvoř novou populaci newpop = {Y1,j, j = 1,2,…,MAXPOP} v generaci g + 1. 3.1 K příslušným hodnotám účelové funkce urči odpovídající hodnoty fitness fit(Y0,j) podle vztahů (24).

(

fit Υ

0, j

)=

(

MAXPOP

Max COSTP Υ i= 1

0 ,i

)+ ε

(

− COSTP Υ

0, j

)

(24)

j = 1,2,…, MAXPOP kde COSTP(Y) = COSTP(Y,X,I) a ε je kladná konstanta. 3.2 Nejhoršího jedince nahraď nejlepším jedincem z předcházející generace. 3.3 Selekcí vyber Y0,j1, Y0,j2 z původní množiny oldpop.Pravděpodobnost výběru Y0,j lze určit podle vztahu (25).

(

pr Υ

0, j

)=

(

fit Υ MAXPOP

∑

i= 1

0, j

(

fit Υ

) 0,i

)

,

j = 1,2,..., MAXPOP

(25)

3.4 Proveď mutaci vybraných rodičů Y0,j1, Y0,j2. Pravděpodobnost mutace je označena jako pm. Při mutaci postupně procházej jednotlivé pozice chromozomu. Pokud hodnota náhodného


Strana 33

čísla bude menší než pravděpodobnost pm, invertuj pozici chromozomu – vzorce (26) a (27). '0, j it

Y

 Yit0, j , =  0, j  Y it , Y

0, j it

 0, =   1,

r < 1 − pm , r < pm ,

j = j1 , j 2

jestliže Yit0, j = 1 jestliže Yit0, j = 0

(26)

(27)

3.5 Proveď křížení vybraných rodičů Y0,j1, Y0,j2. Pravděpodobnost křížení je označena jako pc. Můžeme si zvolit jednobodové, dvoubodové nebo uniformní křížení. 3.6 Do populace newpop přidej nové chromozomy Y1,j1, Y1,j2. 3.7 Pokud je počet nově vytvořených chromozomu roven MAXPOP, jdi na krok 4, jinak jdi na krok 3.2. 4. Zvyš počet generací o jednu, překopíruj množinu newpop do oldpop, jdi zpět na krok 2. 5.2.5. Algoritmus zachovávající přípustnost z hlediska zásob – posuv dozadu a dopředu (PZ4) Algoritmus provádějící posuvy dozadu a dopředu je podobný algoritmu provádějící přesuny dopředu a dozadu. Rozdíl je jen v tom, že v kroku 2.4 provedeme nejdříve posuvy dozadu a poté posuvy dopředu.

Strana 35

6. POPIS GENETICKÝCH OPERÁTORŮ Úkolem této práce bylo přidat nové genetické operátory křížení: výměna celých sloupců, výměna celých řádků, jednobodové ve sloupcích, jednobodov v řádcích, křížení výměnou podstruktur – uzlu a jeho předchůdců, křížení výměnou podstruktur – uzlu a jeho následníků, mutace sousedních struktur, mutace sousedních prvků. Další operátory viz [2].

6.1

Operátor křížení „výměna celých sloupců“

V dalším textu bude používána zkratka VCS. Operátor křížení byl popsán v podkapitole 4.1 na Obr.4 Princip VCS je znázorněn na příkladu – viz obr. 6, kde jsou zobrazeny 4 matice Y.

Obr. 6 : Křížení VCS jednobodové

6.2

Operátor křížení „výměna celých řádků“ V dalším textu bude používána zkratka VCR, princip je znázorněn na příkladu – viz obr. 7.

Strana 36

6. Popis genetických operátorů

Obr. 7 : Křížení VCR jednobodové

6.3

Jednobodové křížení ve sloupcích

V každém sloupci se náhodně vygeneruje dělicí bod a příslušné části sloupců se vymění. Princip je znázorněn na příkladu – viz obr. 8. Dělící body jsou znázorněny šedou barvou.


Strana 37

Obr. 8 : Jednobodové křížení ve sloupcích

6.4

Jednobodové křížení v řádcích

Podobné jako jednobodové křížení ve sloupcích, ale výměna probíhá v řádcích. Princip je znázorněn na příkladu – viz obr. 9. Dělící body jsou znázorněny šedou barvou.

Obr. 9 : Jednobodové křížení v řádcích

Strana 38

6.5


Křížení výměnou podstruktur – uzlu a jeho předchůdců

Princip je znázorněn na příkladu – viz obr. 11. V každém sloupci se náhodně určí uzel - je znázorněn šedou barvou. Provede se výměna pro tento uzel a všechny jeho předchůdce. Jestliže je uzel a předchůdce uzlu b, je výrobek a nutný k výrobě výrobku b. Viz 2 Výrobní struktura. Čísla uzlů odpovídají číslům řádků (číslováno shora). Na obr. 10 je znázorněna výrobní struktura uzlů a předchůdců. Uzly jsou ve zvýrazněných kružnicích, předchůdci jsou v kruzích na šedém pozadí.

Obr. 10 : Výrobní struktura

Obr. 11 : Křížení výměnou podstruktur – uzlu a jeho předchůdců

6.6

Křížení výměnou podstruktur – uzlu a jeho následníků

Křížení výměnou podstruktur – uzlu a jeho následníků je podobné křížení výměnou podstruktur – uzlu a jeho předchůdců, ale výměna probíhá pro vybraný uzel a následníky. Princip je znázorněn na příkladu – viz obr. 13.


Strana 39

Uzel je znázorněn šedou barvou. Jestliže je uzel a následník uzlu b, je výrobek b nutný k výrobě výrobku a. Viz 2 Výrobní struktura. Na obr. 12 je znázorněna výrobní struktura uzlů a následníků. Uzly jsou ve zvýrazněných kružnicích, následníci jsou v kruzích na šedém pozadí.

Obr. 12 : Výrobní struktura

Obr. 13 : Křížení výměnou podstruktur – uzlu a jeho následníků

6.7

Mutace sousedních period

Každý řádek se s pravděpodobností pm vybere k mutaci, ktera spočívá v tom, že se v tomto řádku zvolí náhodně pozice t a provede se následujicí operace: porovnají se hodnoty y na pozicích t-1, t a t + 1; pokud je hodnota yit odlišná právě od jedné sousední hodnoty, provede se jejich záměna; pokud je hodnota yit odlišná od obou sousedních hodnot, náhodně se zvolí jedna z nich a s ní se provede záměna.

6.8

Mutace sousedních výrobků

Mutace sousedních výrobků je podobná křížení s výměnou podstruktur – viz kapitola 6.5 a 6.6, s tím rozdílem, že místo výměny prvků probíhá invertování prvků matice Y.

Strana 40


Strana 41

7. REALIZACE PROGRAMU Program se jmenuje Optimalizace.exe, byl vytvořen pomocí Borland Delphi 6 s využitím podpory objektově orientovaného programování.

7.1

Hlavní okno programu Vzhled programu po spuštění je na obr. 14

Obr. 14 : Vzhled programu po spuštění Hlavní menu obsahuje položky „Soubor“, „Konfigurace“ a „Výpočet“

7.2

Submenu „Soubor“

Submenu „Soubor“ obsahuje položky pro otevření textového souboru s zadáním, generování zadání, ruční vytvoření zadání, editování zadání, ukládání zadání a výsledků a příkaz pro ukončení programu.

7.3

Submenu „Konfigurace“

Na Obr. 15 je ukázka dialogu Konfigurace. Zde je možné nastavit parametry genetického algoritmu.

Strana 42

7. Realizace programu

Obr. 15 : Dialog pro konfiguraci programu

7.4

Submenu „Výpočet“

Na obr. 16 je ukázka dialogu pro nastavení parametrů výpočtu a jeho spuštění. Při použití cyklického výpočtu je nutné zadat jméno souboru – slouží pro získání aktuálního adresáře pro automatické ukládání výsledků. Přidal jsem funkci pro automatické ukládání výsledků do textového souboru. Jména souborů se generují automaticky na zadaném jménu souboru: 1.txt, 2.txt, … Z těchto souborů se vypočítají průměrné hodnoty sledovaných údajů a uloží se do souboru PrumerneHodnoty.txt

7. Realizace programu

Strana 43

Obr. 16 : Dialog pro nastavení a spuštění výpočtu

Strana 45

8. POROVNÁNÍ POUŽITÝCH METOD Označení příkladu v hierarchii adresářů(složek) je výhodné umístit co nejníže, protože při ukládání výsledků do textových souborů se mezi nimi často přepíná.

8.1

Parametry testů Při testech byly použity tyto způsoby ukončení: jednoduché ukončení – délka testu závisí na nastaveném počtu generací, testy byly prováděny pro 500 a 5000 generací. ● ukončení po nalezení prvního přípustného řešení ● ukončení po 1s ● ukončení po 10s ●

Při jednoduchém ukončení byly sledovány tyto hodnoty: ● ● ● ● ●

nejlepší hodnoty účelové funkce průměrné hodnoty účelové funkce nejkratší doba výpočtu - všechny hodnoty měřeny v sekundách průměrná doba výpočtu - všechny hodnoty měřeny v sekundách průměrný počet přípustných řešení Při ukončení po nalezení prvního přípustného řešení byly sledovány tyto hodnoty:

● ● ● ●

nejlepší hodnoty účelové funkce průměrné hodnoty účelové funkce průměrný počet prozkoumaných generací Průměrný počet prozkoumaných prvků populace

Při ukončení po 1s a 10s byly sledovány tyto hodnoty: ● ● ●

nejlepší hodnoty účelové funkce průměrné hodnoty účelové funkce průměrný počet přípustných řešení Všechny časové údaje byly měřeny v sekundách. Při testech byly použity tyto parametry: velikost populace: 30 pravděpodobnost křížení: 0,60 pravděpodobnost mutace: 0,033 stará populace s výjimkou nejlepšího elementu je nahrazena novou populací bez jejího nejhoršího elementu ● ● ● ●

Každý výpočet byl pro 1 příklad a 1 metodu zopakován 20-krát. Přehled testovaných případů: ● algoritmy:

Strana 46

8. Porovnání použitých metod

zachovávající přípustnost z hlediska zásob – posuv dopředu a dozadu (PZ2) zachovávající přípustnost z hlediska zásob – posuv dozadu a dopředu (PZ4) ● typy křížení: ● výměna celých sloupců(VCS) ● výměna celých řádků(VCR) ● normální(původní) křížení ● 1-b křížení ve sloupcích ● 1-b křížení v řádcích ● křížení výměnou podstruktur – předchůdců ● křížení výměnou podstruktur – následníků ● typy selekce: ● ruletová ● turnajová ● typy mutací ● obyčejná(původní) ● mutace sousedních period ● mutace sousedních výrobků – předchůdců ● mutace sousedních výrobků – následníků ● ●

Testy byly prováděny na příkladech č.3 a 7. Popis příkladů je uveden v tabulce 2 příklad č.3

příklad č. 7

Počet výrobků N

7

10

Počet period T

6

4

Počet zdrojů K

1

2

Tabulka 2: Charakteristika příkladů č. 3 a 7

8.2

Porovnání způsobů křížení příklad 3

Typ křížení Normální 1 bodové VCR 1 bodové VCS 1 bodové Normální 2 bodové VCR 2 bodové VCS 2 bodové Normální uniformní VCR uniformní VCS uniformní 1-b křížení v řádcích 1-b křížení ve sloupcích VPP normální 2 b VPN normální 2 b

PZ2 10029 10029 10029 10029 10029 10029 10029 10029 10029 10029 10029 10029 10029

příklad 7 PZ4 10029 10029 10029 10029 10029 10029 10029 10029 10029 10029 10029 10029 10029

PZ2 7984 7984 7984 7984 7984 7984 7984 7984 7984 7984 7984 7984 7984

PZ4 7984 7984 7984 7984 7984 7984 7984 7984 7984 7984 7984 7984 7984

Tabulka 3: Nejlepší hodnoty účelové funkce – jednoduché ukončení po 500 generacích, ruletová selekce


Strana 47

příklad 3 Typ křížení Normální 1 bodové VCR 1 bodové VCS 1 bodové

PZ2 11183 10365 10759

příklad 7 PZ4 10915 10875 10035

PZ2 8142 7984 7984

PZ4 7984 7984 7984

Tabulka 4: Nejlepší hodnoty účelové funkce – jednoduché ukončení po 500 generacích, turnajová selekce

příklad 3 Typ křížení Normální 1 bodové VCR 1 bodové VCS 1 bodové Normální 2 bodové VCR 2 bodové VCS 2 bodové Normální uniformní VCR uniformní VCS uniformní 1-b křížení v řádcích 1-b křížení ve sloupcích VPP normální 2 b VPN normální 2 b

PZ2 10029 10029 10035 10029 10029 10029 10029 10029 10035 10029 10029 10029 10029

příklad 7 PZ4 10035 10029 10029 10029 10029 10035 10029 10029 10035 10035 10035 10029 10029

PZ2 7984 7984 7984 7984 7984 7984 7984 7984 7984 7984 7984 7984 7984

PZ4 7984 7984 7984 7984 7984 7984 7984 7984 7984 7984 7984 7984 7984



PZ2 10035 10029 10035

příklad 7 PZ4 10029 10035 10035

PZ2 7984 7984 7984

PZ4 7984 7984 7984

Tabulka 6: Nejlepší hodnoty účelové funkce – jednoduché ukončení po 5000 generacích, turnajová selekce

Strana 48

8. Porovnání použitých metod příklad 3


PZ2 10034,10 10034,70 10034,10 10034,33 10034,18 10034,38 10034,12 10033,52 10034,44 10033,50 10034,40 10033,80 10032,60

PZ4 10034,40 10034,70 10034,70 10035,07 10034,30 10035,08 10034,75 10034,62 10034,28 10034,70 10054,50 10034,40 10034,70

příklad 7 PZ2 8036,95 8001,35 8104,5 8059,52 8036,63 8147,12 8030,20 8023,23 8132,05 8018,25 8110,95 8000,90 7984,00

PZ4 7984,00 7984,00 7984,00 7994,03 7986,93 7997,95 7988,84 7985,72 7995,18 7984,00 8001,35 7984,00 8001,35

Tabulka 7: Průměrné hodnoty účelové funkce – jednoduché ukončení po 500 generacích, ruletová selekce


PZ2 1,80E+14 12308,52 8,98E+14

PZ4 12627,60 12124,96 3,61E+14

příklad 7 PZ2 8547,40 8520,41 8452,70

PZ4 8369,85 8350,40 8530,00

Tabulka 8: Průměrné hodnoty účelové funkce – jednoduché ukončení po 500 generacích, turnajová selekce

příklad 3 Typ křížení Normální 1 bodové VCR 1 bodové VCS 1 bodové Normální 2 bodové VCR 2 bodové VCS 2 bodové Normální uniformní VCR uniformní VCS uniformní 1-b křížení v řádcích 1-b křížení ve sloupcích VPP normální 2 b VPN normální 2 b

PZ2 10034,7 10034,10 10035,00 10034,10 10033,20 10033,80 10033,80 10033,80 10035,00 10034,70 10034,70 10033,80 10032,90

PZ4 10035,00 10034,40 10034,70 10033,80 10051,80 10035,00 10034,70 10034,10 10035,00 10035,00 10035,00 10033,80 10034,10

příklad 7 PZ2 7984 8000,65 8050,60 8018,00 8000,65 8067,25 8018,70 7984,00 8050,60 7984,00 8000,65 8000,65 7984,00

PZ4 7984,00 7984,00 7984,00 7984,00 7984,00 7984,00 7984,00 7984,00 7984,00 7984,00 7984,00 7984,00 7984,00



Strana 49 příklad 3

Typ křížení Normální 1 bodové VCR 1 bodové VCS 1 bodové

PZ2 11779,56 11381,04 11646,62

příklad 7

PZ4 10553,37 11075,78 10772,32

PZ2 8152,95 8151,40 8236,20

PZ4 8059,80 8059,80 8143,50

Tabulka 10: Průměrné hodnoty účelové funkce – jednoduché ukončení po 5000 generacích, turnajová selekce

příklad 3 Typ křížení Normální 1 bodové VCR 1 bodové VCS 1 bodové Normální 2 bodové VCR 2 bodové VCS 2 bodové Normální uniformní VCR uniformní VCS uniformní 1-b křížení v řádcích 1-b křížení ve sloupcích

PZ2 8,10 8,10 6,50 7,75 6,83 5,35 6,84 5,99 5,85 6,10 7,30

příklad 7 PZ4 7,55 9,05 6,60 9,45 8,78 7,14 9,32 8,97 6,59 8,00 8,25

PZ2 11,80 10,30 13,50 12,68 9,93 13,09 10,37 10,24 13,14 10,00 9,35

PZ4 14,05 17,30 16,10 16,54 16,85 11,88 13,83 18,26 11,47 15,60 12,20

Tabulka 11: Průměrné počty přípustných řešení – jednoduché ukončení po 500 generacích, ruletová selekce

příklad 3 Typ křížení Normální 1 bodové VCR 1 bodové VCS 1 bodové Normální 2 bodové VCR 2 bodové VCS 2 bodové Normální uniformní VCR uniformní VCS uniformní 1-b křížení v řádcích 1-b křížení ve sloupcích

PZ2 6,25 6,05 7,15 9,30 6,15 7,05 6,70 4,70 6,40 6,10 6,15

příklad 7 PZ4 9,25 9,30 8,60 9,90 10,00 7,25 7,80 9,85 6,10 9,05 7,75

PZ2 10,65 12,15 13,30 13,05 8,15 12,50 10,20 9,55 13,75 9,75 9,90

PZ4 17,80 17,85 13,90 19,90 16,85 13,70 12,20 19,35 12,10 18,30 13,20

Tabulka 12: Průměrné počty přípustných řešení – jednoduché ukončení po 5000 generacích, ruletová selekce

Strana 50

Relativní odchylka R =


100

 E – Ebest kde E je průměrná hodnota účelové funkce, Ebest je Ebest

nejlepší hodnota účelové funkce pro daný příklad. příklad 3 Typ křížení Normální 1 bodové VCR 1 bodové VCS 1 bodové Normální 2 bodové VCR 2 bodové VCS 2 bodové Normální uniformní VCR uniformní VCS uniformní 1-b křížení v řádcích 1-b křížení ve sloupcích VPP normální 2 b VPN normální 2 b

PZ2 0,051 0,057 0,051 0,053 0,052 0,054 0,051 0,045 0,054 0,045 0,054 0,048 0,036

příklad 7 PZ4 0,054 0,057 0,057 0,061 0,053 0,061 0,057 0,056 0,053 0,057 0,254 0,054 0,057

PZ2 0,663 0,217 1,509 0,946 0,659 2,043 0,579 0,491 1,854 0,429 1,590 0,212 0,000

Tabulka 13: Relativní odchylky, jednoduché ukončení po 500 generacích, ruletová selekce


Průměr za PZ2 0,357 0,137 0,780 0,500 0,356 1,049 0,315 0,268 0,954 0,237 0,822 0,130 0,018

Průměr za PZ4 0,027 0,029 0,029 0,094 0,045 0,118 0,059 0,039 0,097 0,029 0,236 0,027 0,137


PZ4 0,000 0,000 0,000 0,126 0,037 0,175 0,061 0,022 0,140 0,000 0,217 0,000 0,217




PZ2 0,057 0,051 0,060 0,051 0,042 0,048 0,048 0,048 0,060 0,057 0,057 0,048 0,039

příklad 7 PZ4 0,060 0,054 0,057 0,048 0,227 0,060 0,057 0,051 0,060 0,060 0,060 0,048 0,051

PZ2 0,000 0,209 0,834 0,426 0,209 1,043 0,435 0,000 0,834 0,000 0,209 0,209 0,000

PZ4 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000



Průměr za PZ2 0,029 0,130 0,447 0,239 0,126 0,546 0,242 0,024 0,447 0,029 0,133 0,129 0,020

Průměr za PZ4 0,030 0,027 0,029 0,024 0,114 0,030 0,029 0,026 0,030 0,030 0,030 0,024 0,026


Z údajů v tabulkách 14 a 16 vyplývá, že lepší je metoda PZ4 a v jejím rámci křížení normální 2 bodové následované VCR uniformním a VCR 1 bodovým. Rozdíly jsou ovšem nepatrné, nepřesahují desetinu procenta. Bylo by třeba provést testy pro větší počet příkladů většího rozsahu.

Strana 52


Typ křížení Normální 2 bodové VCR 2 bodové VCS 2 bodové 1-b křížení v řádcích 1-b křížení ve sloupcích VPP normální 2 b VPN normální 2 b

příklad 7

PZ2 19,50 25,50 18,00

PZ4 3,00 18,00 16,50

16,50 18,00 73,50 66,00

13,50 21,00 85,50 63,00

PZ2 28,50 30,00 25,50 30,00 25,50 60,00 60,00

PZ4 30,00 25,50 30,00 30,00 30,00 60,00 60,00

Tabulka 17: Průměrný počet prozkoumaných prvků populace – ukončení po 1. přípustném řešení, 500 generací, ruletová selekce


PZ2 6,12E+012 2,68E+013 6,81E+013

příklad 7

PZ4 7,88E+013 2,49E+013 6,27E+013

PZ2 -

PZ4 -

Tabulka 18: Relativní odchylky, ukončení po 1. přípustném řešení, 500 generací, ruletová selekce

příklad 3 Typ křížení Normální 2 bodové VCR 2 bodové VCS 2 bodové 1-b křížení v řádcích 1-b křížení ve sloupcích VPP normální 2 b VPN normální 2 b

příklad 7

PZ2 10029 10029 10029

PZ4 10029 10029 10029

10029 10029 10029 10029

10029 10029 10029 10029

PZ2 7984 7984 7984 7984 7984 7984 7984

PZ4 7984 7984 7984 7984 7984 7984 7984

Tabulka 19: Nejlepší hodnoty účelové funkce – ukončení po 1s, ruletová selekce


PZ2 10034,70 10033,20 10033,50

PZ4 10034,40 10034,40 10034,70

10033,20 10033,80 10033,50 10032,90

10034,70 10034,40 10034,40 10034,10

příklad 7 PZ2 8018,00 8017,55 8137,80 8001,35 8091,05 8001,35 8089,25

Tabulka 20: Průměrné hodnoty účelové funkce – ukončení po 1s, ruletová selekce

PZ4 7984,00 7984,00 8001,35 7984,00 7984,00 8001,35 7984,00



Typ křížení Normální 2 bodové VCR 2 bodové VCS 2 bodové 1-b křížení v řádcích 1-b křížení ve sloupcích

příklad 7

PZ2 7,65 6,10 5,85

PZ4 10,60 7,50 6,85

7,50 6,90

6,80 9,15

PZ2 11,60 10,40 12,65 9,00 12,05

PZ4 16,15 16,30 13,15 14,20 12,15

Tabulka 21: Průměrné počty přípustných řešení – ukončení po 1s, ruletová selekce


PZ2 0,057 0,042 0,045 0,042 0,048 0,045 0,039

příklad 7 PZ4 0,054 0,054 0,057 0,057 0,054 0,054 0,051

PZ2 0,426 0,420 1,926 0,217 1,341 0,217 1,318

PZ4 0,000 0,000 0,217 0,000 0,000 0,217 0,000

Tabulka 22: Relativní odchylky, ukončení po 1s, ruletová selekce


příklad 7

PZ2 10029 10029 10029

PZ4 10029 10029 10029

10029 10029 10029 10029

10029 10029 10029 10029

PZ2 7984 7984 7984 7984 7984 7984 7984

PZ4 7984 7984 7984 7984 7984 7984 7984



PZ2 10034,40 10034,70 10033,80

PZ4 10034,40 10033,50 10034,40

10034,40 10034,40 10034,10 10032,30

10034,70 10034,10 10034,10 10034,10

příklad 7 PZ2 7984,00 7984,00 8000,65 7984,00 8000,65 7984,00 7984,00


PZ4 7984,00 7984,00 7984,00 7984,00 7984,00 7984,00 7984,00

Strana 54


Typ křížení Normální 2 bodové VCR 2 bodové VCS 2 bodové 1-b křížení v řádcích 1-b křížení ve sloupcích

příklad 7

PZ2 6,55 8,45 5,60

PZ4 9,95 10,05 6,80

6,95 6,40

7,50 6,60

PZ2 13,50 9,90 14,40 7,60 8,10

PZ4 16,65 16,70 11,90 15,25 10,65

Tabulka 25: Průměrné počty přípustných řešení – ukončení po 10s, ruletová selekce


PZ2 0,054 0,057 0,048 0,054 0,054 0,051 0,033

příklad 7 PZ4 0,054 0,045 0,054 0,057 0,051 0,051 0,051

Tabulka 26: Relativní odchylky, ukončení po 10s, ruletová selekce

PZ2 0,000 0,000 0,209 0,000 0,209 0,000 0,000

PZ4 0,000 0,000 0,000 0,000 0,000 0,000 0,000


8.3

Strana 55

Porovnání ruletové a turnajové selekce

VCS, VCR , normální křížení, 1-bodové

selekce Ruletová

Turnajová

Nejlepší hodnoty účelové funkce – jednoduché ukončení po 500 generacích, př. 3

LEPŠÍ


PŘIBLIŽNĚ STEJNÉ









STEJNÉ

STEJNÉ

LEPŠÍ

MNOHEM HORŠÍ (NAPŘ. 1E+14)

Průměrné hodnoty účelové funkce – jednoduché ukončení po 500 generacích, př. 3 Průměrné hodnoty účelové funkce – jednoduché ukončení po 500 generacích, př. 7

LEPŠÍ

Průměrné hodnoty účelové funkce – jednoduché ukončení po 5000 generacích, př. 3

LEPŠÍ

Průměrné hodnoty účelové funkce – jednoduché ukončení po 5000 generacích, př. 7

LEPŠÍ

Nejkratší doba výpočtu – jednoduché ukončení po 500 generacích, př. 3 Nejkratší doba výpočtu – jednoduché ukončení po 500 generacích, př. 7

LEPŠÍ LEPŠÍ

Nejkratší doba výpočtu – jednoduché ukončení po 5000 generacích, př. 3 Nejkratší doba výpočtu – jednoduché ukončení po 5000 generacích, př. 7

LEPŠÍ LEPŠÍ

Průměrná doba výpočtu – jednoduché ukončení po 500 generacích, př. 3 Průměrná doba výpočtu – jednoduché ukončení po 500 generacích, př. 7

LEPŠÍ LEPŠÍ

Průměrná doba výpočtu – jednoduché ukončení po 5000 generacích, př. 3 Průměrná doba výpočtu – jednoduché ukončení po 5000 generacích, př. 7

MÍRNĚ LEPŠÍ LEPŠÍ

Tabulka 27: Porovnání ruletové a turnajové selekce

Rozdíl mezi turnajovou a ruletovou selekcí byl skoro stejný(ruletová nepatrně lepší), ale po provedení více testů se rozdily vyrovnaly. S jednou výjimkou, v příkladě č. 3 při turnajové selekci někdy vycházela velmi vysoká hodnota účelové funkce(1E16 proti 1E4 u ruletové). Po prozkoumání průměrného počtu přípustných řešení ale jednoznačně vede ruletová selekce(kolem 8 přípustných

Strana 56


řešení, u turnajové selekce to bylo 1).

8.4

Porovnání způsobů mutací

Byly testovány mutace sousedních period, sousedních výrobků – předchůdců a sousedních výrobků – následníků, normální 2-bodové křížení. příklad 3 Typ mutace MSP MSVP MSVN

PZ2 10029 10029 10029

příklad 7 PZ4 10029 10029 10029

PZ2 8317 7984 7984

PZ4 7984 7984 7984


příklad 3 Typ mutace MSP MSVP MSVN

PZ2 10029 10029 10029

příklad 7 PZ4 10029 10029 10035

PZ2 7984 7984 7984

PZ4 7984 7984 7984



PZ2 10760,22 10144,71 10663,92

PZ4 10311,70 10034,10 10546,20

příklad 7 PZ2 8446,95 8333,10 8035,15

PZ4 8069,75 8256,25 8001,35



PZ2 10236,70 10034,70 10646,30

PZ4 10033,80 10033,50 10507,20

příklad 7 PZ2 8340,30 8246,15 8018,00

PZ4 8035,35 8035,15 7984,00



PZ2 12000,44 12699,44 10035

PZ4 11405 12033,24 11865

příklad 7 PZ2 1,7E308 1,7E308 1,7E308

PZ4 10259 8753 1,7E308

Tabulka 32: Nejlepší hodnoty účelové funkce – ukončení po 1. přípustném řešení, 500 generací, ruletová selekce



Typ mutace MSP MSVP MSVN

PZ2 6945,90 5631,25 6568,17

příklad 7

PZ4 3846,34 5787,83 2027,47

PZ2 0,00 0,00 0,00

PZ4 512,95 437,65 0,00

Tabulka 33: Průměrné hodnoty účelové funkce – ukončení po 1. přípustném řešení, 500 generací, ruletová selekce


PZ2 103,50 84,00 82,50

příklad 7 PZ4 70,50 87,00 63,00

PZ2 60,00 60,00 60,00

PZ4 72,00 690,00 60,00

Tabulka 34: Průměrný počet prozkoumaných prvků populace – ukončení po 1. přípustném řešení, 500 generací, ruletová selekce


PZ2 10029 10029 10035

příklad 7 PZ4 10029 10029 10029

PZ2 7984 7984 7984

PZ4 7984 7984 7984



příklad 7

PZ2 11508,76

PZ4 10299,90

10263,22 10846,92

10034,10 10502,40

PZ2 8467,00 8301,65 8052,25

PZ4 660468000008286, 63 8184,70 8001,35



PZ2 10029 10029 10029

příklad 7 PZ4 10029 10029 10035

PZ2 7984 7984 7984


PZ4 7984 7984 7984

Strana 58


Typ mutace MSP MSVP MSVN

PZ2 10522,90 10034,10 10492,20

příklad 7

PZ4 10032,90 10033,80 10465,20

PZ2 8353,35 8289,55 8000,65

PZ4 7984,00 8069,85 8015,65


Mutace byly porovnány podle všech sledovaných parametrů – viz příloha. Nejlepší hodnoty účelových funkcí jsou téměř stejné, liší se průměrné hodnoty účelových funkcí a průměrné počty prozkoumaných prvků populace. Pořadí od nejlepšího typu mutace je následující: ● Normální mutace ● MSVP ● MSVN ● MSP

8.5

Porovnání časových hodnot Hodnocení: 1 nejlepší, 3 nejhorší Jednoduché ukončení, 1b + 2b + uniformní křížení počet generací

normální

VCR

VCS

Nejkratší doba výpočtu

500

PZ2

2

3

1


500

PZ4

1

1

2


5000

PZ2

2

3

1


5000

PZ4

2

1

3

Průměrná doba výpočtu

500

PZ2

3

2

1


500

PZ4

1

2

3


5000

PZ2

1

2

1


5000

PZ4

2

1

3

celkem:

14

15

15

Tabulka 39: Porovnání časových hodnot

Z uvedeného porovnání vyplývá, že nejlepších časových výsledků dosáhl normální typ křížení, těsně následují typ výměna celých řádků shodně s typem výměna celých sloupců. Podrobné údaje jsou uvedeny v příloze.

Strana 59

9. ZÁVĚR Cílem této diplomové práce bylo analyzovat problematiku optimalizace dynamických výrobních dávek, navrhnout nové genetické operátory, vytvořit programovou realizaci a vyhodnotit testy těchto operátorů na předložených příkladech. Genetické operátory se vztahovaly k typu selekce, křížení a mutace. Rozdíly mezi turnajovou a ruletovou selekcí byly nejprve minimální, s výjimkou velmi nepříznívých výsledků pro příklad č. 3 při turnajové selekci. Ruletová selekce byla také lepší v počtu přípustných řešení. Při zohlednění všech parametrů sledovaných typů křížení se jako nejlepší ukázalo VCR. Nejlepší hodnoty byly stejné, výpočetní časy se téměř nelišily. Metoda PZ4 dosahovala lepších výsledků než PZ2. Při porovnání jednobodového, dvoubodového a uniformního křížení jako nejlepší vyšlo dvoubodové křížení, potom dvoubodové a jako nejhorší uniformní křížení. Nejlepší typ mutace byl normální, následuje mutace sousedních výrobků – předchůdců, mutace sousedních výrobků - následníků, nejhorších výsledků dosahovala mutace sousedních period. V příloze jsou všechny výpočty, porovnání a všechny textové soubory s výsledky(7019 souborů). Protože rozdíly mezi jednotlivými výsledky testů byly někdy velmi malé, bylo by vhodné zvětšit rozsah testovaných příkladů a zvýšit jejich počet.

Strana 61

10. SEZNAM POUŽITÉ LITERATURY [1] POLIŠČUK, R.: Instrukce pro autory závěrečných prací, 2006, http://autnt.fme.vutbr.cz/doc/SZZ2006_Instrukce.pdf [2] DVOŘÁK, J. Koncept habilitační práce [3] DVOŘÁK, J., MARTINEK, V. and KRÁL, J. Solving a General Dynamic Lot Sizing Problem with Constrained Resources. In Proceedings of the 7th International Research/Expert Conference "Trends in the Development of Machinery and Associated Technology" TMT 2003, Lloret de Mar, Barcelona, Spain, 2003, pp. 1093-1096 [4] KATOK, E., LEWIS, H. S. and HARRISON, T. P. Lot Sizing in General Assembly Systems with Setup costs, Setup times, and Multiple Constrained Resources. Management Science, Vol. 44, 1998, pp.859-877. [5] XIE, J. and DONG, J. A Heuristic Genetic Algorithm to General Capacitated Lot- Sizing Problems. Computers & Mathematics with Applications, Vol. 44, Issues 1-2, 2002, pp. 263-276. [6] KRÁL, J. Optimalizace dynamických výrobních dávek. Diplomová práce. ÚAI FSI VUT, Brno 2002. [7] ČERNOUŠKOVÁ, L. Optimalizace dynamických výrobních dávek. Diplomová práce. ÚAI FSI VUT, Brno 2003. [8] KONEČNÝ, P. Optimalizace dynamických výrobních dávek při omezených zdrojích. Diplomová práce. ÚAI FSI VUT, Brno 2004. [9] OŠMERA, P. Genetické algoritmy a jejich aplikace, využití biologických a fyzikálněinformačních principů evoluce. Habilitační práce. FSI VUT, Brno 2001. [10]PEVNÝ, T. Neuronové sítě a genetické algoritmy-vybrané aplikace při řešení některých technických problémů. Diplomová práce. Katedra matematiky, Fakulta jaderná a fyzikálně inženýrská ČVUT, 2003.

OPTIMALIZACE DYNAMICKÝCH VÝROBNÍCH DÁVEK OPTIMIZATION OF DYNAMIC LOT SIZES

Recommend Documents