VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ PROGRAMOVÝ SYSTÉM PRO PLÁNOVÁNÍ A ROZVRHOVÁNÍ VÝROBY PROGRAM SYSTEM FOR PRODUCTION PLANNING AND SCHEDULING

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

PROGRAMOVÝ SYSTÉM PRO PLÁNOVÁNÍ A ROZVRHOVÁNÍ VÝROBY PROGRAM SYSTEM FOR PRODUCTION PLANNING AND SCHEDULING

DIPLOMOVÁ PRÁCE DIPLOMA THESIS

AUTOR PRÁCE

Petr Pospíšil

AUTHOR

VEDOUCÍ PRÁCE SUPERVISOR

BRNO 2007

RNDr. Jiří Dvořák, CSc.

Strana 3

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 5

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

Strana 7

ABSTRAKT Tato diplomová práce se zabývá vícestupňovým vícevýrobkovým problémem optimalizace dynamických výrobních dávek pro obecné výrobní struktury a problémem optimalizace rozvrhu pořadí výrobků na jednotlivých strojích. Výrobní struktura je reprezentována orientovaným acyklickým grafem a kritériem optimalizace jsou celkové výrobní náklady. Cílem je návrh integrovaného přístupu k řešení obou problémů pomocí stochastických heuristických metod (genetické algoritmy, simulované žíhání, zakázané hledání), programová realizace navržených postupů a jejich srovnání na souboru testovacích příkladů.

ABSTRACT This thesis deals with a multi-level, multi-machine dynamic lot sizing problem with a general production structure and a problem of scheduling products on each machine. The production structure is represented by oriented acyclic graph and the total production costs are used as the optimization criterion. The aim is to propose an integrated approach to solving both problems by means of stochastic heuristic methods (genetic algorithms, simulated annealing, tabu search), program implementation of proposed algorithms and their comparison on test examples.

KLÍČOVÁ SLOVA Výrobní dávka, zakázková výroba, disjunktivní graf, genetický algoritmus, simulované žíhání.

KEYWORDS Lot size, job shop scheduling, disjunctive graph, genetic algorithm, annealing.

simulated

Strana 8

Abstrakt

Strana 9

PODĚKOVÁNÍ Na tomto místě bych rád poděkoval RNDr. Jiřímu Dvořákovi, CSc, za jeho vedení a odborné rady a podněty při vyhotovení této diplomové práce.

Strana 10

Poděkování

Prohlášení Prohlašuji, že jsem diplomovou práci zpracoval samostatně a že jsem uvedl všechny použité prameny a literaturu, ze kterých jsem čerpal.

V Brně dne ….........

…......................... podpis

Strana 11

Obsah: Zadání závěrečné práce...................................................................................................3 Licenční smlouva.............................................................................................................5 Abstrakt............................................................................................................................7 Poděkování.......................................................................................................................9 1 Úvod............................................................................................................................13 2 Optimalizace výrobních dávek.................................................................................15 2.1 Formulace problému...............................................................................................16 2.2 Přesné metody řešení...............................................................................................18 2.3 Heuristické metody řešení.......................................................................................18 3 Rozvrhování výroby .................................................................................................21 3.1 Rozvrhování typu flow-shop (rozvrhování proudové výroby)...............................21 3.2 Rozvrhování typu job-shop (rozvrhování zakázkové výroby) ...............................22 3.3 Metody řešení..........................................................................................................23 4 Heuristické metody....................................................................................................25 4.1 Horolezecký algoritmus (Hill climbing) ................................................................25 4.2 Simulované žíhání (Simulated annealing) ..............................................................25 4.3 Zakázané hledání (Tabu search) .............................................................................27 4.4 Genetické algoritmy (Genetic algorithms) .............................................................28 5 Reprezentace dat........................................................................................................31 5.1 Způsoby reprezentace dat pro job – shop rozvrhování...........................................31 5.2 Disjunktivní graf.....................................................................................................32 5.3 Montážní a distribuční operace...............................................................................33 5.4 Časy přípravy, dopravní a technologické časy........................................................34 6 Návrh řešení problému..............................................................................................35 6.1 Použitý způsob reprezentace dat.............................................................................35 6.2 Relace sousedství....................................................................................................36 6.3 Popis algoritmu.......................................................................................................36 6.4 Přesuny výroby........................................................................................................39 6.5 Algoritmus pro nalezení počátečního rozvrhu........................................................41 7 Realizace programu...................................................................................................43 7.1 Hlavní okno.............................................................................................................43 7.2 Nápověda.................................................................................................................44 7.3 Nastavení parametrů algoritmů...............................................................................44 7.4 Výpočet...................................................................................................................45 7.5 Součásti programu...................................................................................................46 7.6 Spuštění výpočtu.....................................................................................................46 7.7 Zpracování prvků a simulované žíhání...................................................................47 7.8 Programové řešení genetického algoritmu..............................................................49 8 Výpočetní experimenty..............................................................................................51 8.1 Příklady zaměřené na hledání optimálního rozvrhu................................................51 8.2 Příklad zaměřený na integraci dávek a rozvrhu......................................................53 8.3 Porovnání výsledků.................................................................................................55 9 Závěr...........................................................................................................................57 10 Seznam použité literatury........................................................................................59

Strana 13

1

ÚVOD

V současné době kolem sebe vidíme snahu o zvyšování produktivity práce a zefektivnění výroby. S rostoucí konkurencí se firmy snaží své vnitropodnikové procesy co nejvíce optimalizovat, aby proti svým soupeřů získaly nějakou výhodu. Proto je důležitým úkolem plánování výroby a tvorba výrobních rozvrhů. Plánování znamená určení velikosti výrobních dávek, tj. kdy a kolik výrobků se má vyrobit. Plánovací horizont je časové období, které je rozdělené na několik stejně dlouhých period, ve kterém se plánují činnosti v závislosti na poptávce po koncových výrobcích. Poptávka po výrobcích může být v čase konstantní (stacionární) nebo proměnná (dynamická). V této práci jsem uvažoval dynamickou poptávku, která je spojena s konečným plánovacím horizontem. Obecně je problém rozvrhování dán konečnou množinou prací, které mají být v určitém časovém období provedeny a omezeným počtem strojů, které jsou k dispozici. Přitom u každého výrobku známe technologický postup, určující operace v daném pořadí i jejich doby trvání, a který každé operaci přiděluje určitý druh stroje. Existují dva typy rozvrhování, a to rozvrhování zakázkové výroby (job shop scheduling), o kterém mluvíme v případě, že pořadí strojů může být pro každý výrobek různé a rozvrhování proudové výroby (flow shop scheduling), kde nastává speciální případ, kdy pořadí strojů je pro všechny výrobky stejné. Úkolem rozvrhování je najít nejlepší rozvrh (schedule) provádění operací, tzn. nalézt optimální pořadí operací na jednotlivých strojích. Jako hlavní kritérium rozvrhu se nejčastěji používá celková doba trvání výroby (makespan), dále ztráty vyplývající s nedodržením časových požadavků, stupeň rozpracovanosti apod. Tato diplomová práce se zabývá problematikou rozvrhování výroby a optimalizace výrobních dávek pro vícestupňový vícevýrobkový výrobně - montážní systém s obecnou strukturou a více kapacitně omezenými zdroji v prostředí zakázkové výroby. Navazuje na výsledky dosažené v [14], kde byl představen dekompoziční přístup, při kterém se střídá řešení plánovacího problému (problém velikosti výrobních dávek) pro pevně stanovenou posloupnost operací na strojích s řešením rozvrhovacího problému pro neměnný výrobní plán. Cílem této práce je analyzovat typy problémů a existující metody řešení, navržení integrovaného přístupu pro řešení vybraných typů obou problémů s použitím stochastických heuristických metod a následně vytvoření programové realizace navržených metod a jejich srovnání na souboru testovacích příkladů. Text práce je seřazen do následujících částí: Nejdříve je analyzována problematika rozvrhování výroby a problematika optimalizace výrobních dávek, poté jsou podrobněji rozebrány publikované metody řešení zadaného problému a následně je popsán návrh a realizace řešení. Nakonec je provedeno srovnání navržených metod na souboru testovacích příkladů.

Strana 14

1 Úvod

Strana 15

2

OPTIMALIZACE VÝROBNÍCH DÁVEK

Již v úvodu byly uvedeny některé základní pojmy, které ještě s několika dalšími nyní vysvětlím. Jeden ze základních pojmů je výrobní dávka (production lot), což je množství výrobků (součástí, dílů), které jsou současně zadávány do výroby nebo z výroby odváděny, jsou opracovávány v těsném časovém sledu nebo současně, a to na určeném pracovišti a s jednorázovým konstantním vynaložením nákladů na přípravu a zakončení příslušného procesu. Pojem výrobní dávka je třeba oddělit od pojmu série, která představuje celou řadu výrobků (součástí, dílů), jednoho provedení a je tvořena výrobními dávkami. Výrobní dávky mají z ekonomického hlediska velký vliv na efektivitu celého procesu. Zvyšování velikosti výrobních dávek snižuje fixní náklady (náklady na přípravu a zakončení výroby), zvyšuje produktivitu práce a zjednodušuje operativní řízení výroby. Naopak se zvýšení dávek projeví zvýšením skladovacích nákladů, zvýšením vázanosti obratového kapitálu, zvýšením výrobních a manipulačních ploch, prodlužováním průběžné doby výroby a snižováním odolnosti výroby proti změnám a poruchám. Cílem řešení problému výrobních dávek je určení výrobních dávek pro všechny výrobky tak, aby byla splněna vnější poptávka po těchto výrobcích a současně celkové náklady byly minimální. V minulosti bylo vypracováno mnoho modelů pro různé typy problémů výrobních dávek známých z průmyslové praxe. Tyto modely mohou být rozděleny podle: • Plánovacího horizotu (konečný nebo nekonečný) • Charakteru poptávky (stacionární nebo dynamická) • Povahy dávek (časově invariantní nebo dynamické dávky) • Počtu výrobků (jeden nebo více výrobků) • Počtu omezených zdrojů (kapacitně neomezené nebo omezené) • Počtu výrobních stupňů (jednostupňové nebo vícestupňové) • Povahy montážního systému (sériová, montážní, distribuční nebo obecná) Plánovací horizont je určité časové období rozdělené na množství stejně dlouhých period, ve kterém se plánují nějaké činnosti. Tyto činnosti se plánují v závislosti na poptávce. Poptávka je buď konstantní v čase (stacionární), nebo variabilní v čase (dynamická). Nekonečný plánovací horizont je obvykle spojen se stacionární poptávkou a s časově invariantními výrobními dávkami, zatímco dynamické výrobní dávky s dynamickou poptávkou se plánují v horizontu konečném. Poptávka je předpokládaná spotřeba výrobků na konci časových period. Podle původu rozeznáváme nezávislou a závislou poptávku. Dále rozeznáváme modely se statickou a dynamickou poptávkou: • Nezávislá poptávka – na tuto poptávku nemá podnik v podstatě vliv. Jde většinou o poptávku zákazníků po konečných výrobcích • Závislá poptávka – odvozuje se z poptávky po konečném výrobku. Ze znalosti poptávky po konečném výrobku lze vypočítat čas a množství všech dílů a materiálu, které jsou nutné pro výrobu a montáž konečného výrobku • Stacionární poptávka – poptávka je konstantní v čase • Dynamická poptávka – poptávka je variabilní v čase Výrobně – montážní strukturu si lze představit jako orientovanou síťovou strukturu. Výrobní struktura může být jednoúrovňová (single level), nebo víceúrovňová (multilevel). V případě jednoúrovňové struktury obsahuje síť pouze izolované uzly v paralelním vztahu. U víceúrovňové struktury je nejméně jedna dvojice uzlů spojena hranou. Uzly grafu

Strana 16

2 Optimalizace výrobních dávek

představují jednotlivé koncové výrobky či polotovary nutné k sestavení koncového výrobku. Hrany jsou vztahy mezi výrobky. Hrana (i, j) z uzlu i do uzlu j existuje tehdy, pokud je výrobek i nutný k sestavení výrobku j (počet jednotek výrobku i požadovaný pro jednu jednotku výrobku j je ohodnocením této hrany). V literatuře bývá tato struktura značena jako BOM (Bill of material). Pokud jsou však uvažovány kapacitně omezené zdroje, je o výrobně/montážní struktuře nutno uvažovat v rovině prováděných operaci. Každé operaci je přiřazen určitý typ zdroje a graf pak podává informaci nejen o vstupně - výstupní (tzv. „gozinto“) struktuře, ale také o prováděných operacích a požadovaných zdrojích. Víceúrovňové struktury dále rozlišujeme podle typu sítě na sériové, montážní, distribuční a obecné. Pro sériové struktury platí, že každý uzel má nejvýše jednu vstupní a nejvýše jednu výstupní hranu, zatímco obecná montážní struktura umožňuje, aby každý uzel měl více než jednu vstupní a jednu výstupní hranu. U čistě montážní (stromové struktury) má každý uzel (mimo uzlu * ) nejvýše jednu výstupní a jednu nebo více vstupních hran. Montážní a distribuční jsou pak speciálními případy obecné struktury (viz obr. 1).

Obr. 1. Výrobně montážní struktura V MRP II (Manufacturing Ressource Planning) systémech jsou velikost dávek a výrobní rozvrh obvykle určeny ve třech fázích: nejprve jsou určeny dávky bez ohledu na kapacitní omezení. Vícestupňová výrobní struktura je do problému zahrnuta tak, že dávky jsou postupně vypočítány stupeň po stupni počínaje koncovými výrobky. Velikost dávek je poté přizpůsobena kapacitním omezením. Priorita mezi výrobky není v tomto okamžiku brána v potaz. Pořadí vykonávaných operací je určeno až nakonec. Tato strategie však vede k vysoké rozpracovanosti výroby (work-in-process) a dlouhým průběžným časům (lead time), což je důvodem pro hledání nových výhodnějších postupů pro nalezení řešení blízké optimálnímu. 2.1 Formulace problému Při integraci problému dávek a rozvrhování budeme vycházet z následujícího modelu, prezentovaného dříve např. v [2], [16]. Uvažujeme vícevýrobkový vícestupňový kapacitně


Strana 17

omezený problém dynamických výrobních dávek (MLCLSP – multi level capacitated lot sizing problem) charakterizovaný následujícími předpoklady: • výrobní struktura je obecného typu (s více možnými koncovými výrobky), • plánovací horizont je konečný s T časovými periodami, • je dána dynamická pevná vnější poptávka po N výrobcích, • je dáno více zdrojů s omezenou kapacitou, která musí být dodržena, • nejsou povoleny skluzy při uspokojování poptávky, • produkce výrobků je okamžitá, nehledě na vyráběné množství, • výrobní, seřizovací a skladovací náklady jsou časově proměnné. Předpokládáme, že všechny uzly jsou očíslované tak, aby splňovaly podmínku i > j pro hranu (i, j). Zaveďme následující označení: N … počet výrobků T … počet časových period K ... počet kapacitně omezených zdrojů dit … vnější poptávka po výrobku i v periodě t S(i) … množina bezprostředních následníků výrobku i (jestliže i je koncový výrobek, pak S(i) = Ø); 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 bkt … množství zdroje k dostupné v periodě t; fikt … pevné množství zdroje k nutné k výrobě 1 položky výrobku i v periodě t (např. seřizovací čas na stroji); vikt ... jednotkové 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) Yit … binární proměnná označující, zda je dovolena produkce výrobku i v periodě t ( Y it =1 jestliže X it 0 , Y it =0 v opačném případě) Iit … zásoba výrobku i v periodě t; (počáteční zásoba a I i0 konečná zásoba I iT výrobku i jsou dány) M ... velké kladné číslo Cílem řešení MLCLSP problému je určení výrobních dávek, které minimalizují sumu seřizovacích, výrobních a skladovacích nákladů výrobního systému. Problém lze formulovat jako následující model smíšeně celočíselného programování: N

T

F { X ,Y , I }=∑ ∑ {s it Y it cit X it hit I it }

Minimalizovat

(1)

i =1 t =1

za podmínek: I i ,t −1 X it −I it =d it 

∑

j∈ S  i

r ij X

jt

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

(2)

Strana 18


N

∑  f kit Y it v kit X it ≤bkt i=1

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

(3)

X it ≤M Y it

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

(4)

I it , X it ≥0

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

(5)

Y it ∈0,1

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

(6)

Omezení (2) představují rovnice rovnováhy zásob. Podmínky (3) zabezpečují přípustnost z hlediska kapacit. Omezení (4) zajišťují, že seřizovací náklady sit jsou započítány pouze když X it je kladné. Podmínka nezápornosti zásob I it v (5) zabraňuje skluzu v uspokojování poptávky. Pro řešení MLCLSP problému se používají dva fundamentálně odlišné přístupy. Prvním je optimalizační přístup, který hledá optimální řešení, zatímco druhý heuristický přístup hledá dobrá řešení a empiricky testuje jejich kvalitu. 2.2 Přesné metody řešení Metoda větví a mezí je iterační metoda pro nalezení globálního extrému funkce f(x) na množině přípustných řešení M. Je založena na opakování dvou operací: Větvení – množina M a později její vybraná podmnožina se rozkládají na dvě či více disjunktní podmnožiny (postup lze znázornit stromovým grafem) Omezování – každou podmnožinu získanou předchozí operací určuje dolní (při minimalizaci), resp. horní (při maximalizaci) mez hodnot funkce f(x) na této podmnožině Pro další rozklad se volí podmnožina s nejnižší dolní, resp. nejvyšší horní mezí. Cílem je najít takové přípustné řešení, pro něž hodnota víceúčelové funkce není větší než dolní meze, resp. není menší než horní meze u všech dosud nerozložených podmnožin, neboť takové řešení je optimální. Dynamické programování Základy dynamického programování vypracoval v roce 1957 Bellman. Problém je rozdělen na několik stupňů a v každém stupni je potřeba učinit rozhodnutí, která mají vliv na rozhodnutí učiněná v dalších stupních. Na základě Bellmanova principu optimality je sestavena rekurzivní rovnice, která popisuje optimální hodnotu účelové funkce v daném stupni jako funkci hodnoty získané v předchozím stupni. 2.3 Heuristické metody řešení Klasické optimalizační metody (dynamické programování, metoda větví a mezí) mohou být aplikovány pouze na malou třídu problémů, které mají malou velikost nebo jednoduchou strukturu. Jednovýrobkový, jednoúrovňový, kapacitně neomezený problém s konstantní poptávkou je jednoduše optimálně řešitelný metodou EOQ (Economic Order Quantity), která počítá se spojitým časem a nekonečným plánovacím horizontem a nepočítá s kapacitními omezeními. Tato metoda byla použita např. v [9]. V případě, že poptávka není konstantního charakteru, se dá vhodně řešit metodou dynamického programování, mnoha výkonnými heuristickými procedurami, přřípadně algoritmem Wagner-Withinovým, který


Strana 19

usiluje o minimalizaci proporcí nákladů objednávání a skladování za použití dynamického programování. Jde o výběr optimální strategie pokrytí požadavků každé výrobní periody při minimálních celkových nákladech. Přehled procedur řešících výrobní dávky je prezentován např. v [6]. Problém dávek se stává obtížně řešitelným v momentě, kdy jsou do modelu zahrnuta kapacitní omezení. Florian et al. [8] ukázali, že jednovýrobkový, kapacitně omezený problém výrobních dávek bez seřizovacích časů je NP těžký, z čehož plyne, že vícevýrobkový kapacitně omezený problém výrobních dávek je také NP těžký. Z předchozího vyplývá, že většinu praktických problémů je nutno řešit použitím heuristických metod. Heuristické metody byly často vyvíjeny na tělo daným specifickým problémům či typům problémů, s kterými jsou do značné míry provázány. Pak ovšem nelze takovou heuristiku řešící jeden typ problému nijak snadno použít k řešení problému jiného. Z tohoto důvodu je dnes nemalý zájem věnován technikám schopným řešit širší třídy problémů. Typickými zástupci těchto metod jsou genetické algoritmy (GA), simulované žíhání (SA), zakázané hledání (TS) a evoluční algoritmy. Katok et. al. [10] rozdělují heuristické procedury do čtyř tříd: • •

•

•

Dekompoziční přístupy: Tyto přístupy ignorují víceúrovňovou strukturu MLCLSP a řeší posloupnost jednoúrovňových kapacitně omezených problémů. Procedury založené na Lagrangiánu: Tempelmeier a Derstroff používají Lagrangeovskou relaxaci podmínek rovnováhy zásob a kapacitních omezení a aktualizují Lagrangeovy multiplikátory pomocí subgradientové optimalizace s cílem určit dolní meze. Přípustná řešení jsou sestavena heuristickou konečnou rozvrhovaní procedurou, která posouvá produkci z přetížených period. Procedury založené na lineárním programování (LP): Tato skupina zahrnuje různé LP relaxace MLCLSP problému formulovaného jako úloha smíšeně celočíselného programování. Maes et. al. Představují tři heuristiky založené na LP pro řešení problémů se seřizovacími náklady bez seřizovacích časů. Harrison a Lewis uvažují problémy se seřizovacími časy bez seřizovacích nákladů v sériovém montážním systému. Stochastické metody lokálního hledání: Tato skupina zahrnuje simulované žíhání, zakázané hledání, genetické algoritmy a evoluční strategie. Özdamar a Birbil navrhují hybridní heuristiky pro kapacitně omezený problém výrobních dávek. Do GA integrují schéma lokálního hledání, které spojuje výhody TS a SA. Xie a Dong [11] navrhují genetický algoritmus pro obecné struktury s více možnými koncovými výrobky. Jejich metoda založená na genetickém algoritmu zajišťuje přípustnost jen z hlediska kapacit, zatímco nepřípustnost z hlediska zásob je penalizována. Dvořák a Král v [7] navrhli algoritmus zachovávající přípustnost z hlediska zásob, přičemž nepřípustnost z hlediska kapacit je snižována přesunem výroby dopředu nebo dozadu a zbývající přesahy kapacit jsou penalizovány.

Strana 20


Strana 21

3

ROZVRHOVÁNÍ VÝROBY

Problematika rozvrhování výroby (scheduling problem) je velice složitý proces patřící do množiny složitých kombinatorických úloh. Tento problém je určen množinou strojů, množinou prací členěných do sledů jednotlivých operací a stanovením vztahů mezi stroji a operacemi. Následné řešení spočívá v nalezení nejlepších pořadí prací na zadaných strojích. V jednodušším případě každá práce pochází přes všechny stroje a pořadí strojů je u každé práce stejné (tzv. flow shop scheduling). Ve složitějším případě pořadí strojů může být pro jednotlivé práce různé a navíc práce nemusejí procházet přes všechny stroje (tzv. job shop scheduling). Při řešení mohou být sledovány různé cíle, jako např. minimalizace ztrát spojené s nesplněním prací v požadovaných termínech, minimalizace celkové doby zpracování, minimalizace prostojů, minimalizace rozpracované výroby apod. Je dána množina úloh nebo též prací (jobs) a množina m strojů či procesorů (machines). Je nutno vykonat všech n úloh, přičemž každá úloha se skládá z určitého, obecně nestejného počtu operací. Doby trvání těchto operací mohou být opět obecně různé, dokonce nulové. Pořadí operací pro každou úlohu je pevně dáno technologickým postupem a nelze je měnit. Na jednom stroji lze současně provádět pouze jednu operaci jedné úlohy a provádění operace nelze přerušit. Vykonání úlohy znamená tedy provedení všech jejích operací v daném pořadí na daných strojích. Přiřazení libovolných proveditelných pořadí operacím na všech strojích se nazývá rozvrh (schedule). Úkolem rozvrhování je optimalizovat rozvrh, tedy nalézt nejvhodnější pořadí úloh na dané množině strojů. Kritériem pro optimalizaci bývá nejčastěji čas dokončení všech úloh, tedy celková doba trvání výroby (makespan). 3.1 Rozvrhování typu flow-shop (rozvrhování proudové výroby) Problém flow-shop rozvrhování může být popsán následovně: Existuje množina m strojů a množina n prací. Všechny práce prochází stejné pořadí strojů, tzn., že práce je složena ze seznamu úkolů, kde i-tý úkol každé práce je určen stejným strojem, který potřebujeme k provedení daného úkolu, a časem provedení na daném stroji. Předpokládejme, že pořadí zpracování množiny prací J na m rozdílných strojích popsáno posloupností strojů P1, P2, … , Pm . Práce Jj ∈ J je sestavena z úkolů T1j, … , Tmj s procesními časy pij pro všechny stroje Pi , i = 1, … , m . Existuje mnoho omezení týkajících se jak prací, tak i strojů. Základní omezení a pravidla je možno definovat následujícím způsobem: • • • • •

každá práce je složena z operací, které se provádějí na vzájemně různých strojích všechny práce provádějí své operace na strojích ve stejném pořadí strojů (stroje jsou řazeny sériově) operace jsou nepřerušitelné v každém okamžiku se na každém stroji může provádět nejvýše jedna operace, a tedy nejvýše jedna úloha mezi operacemi různých úloh nejsou žádné precedenční omezení

Zatímco pořadí strojů všech prací je stejné, problém rozvrhování je nalézt pořadí prací, které minimalizuje maximum časů dokončení všech úkolů. Ve většině případů flow-shopu

Strana 22

3 Rozvrhování výroby

se jedná o tzv. permutační flow-shop, kde každý stroj provádí práce ve stejném pořadí. Z toho vyplývá, že když je u permutačního flow-shopu stanoveno pořadí prací na prvním stroji, je potom použito i u ostatních strojů. V tomto permutačním problému rozvrhování proudové výroby je řešení reprezentováno pouze pořadím π všech úloh. Potom je každé řešení proveditelné. Výsledný rozvrh je pak nazýván permutačním rozvrhem. Cílem se stává nalezení takového rozvrhu π, u kterého je hodnota účelové funkce optimální. Nejčastěji se jako kritérium používá makespan Cmax, který je možno definovat jako termín dokončení poslední úlohy. 3.2 Rozvrhování typu job-shop (rozvrhování zakázkové výroby) Problém job-shop rozvrhování může být pospán následovně: Existuje množina m strojů a množina n prací. Každá práce má specifikováno procesní pořadí strojů, tzn., že práce je složena ze seznamu jednotlivých úkolů, které jsou určeny požadavkem na stroj a na procesním časem na něj. Operace a stroje musí splnit několik následujících omezení: • každé operaci přísluší jediné pracoviště, na němž se může operace provádět • každá operace musí být na daném stroji zpracována v nepřerušeném časovém úseku dané délky • v každém okamžiku se na každém stroji může provádět nejvýše jedna operace • po sobě jdoucí operace patřící k téže úloze jsou prováděny na různých pracovištích • mezi operacemi různých prací nejsou žádné precedenční omezení Nechť je použito následující označení: n N

počet prací (finálních výrobků, koncových položek) celkový počet operací (výrobních položek); koncové položky mají čísla 1,…, n B(i) množina bezprostředních předchůdců operace (položky) i m počet strojů (skupin strojů) O(k) množina operací přiřazených stroji k p j doba provádění operace j na výrobní dávce příslušného výrobku zj nejdříve možný termín zahájení operace j M velké kladné číslo (horní mez celkové doby trvání všech prací) Cmax celková doba trvání všech prací (čas dokončení poslední práce) x jl

proměnná popisující precedenční vztah mezi operacemi j, l ∈ O(k): 1 … operace j se provede před operací l 0 … operace l se provede před operací j

Problém optimalizace výrobního rozvrhu pak lze matematicky formulovat takto: Minimalizovat

C max

(7)

za podmínek : C max ≥z i  p i ,

i = 1, … , n

(8)


Strana 23

z j ≥z i  p i ,

j = 1, … , N; i∈ B j

z l ≥z j p j x jl −M 1−x jl  ,

k = 1, … , m;

j , l ∈O k 

(10)

z j ≥z l  pl 1−x jl −M x jl ,

k = 1, … , m;

j , l ∈O k 

(11)

x jl ∈ { 0,1 } ,

k = 1, … , m;

j , l ∈O k 

(12)

C max ≥0 , z j ≥0 ,

j = 1, … , N

(9)

(13)

Podmínka (9) zajišťuje, že operace na každé práci se provádějí v předem určeném pořadí. Omezení (10)-(12) určují, že v určitém čase může být na jednom stroji pouze jedna operace. Jakékoliv přípustné řešení vyhovující podmínkám (8)-(13) je proveditelné a nazývá se rozvrh. Při rozvrhování ve skutečné výrobě se mohou sledovat i jiné cíle, např. minimalizace ztrát spojených s nesplněným prací v požadovaných termínech, minimalizace prostojů, atd. 3.3 Metody řešení Problém rozvrhování patří mezi obecně mezi NP-úplné problémy, což znamená, že přesné optimalizační metody jsou prakticky použitelné pouze pro úlohy omezeného rozsahu. Rozsáhlejší problémy je nutno řešit heuristickými metodami, které sice nezaručují nalezení optimálního řešení ani nedokážou stanovit, jak blízko se k optimu určité přípustné řešení nachází, ale jsou schopny v přiměřené době poskytnout „uspokojivé“ řešení. Speciální kapitolou heuristických algoritmů jsou evoluční algoritmy. Tyto algoritmy jsou založeny na myšlence simulace některých v přírodě se vyskytujících procesů. Mezi nevýhody těchto algoritmů patří pravděpodobnostní charakter výsledků. Z toho vyplývá, že po každém spuštění se může dojít k jinému výsledku. Mezi základní a nejznámější evoluční algoritmy v současné době patří: • Genetický algoritmus (Genetic algorithm) • Simulované žíhání (Simulated annealing) • Zakázané hledání (Tabu search)

Strana 24


Strana 25

4

HEURISTICKÉ METODY

Slovo heuristika je odvozeno od řeckého slova heuriskein, což znamená nalézt, nebo objevit. Heuristické metody jsou metody pro hledání „dobrých“ řešení (tj. řešení blízkých optimálnímu) pomocí intuitivních přístupů a při rozumných výpočetních nákladech. Obecně heuristická metoda nemůže zaručit nalezení globálního optima a obvykle ani stanovit, jak blízko je nalezené řešení od optimálního. Heuristické metody se používají pro řešení úloh s velkým rozměrem nebo složitou strukturou, u nichž by výpočet pomocí exaktních metod byl časově velmi náročný. Nejjednodušší (ale nejméně efektivní) heuristickou metodou je tzv. metoda lokálního hledání (local search method). Je to vlastně gradientová metoda bez gradientu, kdy se směr nejprudšího spádu určí kompletním prohledáním sousedství. Tento algoritmus trpí základní nectností gradientových metod, tj. že nejspíše skončí v některém lokálním optimu. Tomuto algoritmu se nebudu věnovat podrobně, spíše se zaměřím na nejčastěji používané metody. 4.1 Horolezecký algoritmus (Hill climbing) Horolezecký algoritmus patří do skupiny algoritmů, ve kterých jsou dovoleny i kroky směřující ke zhoršení aktuálního řešení. Podobně jako v metodě lokálního hledání v každém kroku vybíráme nejlepší řešení ze sousedních řešení. Rozdíl je v tom, že podmínkou ukončení algoritmu není nalezení zlepšujícího řešení mezi sousedními řešeními, ale provedení určitého počtu iterací. V průběhu celé historie algoritmu zaznamenáváme nejlepší dosažené ř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 iteračních kroků vrací k lokálně optimálnímu řešení, které se již vyskytlo v některém předcházejícím kroku (problém zacyklení). Tento problém se částečně řeší tak, že se algoritmus spustí několikrát z různých náhodně vygenerovaných počátečních řešení a za výsledek se bere nejlepší z několika průběhů. Možnou modifikací horolezeckého algoritmu je, že v každé iteraci nebudeme generovat všechna sousední řešení aktuálního řešení, ale například pouze jejich náhodně zvolenou část. Princip horolezeckého algoritmu: 1. Zvolíme náhodně počáteční přípustné řešení 2. Pro aktuální řešení vygenerujeme všechna sousední řešení a vypočteme pro ně hodnoty účelové funkce 3. Ze sousedních řešení vybereme takové, která má nejnižší hodnotu účelové funkce a zvolíme ho jako nové aktuální řešení 4. Dokud není proveden předepsaný počet iterací pokračujeme bodem 2 Horolezecký algoritmus jsem zde uvedl z toho důvodu, protože z něj vychází simulované žíhání, které jsem implementoval v programové realizaci této práce. 4.2 Simulované žíhání (Simulated annealing) Základy této metody byly poprvé publikovány již v roce 1953 v algoritmu, který simuloval chladnutí materiálu v horké lázni. V roce 1980 Kirkpatrick navrhl, že by tento typ simulace mohl být použit ke hledání přípustných řešení optimalizačního problému s cílem zajistit konvergenci k optimálnímu řešení. Simulované žíhání je variantou horolezeckého algoritmu, v němž heuristické kroky směřující k horšímu řešení jsou vždy řízeny určitou pravděpodobností. Přístup simulovaného

Strana 26

4 Heuristické metody

žíhání je založen na simulování fyzikálních procesů probíhajících při odstraňování defektů krystalické mřížky. Krystal se zahřeje na určitou (vysokou) teplotu a potom se pomalu ochlazuje (žíhá). Defekty krystalické mřížky mají při vysoké teplotě vysokou pravděpodobnost zániku. Pomalé ochlazování systému zabezpečí, že pravděpodobnost vzniku nových defektů klesá. Pří žíhání se soustava snaží dostat do takového stavu, ve kterém je její energie minimální – tj. krystal bez defektů. Existuje určitá analogie tohoto přírodního procesu s procesem řešení optimalizačních problémů. Metoda simulovaného žíhání simuluje změny energie systému, dokud není dosaženo ustáleného stavu. V průběhu výpočtu jsou dovoleny i kroky směřující k horšímu řešení. Frekvence těchto kroků je řízena pravděpodobnostní funkcí, která vyjadřuje zákony termodynamiky, podle nichž je při teplotě t pravděpodobnost růstu energie o δE dána vztahem: − E , (14) P  E =exp  kt kde E je energie [J], t je teplota [K], a k je Boltzmanova 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 (14). V literatuře je popsána podrobná teorie simulovaného žíhání. Byly dokonce dokázány existenční teorémy, za jakých podmínek simulované žíhání poskytuje globální minimum funkce ƒ(x) v definičním oboru x. Často se používá rozšíření simulovaného žíhání směrem ke genetickému algoritmu. Místo jednoho řešení se současně optimalizuje simulovaným žíháním malá populace řešení, které si vždy po určitém počtu kroků s malou pravděpodobností vymění informaci operací totožnou křížením z genetického algoritmu. Generická rozhodnutí se týkají volby parametrů algoritmu. Jedná se o počáteční teplotu, počáteční počet opakování, pravidla pro snižování teploty (funkce α), funkci γ, která slouží k ke změně počtu opakování, a podmínku zastavení výpočtu. Ke snižování teploty se často používá fce. (15) t =at kde 0 < a < 1. Nejčastěji se používají a hodnoty (0,8 – 0,99). Délka vnitřního cyklu se může zvětšovat geometricky (16) nebo aritmeticky (17).  n=bn ,b1

(16)

 n=nc , c0

(17)

Tato generická rozhodnutí se používají z důvodu, že pokud se blížíme nějaké optimální hodnotě, tak je potřeba prohledávat větší okolí dosud nejlepšího nalezeného řešení. Princip simulovaného žíhání: 1. Zvolíme si podmínku ukončení a počáteční počet opakování n 2. Náhodně vygenerujeme počáteční přípustné řešení problému x0 a položíme xmin = x0 3. Pokud není splněna podmínka pro ukončení cyklu, provádíme kroky 3.1 až 3.3 3.1 Opakujeme kroky 3.1.1 až 3.1.4 dokud není počet opakování roven n 3.1.1 Náhodně vybereme sousední řešení x1 3.1.2 Položíme δ = f(x1) – f(x0) 3.1.3 Jestliže δ < 0 provedeme krok 3.1.3.1, jinak provedeme krok 3.1.3.2 3.1.3.1 Položíme x0 = x1 3.1.3.2 Náhodně vygenerujeme hodnotu r z intervalu <0, 1>. Jestliže


Strana 27

r < exp(-δ/t), položíme x0 = x1 3.1.4. Je-li f(x1) < f(xmin), pak položíme xmin = x1 3.2 Dosavadní hodnotu t nahradíme hodnotou α(t) 3.3 Dosavadní hodnotu n nahradíme hodnotou γ(n) 4. Řešení xmin je aproximací optimálního řešení 4.3 Zakázané hledání (Tabu search) Metodu zakázaného hledání navrhnul koncem 80. let Glover jako zobecnění horolezeckého algoritmu k řešení optimalizačních úloh z operačního výzkumu. Základem metody je hledání nejlepšího souseda ze sousedství jednotlivých řešení. Zakázané hledání vychází z horolezeckého algoritmu, kde se pro dané aktuální řešení generuje pomocí konečné množiny transformací množina sousedů. V průběhu algoritmu se zaznamenává nejlepší řešení, které slouží jako výsledné optimální řešení. Nevýhodou tohoto algoritmu je, že se po určitém daném počtu iteračních kroků vrací k lokálnímu řešení, které se již vyskytlo v předchozích krocích. Tento nedostatek Glover vyřešil zavedením tzv. krátkodobé a dlouhodobé paměti. Krátkodobá paměť (tabu list) 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 něj dodá transformace, která poskytla lokální optimální řešení. Po naplnění tabu listu se v každé iteraci provede aktualizace tabu listu (délka zákazu u všech pohybů se sníží o jedna). Důležitým parametrem je délka tabu listu. Jestliže je velikost malá, pak může dojít k zacyklení. Jestliže je délka příliš velká, pak s velkou pravděpodobností vynecháme lokální minima, která by mohla být globálními minimy. Proces hledání lze významně zdokonalit použitím tzv. aspiračních kritérií. Aspirační kritérium je podmínka, která za určitých okolností dovoluje ignorování tabu omezení (např. zakázaný pohyb vede k řešení, které je lepší než všechna dosud dosažená řešení). 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. Rozlišujeme dva procesy, intenzifikaci a diverzifikaci. Intenzifikační strategie se při hledání řešení zaměřují na podporu „dobrých“ atributů. Diversifikační strategie namísto toho generují řešení zahrnující atributy významně odlišné od těch, které se vyskytly v procesu dosavadního hledání. Existují dvě metody výběru sousedů: • Metoda nejstrmějšího spádu – prohledává se množina sousedů aktuálního řešení a vybírá se to řešení, které nejvíce snižuje hodnotu účelové funkce • Metoda náhodného spádu – v náhodném pořadí se prohledávají sousedé aktuálního řešení a vybírá se první řešení s nižší hodnotou účelové funkce Technika zakázaného prohledávání může být použita jak v klasickém spojení s horolezeckým algoritmem, tak i v kombinaci s jinými algoritmy. U ostatních metod však není natolik efektivní, neboť tyto metody neprohledávají celé sousedství aktuálního řešení a pravděpodobnost zapůsobení zakázaného seznamu je tedy dost malá. Princip zakázaného hledání: 1. Zvolíme délku tabu listu a počet iterací 2. Vygenerujeme počáteční přípustné řešení problému x0 a položíme xmin = x0 3. Pokud není splněna podmínka pro ukončení, tak provádíme kroky 3.1 až 3.5 3.1 Vygenerujeme množinu přípustných sousedů N(x0) nepatřící do tabu listu * * 3.2 Vybereme  x ∈ N  x0  takové, že f  x =min f  x  , x ∈S  x 0  3.3 Položíme x0 = x*

Strana 28


3.4. Je-li f(x*) < f(xmin), pak položíme xmin = x* 3.5. Aktualizujeme tabu list a zvýšíme počet iterací o jednu 4. Bod xmin je aproximací optimálního řešení 4.4 Genetické algoritmy (Genetic algorithms) Genetické algoritmy jsou inspirovány Darwinovými zákony přirozeného výběru. V evolučním vývoji nebo při šlechtění rostlin či živočichů se prosazují jedinci, kteří mají jisté žádoucí charakteristiky, které jsou na genetické úrovni determinovány kombinací rodičovských chromozomů. U zrodu genetických algoritmů stála myšlenka, že při hledání lepších řešení složitých problémů by bylo možno obdobným způsobem kombinovat části existujících řešení. Ačkoli genetické algoritmy nemají již prakticky s biologií nic společného, udržují si biologickou terminologii. Evolucí jsou míněny postupné změny proměnných vedoucí k nalezené extrému funkce. Soubor proměnných vstupních veličin funkce tvoří jedince (někdy je formálně jedinec nazýván chromozómem). Není zde však důležitý samotný jedinec, jako postupný vývoj, kooperace a fungování populace – soubor jedinců. Neúspěšní jedinci vymírají, úspěšní přežívají a množí se. Při aplikaci genetických algoritmů na problémy operačního výzkumu každý jedinec v algoritmu nějakým způsobem kóduje jedno řešení x problému. V případě rozvrhování výroby bude jedince, zřejmě jeden přípustný rozvrh. Hodnota zdatnosti (fitness) jedince odpovídá hodnotě účelové funkce ƒ(x) v tomto řešení. Pro manipulace s chromozómy se používají genetické operátory selekce (selection), křížení (crossover) a mutace (mutation). Při selekci se jedná o výběr jedinců z celkové populace, kteří se stanou rodiči. Důležitým hlediskem, jenž se přímo či nepřímo uplatňuje při výběru alespoň jednoho z rodičů, je právě jeho zdatnost. Hybnou silou změn jsou křížení (výměna genetické informace mezi jedinci) a mutace (velmi málo pravděpodobné provedení náhodné změny chromozómu, zabraňující zdegenerování populace). Genetické algoritmy pracují tím způsobem, že se nejprve vytvoří počáteční populace o velikosti p jedinců a pak se tato populace mění pomocí genetických operátorů tak dlouho, dokud není splněna nějaká podmínka ukončení. Počáteční populace se většinou získá náhodným generováním. Byly provedeny také pokusy nasadit do počáteční populace kvalitní řešení, získaná jinými heuristickými metodami, ale při tomto způsobu se ukázalo nebezpečí předčasné konvergence do nějakého ještě ne dost dobrého lokálního optima. Pokud jde o velikost p populace, je jasné, že příliš malá populace může zavinit špatné pokrytí prostoru řešení, zatímco velká populace zvyšuje výpočetní náročnost. Zkušenosti ukazují, že pro většinu problémů je dostačující populace o velikosti 50 až 200 jedinců. Selekcí je třeba z populace vybrat zdatné jedince (s dobrou hodnotou fitness), kteří se potom stanou rodiči. Rodiče se vybírají pseudonáhodně. Zdatnější jedinci mají větší šanci být vybráni než méně zdatní jedinci. Čím je jedinec zdatnější (čím má větší hodnotu fitness), tím je pravděpodobnost jeho výběru ke křížení větší. Pokud se výběr uskutečňuje v souladu s rozdělením pravděpodobnosti, počítané jako podíl hodnoty fitness chromozómu k celkové hodnotě fitness populace, označujeme tento způsob výběru jako „ruleta“. Jiným způsobem selekce je například soutěžení (tournament). Soutěže se účastní část populace a její vítěz, nejzdatnější účastník soutěže, se pak stane rodičem. Křížení se pro vybranou skupinu rodičovských chromozómů může uskutečňovat několika způsoby. Například pro případ, kdy je jedinec reprezentován sekvencí čísel úloh, představuje nejjednodušší přístup tzv. jednobodové křížení, při němž se zvolí náhodně nějaký bod, dělící oba rodičovské chromozómy na dvě části. Jeden potomek pak zdědí levou část


Strana 29

z prvního rodiče a na zbývající pozice se mu doplní chybějící prvky v tom pořadí, v jakém se vyskytují ve druhém rodiči, druhý potomek vznikne analogicky s obráceným pořadím rodičů. Mutace je v obecnosti malá náhodná změna jedné, či několika proměnných (prvků chromozómu), která ovlivní řešení, ať už kladně nebo záporně. Pravděpodobnost uskutečnění mutace je nízká (obvykle menší než 1%). Mutace je nutná k tomu, aby se zamezilo přílišné specializaci – zapadnutí celé populace do jednoho lokálního minima, aby vždy byla možnost vytvoření zásadně nových chromozómů odpovídajících lepšímu řešení. Mutace přinášejí do chromozómů novou genetickou informaci. Pro mutaci mohou být použity stejné operátory, jakými lze generovat sousední řešení v předchozích popsaných metodách. Jednou z možností změny p-členné populace je vygenerovat pomocí křížení a mutace novou generaci p potomků a nahradit jí rodičovskou generaci en bloc. Jiné způsoby umožňují nějaké překrývání populace rodičů a potomků a populaci tedy mění inkrementálně. Např. vygenerovaný potomek nahrazuje pseudonáhodně vybraného slabého příslušníka aktuální populace. Princip genetických algoritmů: 1. 2. 3. 4.

Zvolíme velikost populace, počet generací, pravděpodobnost křížení a mutace Náhodně si vygenerujeme počáteční generaci Pokud byla splněna ukončující podmínka tak skončíme výpočet a vypíšeme řešení Opakujeme následující kroky, dokud není vytvořen požadovaný počet potomků 4.1. Pomocí selekce vybereme vhodné rodiče 4.2. Provedeme křížení rodičů a vytvoříme tak potomky 4.3. Provedeme mutaci potomků 5. Vytvoříme novou populaci a přejdeme zpátky na krok 3.

Strana 30


Strana 31

5

REPREZENTACE DAT

Pod pojmem reprezentace dat (kódování) v oblasti job – shop rozvrhování rozumíme vytvoření určitého způsobu zápisu posloupností operací na strojích do seznamu, který nám umožní provádění výpočtu na počítačích, nalezení co nejlepšího řešení v co nejkratším čase. Dále je třeba posuzovat navržené kódování z hlediska paměťových nároků a složitosti algoritmů, protože i když je dnes výpočetní technika na vysoké úrovni, heuristické výpočty patří neustálým opakováním stejných operací k jedněm z nejvíce náročných algoritmů na velikost paměti. Na zvoleném způsobu reprezentace dat záleží, které varianty se budou při heuristickém prohledávání zkoumat. Například pomocí kódování založeného na operacích vytváříme pouze takové kódy, které z hlediska uspořádání jednotlivých operací za sebou v jednotlivých pracích vytváří vždy správné rozvrhy. Otázkou ovšem zůstává, jestli tím, že vynecháme řešení, která jsou nesmyslná, zároveň neztratíme cestu k řešením, která by pro nás byla výhodná. Tyto a mnoho dalších úvah musí vzít programátor vytvářející program pro job – shop rozvrhování vzít v potaz. Při převádění zadání do seznamu musíme mít na zřeteli tři zásadní otázky kódování: • proveditelnost seznamu • legálnost řešení • jedinečnost seznamu Proveditelností rozumíme otázku, zda výsledné řešení dekódované ze seznamu leží v oblasti daného problému. Další otázkou je legálnost výsledku, a to z hlediska zejména pořadí jednotlivých operací na výrobcích apod. Poslední je jedinečnost námi vytvořeného seznamu, který musí odpovídat jedinečnému rozvrhu. 5.1 Způsoby reprezentace dat pro job – shop rozvrhování V průběhu let bylo navrženo několik způsobů reprezentace dat problému rozvrhování zakázkové výroby. Z nich uveďme alespoň ty základní: • • • • • •

reprezentace založená na úlohách (job-based representation) reprezentace založená na operacích (operation-based representation) reprezentace preferenčním seznamem (preference-list-based representation) reprezentace disjunktivním grafem (disjunctive graph-based representation) reprezentace založená na strojích (machine-based representation) reprezentace pomocí náhodných klíčů (random keys representation)

Tyto reprezentace se moho rozdělit podle přístupu na • reprezentace s přímým přístupem – rozvrh je zakódován do seznamu jednotlivých operací a heuristické metody vytváří přesně definovaná sousedství, kde probíhá vlastní hledání. Může to být např. reprezentace založná na operacích, reprezentace založená na pracích,... • reprezentace s nepřímým přístupem – místo rozvrhů se kódují sekvence pravidel, podle kterých následně uspořádáme operace. Cílem se tedy stává nalezení co nejlepší sekvence pravidel. Do této skupiny patří reprezentace preferenčním seznamem, reprezentace disjunktivním grafem a reprezentace založená na strojích. Nejvýhodnější reprezentací z hlediska použití při vytváření programu u heuristických metod se jeví reprezentace pomocí disjunktivního grafu, která je studována např. v [12].

Strana 32

5 Reprezentace dat

Srovnání reprezentací bylo provedeno např. v [3], kde jednoznačně lepší způsob byl u reprezentace pomocí disjunktivního grafu, která byla efektivnější i rychlejší než reprezentace pomocí preferenčního seznamu. 5.2 Disjunktivní graf Klasický disjunktivní graf G je definován množinou uzlů V, množinou konjunktivních hran C a množinou disjunktivních hran D, G=V , C∪D . Uzly reprezentují operace všech úloh, tedy výrobky, respektive položky výrobků. Množina uzlů V obsahuje navíc dva speciální uzly, počáteční 0 (nula) a koncový uzel * (hvězdička). Tyto speciální uzly jsou ohodnoceny nulami, ostatní uzly jsou ohodnoceny dobami trvání odpovídajících operací. Orientované konjunktivní hrany vyjadřují zadané pořadí operací v rámci jednotlivých úloh. Dále jsou zde hrany vycházející z počátečního uzlu 0 a směřující do uzlů příslušných prvým operacím úloh a hrany vycházející z uzlů příslušných posledním operacím úloh a směřující do koncového uzlu *. Disjunktivní hrany spojují operace, které musejí být provedeny na stejném stroji. Na začátku algoritmu jsou disjunktivní hrany neorientované. Příklad reprezentace problému disjunktivním grafem představuje obrázek 2.

Obr. 2 Disjunktivní graf Stanovit výrobní rozvrh znamená rozhodnout o pořadí operací na jednotlivých strojích, tedy stanovit orientaci disjunktivních hran. Množina S všech orientovaných disjunktivních hran se nazývá úplná selekce. Úplná selekce určuje přípustný rozvrh  pouze v případě, že výsledný graf G =V , C∪S  je acyklický. V tom případě se S nazývá acyklická úplná selekce. Příkladem rozvrhu pro problém znázorněný disjunktivním grafem na obrázku 2 může být ={4,1 ,7 ,6,2 , 5,3 ,8} , kde jednotlivé seznamy operací v kulatých závorkách představují pořadí operací na jednotlivých strojích. Celková doba zpracování všech úloh (makespan) je pak dána délkou nejdelší cesty z počátečního uzlu do koncového uzlu grafu. Tuto cestu nazýváme kritickou cestou. Máme-li vytvořen acyklický orientovaný graf, můžeme pomocí algoritmu nalezení kritické cesty CPM (critical path method) určit nejdříve možné časy dokončení operací. Než k tomu přistoupíme, můžeme ještě graf zjednodušit. Protože libovolná operace má na stejném stroji nejvýše jednu bezprostředně předcházející operaci a nejvýše jednu bezprostředně následující operaci, můžeme z grafu vypustit ty disjunktivní hrany, které nespojují uzly odpovídající bezprostředně po sobě následujícím operacím na stejném stroji. Ve zjednodušeném grafu bude každý uzel, s výjimkou uzlů 0 a *, mít nejvýše dva

5 Reprezentace dat

Strana 33

bezprostřední následníky a nejvýše dva bezprostřední předchůdce (viz obr. 3).

Obr. 3 Zjednodušený orientovaný disjunktivní graf

5.3 Montážní a distribuční operace Častým požadavkem při výrobě i méně složitých výrobků je potřeba kompletovat celek z více částí. S těmito celky také často provádíme další montážní operace, než vznikne konečný výrobek. Obrácenou operací montáže je operace typu distribuce (výsledky této operace se distribuují na několik bezprostředně navazujících operací). Například polotovar dělíme na více částí a z každé části vyrábíme jinou součást stejného nebo jiného výrobku. Disjunktivní graf lze snadno rozšířit o distribuční a montážní operace. V klasické podobě disjunktivního grafu má každý uzel (kromě uzlů 0 a *) v podgrafu G0 V , C  pouze jednoho předchůdce a pouze jednoho následníka. Problém s montážními operacemi lze jednoduše modelovat takovým způsobem, že připustíme, aby uzel reprezentující montážní operaci (obrázek 4b) měl více předchůdců, spojených s tímto uzlem konjunktivními hranami. Obdobně z uzlu reprezentujícího distribuční operaci (obrázek 4a) bude moci vystupovat více konjunktivních hran k uzlům reprezentujícím následující operace.

Obr. 4 a) distribuční operace, b) montážní operace Ukázku grafu G0 V , C  rozšířeného tímto způsobem můžeme vidět na obrázku 5. Operace 1 a 13 jsou distribuční a operace 10 a 16 jsou montážní.

Strana 34

5 Reprezentace dat

Obr. 5 Rozšíření disjunktivního grafu o distribuční a montážní operace 5.4 Časy přípravy, dopravní a technologické časy Obvykle se u klasického modelu rozvrhování počítá pouze s jedním výrobním časem operace (process time). Ale v praxi je doba výroby jedné operace dána více časy, které se musí také započítávat: čas přípravy, dopravní čas a technologický čas. Čas přípravy (setup time) je doba, která je nutná např. k seřízení stroje, namíchání barvy apod. Je to doba přípravy stroje, kdy ještě není bezpodmínečně nutné, aby byla dokončena předchozí operace na stejné úloze na jiném stroji. Musí se brát ale ohled na to, jestli se jedná o čas přípravy nezávislý na pořadí operací a čas přípravy závislý na pořadí operací. Dopravní čas (transport time) je doba potřebná k dopravě výrobku na další pracoviště. Technologický čas (technologic time) označuje dobu, po kterou musí výrobek ještě zůstat na pracovišti po skončení výroby, než může být přesunut na další stanoviště, může to být např. doba nutná k zaschnutí laku, odkapání oleje apod. Samotný stroj však už může být použit pro další výrobu. Dopravní a technologický čas mají na počáteční čas další operace stejný vliv, proto mohou být nahrazeny jednou hodnotou. Časy přípravy, výrobní, dopravní a technologické mohou být reprezentovány pomocí ohodnocení uzlů a hran v disjunktivním grafu.

Strana 35

6

NÁVRH ŘEŠENÍ PROBLÉMU

Problém řešení optimalizace výrobních dávek a rozvrhování výroby je úplný problém, který byl už řešen v mnoha odborných publikacích a stal se předmětem výzkumu použití heuristických metod při hledání optimálního řešení. Několikrát byla řešena buď jenom optimalizace výrobních dávek [17] nebo se hledal pouze optimální rozvrh [3], [15]. Pokusy řešit oba dva tyto problémy současně spočívaly v tom, že se přeskakovalo mezi hledáním optimálních dávek a přípustného optimálního rozvrhu [14], [16]. V této práci jsem se pokusil oba dva tyto problémy kombinovat, nejdříve je na každý nejlepší prvek z populace aplikována metoda simulovaného žíhání pro nalezení nejlepšího rozvrhu, a poté jsou na všechny prvky (generaci) použity genetické operátory. V následujících kapitolách je naznačena struktura, se kterou se pracuje, a algoritmus, který tvoří samotný program. 6.1 Použitý způsob reprezentace dat Jak už bylo naznačeno výše, jako nejvýhodnější se jeví reprezentace disjunktivním grafem. V práci [3], kde byla srovnávána s reprezentací pomocí preferenčního seznamu, bylo na testovacích příkladech prokázáno, že reprezentace pomocí grafu je daleko efektivnější a vede k lepším výsledkům. Při řešení této práce jsem vycházel z [4]. Disjunktivní graf je vytvořen z obecné výrobní struktury, jejímiž uzly jsou výrobky, resp. položky výrobků. Vazby v této struktuře jsou konjunktivní vazby. Disjunktivní vazby spojují ty dvojice výrobních položek, které se vyrábějí na stejném stroji. Jedná se tzv. zobecněný disjunktivní graf. Každé etapě plánovacího horizontu odpovídá jiný graf (s jinou strukturou) určený hodnotami Yit a případně hodnotami X'it , (část výrobní dávky Xit určená pro další výrobu v téže periodě). X'it = ∑ r i k X k t −I i , t−1 , (18) k ∈ A i

kde A(i) je množina bezprostředních následníků operace (položky) i ve výchozí konjunktivní struktuře. Tato definice se ale netýká uzlů, které odpovídají finálním výrobkům, tj. uzlů, pro něž platí A(i) = {*}. Pro tyto uzly klademe X'it = Xit. Dále můžeme označit B(i) množinu bezprostředních předchůdců operace (položky) i ve výchozí konjunktivní struktuře. Jestliže Yit = 0, potom se uzel odpovídající položce i v grafu periody t nebude vyskytovat. Uzly j  Ai , pro něž platí Yjt = 1, jsou propojeny konjunktivními hranami přímo s uzlem 0 (potřebné požadavky se budou brát přímo ze skladu), tzn. hrany (i, j) se nahradí hranami (0, j). Uzly j  Bi , pro něž platí Yjt = 1, jsou propojeny přímo s uzlem * (jejich výroba půjde přímo do skladu), tzn. hrany (j, i) se nahradí hranami (j, *). Pokud platí Yit = 1 a X'i t = 0, pak sice uzel i v grafu zůstane, ale hrany (i, j), pro něž platí Yjt = 1, se nahradí hranami (0, j). Po těchto úpravách se v grafu nachází množina uzlů Vt, množina konjunktivních hran Ct, a každý uzel i má množinu A(i, t), která obsahuje všechny bezprostřední následníky operace i v periodě t a množinu B(i, t), která obsahuje všechny bezprostřední předchůdce operace i v periodě t. Symbolem b(i, t) lze označit bezprostředního předchůdce položky i na stejném stroji v periodě t a symbolem a(i, t) lze označit bezprostředního následníka položky i na stejném stroji v periodě t.

Strana 36

6 Návrh řešení problému

6.2 Relace sousedství Myslím, že je na místě zde zavést pojem sousedství rozvrhu. Pro použití většiny heuristických metod je nutné definovat určitou relaci sousedství, která pro každé přípustné řešení x umožňuje pomocí nějaké stanovené množiny transformací S(x) stanovit jeho okolí U(x) jako podmnožinu přípustných řešení sousedících s x. V případě problému rozvrhování výroby je přípustným řešením určitá množina proveditelných sekvencí operací na jednotlivých strojích. Sousedství je tedy množina rozvrhů, které lze získat aplikováním operátoru přechodu do jiného rozvrhu. Pro každý tento jednotlivý rozvrh je možné vypočítat hodnotu účelové funkce. V této práci byla jako účelová funkce vybrána celková doba trvání všech úloh (makespan). Cílem optimalizace je najít přípustnou množinu sekvencí na strojích s nejmenší hodnotou účelové funkce. Definice sousedství byla podrobněji řešena v [3]. Jelikož se snažíme snížit hodnotu makespanu, musí se měnit operace ležící na kritické cestě. Po několika pokusech s různýmy množinami sousedství jsem se rozhodl pro variantu s náhodným přepínáním mezi dvěma variantami: • Náhodně si najdeme stroj, který má nejméně dvě operace, které leží na kritické cestě. Následně pak procházíme jeho sekvenci operací, kde postupujeme od počátku. Až se narazí na uzel ležící na kritické cestě, tak se příslušná operace prohodí s předchozí operací, která na kritické cestě neleží. Pokud je tato sekvence proveditelná, tak se algoritmus ukončí, jinak se snažíme měnit následné dvě operace až do té doby, pokud není nalezena povolená sekvence pořadí na vybraném stroji. • Druhá varianta je v podstatě totožná s první, opět hledáme zdroj s nejméně dvěma kritickými operacemi, jen s tím rozdílem, že poté procházíme jeho sekvenci operací od konce. Když se narazí na uzel ležící na kritické cestě, pokusíme se vyměnit tuto operaci s operací následující, pokud to nejde (graf obsahuje cyklus, je to poslední operace na stroji), potom přejdeme na předchozí operaci. Takto postupujeme do doby, než je nalezeno proveditelné řešení. 6.3 Popis algoritmu Jak už bylo uvedeno výše, nadřazeným algoritmem je genetický algoritmus pro optimalizaci výrobních dávek. Velikost populace je označena jako VelPop a počet generací PocGeneraci. V práci [17] byly řešeny tři algoritmy pro zachování přípustností, jeden zachovává přípustnost jen z hlediska kapacit a další dva z hlediska zásob. Z těchto algoritmů se jako nejlepší projevil upravený algoritmus zachovávající přípustnost z hlediska zásob a posuvem dopředu i dozadu. Tento algoritmus bylo ovšem potřeba upravit, protože v [17] se předpokládá okamžitá výroba a možnost současného sdílení zdrojů. Další úpravy vycházejí z [4]. 1. Pokud je počet period vyšší než 1, pokračuj na krok 2, jinak proveď kroky 4.6.1 4.6.5 mimo kro 4.6.3. Hodnoty Y budou rovny 1, hodnoty X vypočítej z vnější poptávky, viz. krok 4.2 a vzorec (22). Potom výpočet ukonči a vypiš řešení. 2. Náhodně vygeneruj počáteční generaci oldpop 3. Pokud je počet generací menší nebo roven PocGeneraci, nebo pokud není splněna některá z podmínek pro ukončení algoritmu, proveď kroky 3 a 4, jinak ukonči výpočet a vypiš dosud nalezené nejlepší řešení: 4. Pro všechny prvky z oldpop proveď následující kroky: 4.1 Vypočítej počáteční řešení bez ohledu na kapacitní omezení. Urči hodnotu Xit odpovídající hodnotě Yit následovně:


Strana 37

Jestliže Yit = 0, potom Xit = 0 Jestliže

Y i  =1 , Y i  =1 , 1 2T , a Yit = 0 pro Yit = 0 pro 1tT a  2=T 1 ), potom 1

2

 2−1

X i , 1= ∑  d it − t= 1

∑

j ∈S  i

r ij X jt 

1t 2 (nebo

(19)

4.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, Y i , 1=1 kde 

1=min { / I i0 ∑ Dit }

(20)

t=1

kde Dit =d it 

∑

j∈ S i 

r ij D jt

Xit = 0 pro t = 1, 2, …, τ1 - 1 a  2−1

X i  1= ∑  d it  t =1

∑

j ∈S  i

r ij X jt 

(22)

kde  2=min {t /t1, Y it =1 }

Předpokládáme, že počáteční zásoby jsou rovny 0. 4.3 Pro všechny výrobky a všechny periody urči zásoby Iit odpovídající hodnotám Xit I it =I i ,t −1 X it −d it −

∑

j∈ S i 

r ij X

jt

1
(23)

4.4 Pro všechny periody urči následujícím způsobem rezervy v konjunktivní struktuře a hodnotu C*t (dolní hranice hodnoty makespanu). V každé periodě uvažujeme konjunktivní strukturu Gt = (Vt , Ct), tzn. graf upravený v závislosti na hodnotách Yit a X'it , k němuž jsou přidány uzly 0 a *. Dále o= o0 , o 1 ,... , o*  je pořadí operací z Vt , kde platí: jestliže oi , o  j ∈C t , pak i < j. Nt je počet položek, které se v periodě t vyrábějí. Nejdříve možné termíny zahájení je možné vypočítat následovně: z 0 t =0 z jt =max {z it i X 'it /i∈ B j ,t } (24) kde výpočet postupuje v pořadí j = o(1), o(2), … , o(Nt) z*t = max {z it  pit i∈V t } , C*t = z*t (25) Nejpozději možné termíny zahájení operací zit se vypočtou takto: z* t =z * t zit =min {min { zj t / j∈Ai , t− i X 'it }, z* t − p it } (26)

Strana 38


kde výpočet postupuje v pořadí i = o(Nt), o(Nt – 1), …, o(1) Celkové rezervy všech operací jsou dány vztahem Rit = zit −z it

(27)

4.5 U všech period zkontroluj platnost podmínky C *t ≤ t , (28) pokud u všech period platí, pak přejdi na krok 5, jinak se pokus splnění podmínky docílit pomocí přesunů výroby. Pokud se to podaří, přejdi na krok 4, jinak pro všechny periody proveď kroky 4.5.1 až 4.5.4 Protože je popis přesunů výroby poněkud obsáhlejší, z důvodu přehlednosti jsou popsány v samostatné kapitole 6.4. 4.5.1 Vypočítej nějaký počáteční proveditelný rozvrh, viz. kapitola 6.5 4.5.2 Vypočítej hodnotu Cmax, t (makespan) – viz. krok 4.6.2, aby bylo možné vypočítat hodnotu penalizačního členu, která se určí T

∑ M ⌈max {0, C max ,t − t }⌉2

(29)

t =1

4.5.3 Urči hodnotu účelové funkce (fitness) 4.5.4 Vezmi další prvek a přejdi na krok 2 4.6 Nejprve zpracuj periody v pořadí 1, 2, …, T – 1 a pak v pořadí T, T – 1 , …, 2. Pro každou periodu proveď následující kroky: 4.6.1 Pro periodu t vypočítej nějaký počáteční přípustný rozvrh. 4.6.2 Urči celkové rezervy v disjunktivní struktuře a hodnotu makespanu Cmax následujícím způsobem: Uvažujeme nyní graf G(St) = (Vt , C t ∪S t ), kde St je nějaká redukovaná acyklická úplná selekce. Nejdříve možné termíny zahájení operací se vypočítají následovně: z0 t = 0, z jt =max {max {z it i X 'it /i∈B  j , t}, z b  j ,t , t pb  j , t ,t  j } (30) kde výpočet postupuje v pořadí j = o(1), o(2), …, o(Nt) z*t = max {z it  pit i∈V t } ,

(31)

Nejpozději možné začátky zahájení operací żit se vypočtou takto: z* t =z * t zit =min {min { zjt / j∈ Ai , t}− X 'it , z a i ,t  ,t − pi ,t − a  i , t } (32) kde výpočet postupuje v pořadí i = o(Nt), o(Nt – 1), …, o(1) Celkové rezervy všech operací jsou opět dány vztahem Rit = z it −z it

(33)

Makespan je rovný termínu koncového vrcholu Cmax, t = z*t. 4.6.3 Pokud platí podmínka C max , t≤ t , potom přejdi na další periodu a krok 4.6.1 (pokud už jsou všechny periody zpracovány, přejdi na krok 4.6.5). Pokud podmínka neplatí, přejdi na krok 4.6.4.


Strana 39

4.6.4 Za využití heuristické metody simulovaného žíhání (viz. kapitola 5.2) optimalizuj rozvrh a pokus se nalézt výrobní rozvrh s nižší hodnotou makespanu. Pro výběr sousedního řešení f(x1) použij algoritmus popsaný v kapitole 7.2. Pokud platí podmínka C max , t≤ t , potom přejdi na další periodu a krok 4.6.1 (pokud už jsou všechny periody zpracovány, přejdi na krok 4.6.5), jinak přesuň část produkce do sousední periody. Přesouvaná množství urči podobně jako u konjunktivní struktury a jsou opět popsaná v kapitole 7.4. 4.6.5 Vypočítej hodnotu fitness podle vzorce N

T

T

fit =∑ ∑  sit Y it c it X it hit I it ∑ M ⌈ max {0, C max ,t −t }⌉ 2 i=1 t =1

(34)

t=1

Pokud jsou všechny prvky z oldpop zpracované přejdi na krok 5, jinak vezmi další prvek a přejdi na krok 4.1. 5. V následujících krocích se aplikují genetické operátory: 5.1 Počet prvků z generace newpop dej roven 0. Do newpop přidej nejlepšího jedince z oldpop. 5.2 Podle zvolené selekce vyber z oldpop rodiče Y 0, j1 , Y 0, j2 0, j2 0, j1 5.3 Proveď mutaci vybraných rodičů Y , Y . Pravděpodobnost mutace je označena jako PravdMutace a její průběh byl popsán v kapitole 5.4 5.4 Proveď křížení vybraných rodičů Y 0, j1 , Y 0, j2 . Pravděpodobnost křížení je označena PravdKrizeni. 5.5 Do populace newpop přidej nové chromozomy Y 0, j1 , Y 0, j2 5.6 Pokud je počet chromozomů v newpop roven velikosti populace, jdi na krok 5.7, jinak jdi na krok 5.2 5.7. Zvyš počet generací o jednu, překopíruj generaci oldpop do newpop a přejdi na krok 2 6.4 Přesuny výroby K přesunutí části výrobní dávky z jedné periody do následující nebo předchozí musí * dojít tehdy, pokud není splněna podmínka C t ≤ t u konjunktivní struktury a C max , t≤ t u strukutry disjunktivní. Označme symbolem Rt časovou rezervu periody t. Při práci s konjunktivní strukturou (krok 3.5 algoritmu) je * Rt =t −C t (34) Pokud pracujeme s disjunktivní strukturou (krok 3.6.4 algoritmu) je Rt =t −C max ,t (35) K přesunu části výroby musí dojít, pokud je Rt 0 (u konjunktivní struktury okamžitě a u disjunktivní struktury v okamžiku, kdy tento problém nelze odstranit optimalizací rozvrhu). Smysl má přesouvat pouze takovou velikost výrobních dávek, která se nachází na kritické cestě. Kritická cesta je nejdelší cesta v grafu a její délka je rovna C max , t . Tato cesta začíná

Strana 40


ve vrcholu 0 a končí ve vrcholu *. Uzly (operace) na ní ležící nemají žádnou časovou rezervu, proto každé jejich zpoždění ve výrobě prodlužuje celkovou dobu trvání výroby. Tyto uzly můžeme určit např. takto: • předchůdce vrcholu * na kritické cestě je vrchol, který maximalizuje výraz na pravé straně rovnice (30) • jestliže operace leží na kritické cestě, pak jejím předchůdcem na této cestě je vrchol, který maximalizuje výraz na pravé straně rovnice (29) Pokud je kritických cest více, je nutné současně na všech provést stejné zkrácení. Uvažujme nyní snížení dávky X it o hodnotu  X it . Nelze přesunout více, než je velikost výrobní dávky, proto musí platit  X it ≤X it (36) Dále také nemá smysl přesouvat více, než nutné, tedy dále platí  X it ≤−Rt /i

(37)

Při přesunu výroby nesmí dojít k porušení rovnováhy zásob, musí platit další podmínka  X it ≤I it při přesunu vpřed z periody t do periody t + 1 (38) I j t −1  X it ≤ pro všechna j∈ B i , t  při přesunu vzad z periody t do periody t–1 r ji (39) Po přesunutí dávky musí kritická cesta zůstat kritickou. Označme symbolem K it , který začíná bezprostředně za uzlem i. Pak musí platit  X it ≤R jt /i pro všechna k ∈ K it , j∈B k , t∪b k ,t  , j∉K it , (40) kde R jt je celková rezerva operace j. Zjednodušeně formulováno, zkrácení nemůže být větší než celková rezerva jakékoliv nekritické operace, která je bezprostředním předchůdcem nějaké kritické operace z úseku K it . Přesouvanou část výrobní dávky  X it tedy můžeme určit následovně: • při přesunu vpřed z periody t do periody t + 1: R R  X it =min {X it ,− t , I it , min { jt / j ∈B k ,t ∪b k , t−K it , k ∈ K it }} (41) i i při přesunu vzad z periody t do periody t – 1: Rt I j , t−1  X it =min { X it ,− , min { / j∈Bi ,t } , i r ji R min { jt / j∈ B k , t ∪b k , t− K it , k ∈ K it } } (42) i Při snaze o zlepšení (snížení) hodnoty makespanu může být výhodné i přesunutí většího množství produkce, tento případ zde ale neuvažujeme. Pokud nastane případ, kdy je nutné snížit současně několik dávek o část výrobní dávky  X , označme symbolem Z množinu zkracovaných kritických operací, které se nacházejí na více kritických cestách (žádné dvě operace se nesmějí nacházet na jedné kritické cestě). Potom  X =min { X it /i∈Z } •


Strana 41

Pokud chceme přesunout část výrobní struktury u konjunktivní struktury, provádíme nejprve přesuny vpřed postupně pro periody 1, 2, … , T – 1, přičemž při určování přesouvaného množství se bude postupovat od konce kritické cesty (cest). Následně se bude budou provádět přesuny vzad postupně pro periody T, T - 1, … , 2 , přičemž při určování přesouvaného množství se bude postupovat od začátku kritické cesty (cest). U disjunktivní struktury je možné použít dvě strategie, které se liší v tom, zda se případné přesuny provádějí do sousední periody bez ohledu na její časovou rezervu, nebo do nejbližší volné periody do výše její časové rezervy. Zde uvažujeme první případ, který je jednodušší, stačí tam určit množství, které chceme přesunout a v periodě, kam přesouváme, nemusí existovat vytvořený rozvrh. Opět se postupuje jako u konjunktivní struktury. Při přesunutí výrobní dávky dochází k následujícím akcím. Při přesunu vpřed z periody t do periody t + 1: X it :=X it − X 1. je – li poté X it =0 , pak bude Y it :=0 a změní se struktura grafu X i t 1 := X it 1  X 2. je – li Y i t 1=0 , pak bude Y i t 1 :=1 a změní se struktura grafu I it :=I it − X 3. I jt :=I jt r ji  X pro j ∈B i ,t  4. 5. Následně se vypočtou hodnoty X 'jt pro j ∈B i ,t  a bude-li poté X 'jt =0 , změní se struktura grafu 6. Znovu se vypočte hodnota X 'i t 1 a dojde-li ke zvýšení z nuly na nenulovou hodnotu, změní se struktura grafu 7. Po provedeném přesunu bude nutné znovu přepočítat rezervy. Při přesunu vzad z periody t do periody t – 1: X it :=X it − X 1. je – li poté X it =0 , pak bude Y it :=0 a změní se struktura grafu X i t −1 := X it −1 X 2. je – li Y i t −1=0 , pak bude Y i t −1 :=1 a změní se struktura grafu I i t−1 :=I i t−1 X 3. I j t−1 :=I j t −1−r ji  X pro j ∈B i ,t−1 4. 5. Následně se vypočtou hodnoty X 'jt −1 pro j ∈B i ,t−1 a dojde-li ke zvýšení z nuly na nenulovou hodnotu, změní se struktura grafu 6. Znovu se vypočte hodnota X 'it a bude – li poté X 'it =0 tak se změní struktura grafu 7. Po provedeném přesunu bude nutno znovu přepočítat rezervy. 6.5 Algoritmus pro nalezení počátečního rozvrhu Pro nalezení počátečního proveditelného rozvrhu jsem použil metodu, kterou navrhli Giffler a Thompson [18] a která byla prezentovaná v [3]. Algoritmus má následující podobu: Q(t) množina všech nerozvržených operací v čase t ri nejříve možný čas zahájení operace Ti Ci nejdříve možný čas dokončení operace Ti begin t := 0;

Strana 42

6 Návrh řešení problému Q(t) := {o1, …, on}; Pro všechna i∈1,... , n nastav ri := 0; repeat * Nechť O j ∈Q t  je operace s nejmenším

časem

dokončení,

* j

C =min {C j / o j ∈Q t , C j=max {t , r j } , p j } . Nechť M na kterém je prováděna; Náhodně vyber operaci oi z konfliktní množiny { být zpracovávána na stroji

Qt =Qt −{oi } ; Modifikuj

Cj

pro

všechny

zpracovávat na stroji

* k

M a r j C

operace

M

* k

* j

* k

tj.

je stroj

o j∈Q t/o j musí

} a tu rozvrhni;

o j∈Q t , které se budou

; *

Nastav t na další rozvrhovatelnou operaci, tj. C i min {C i } , oi se zpracovává na nějakém stroji Mk a existuje ještě alespoň jedna operace c Q(t), která se bude zpracovávat na stroji Mk; r *j :=min{r j /o j ∈Q t } ;

t :=max {C *i , r *j } ; until Q(t) je prázdná; end;

Upravená podoba tohoto algoritmu byla prezentována také v [13]. Tento algoritmus nám poskytne náhodný přípustný rozvrh, kterému budeme moci přiřadit hodnotu účelové funkce.

Strana 43

7

REALIZACE PROGRAMU

Program k této práci byl vytvořen ve vývojovém prostředí Delphi 7. Spustitelný soubor se nazývá PlanovaniARozvrhovani.exe a nachází se na přiloženém CD i s nejdůležitějšími knihovnami, zadáním příkladů i jejich řešeními. 7.1 Hlavní okno Hlavní menu programu je rozděleno do 4 částí, v první se pracuje se samotnými soubory příkladů, v druhé se nastavují všechny parametry problému i parametry pro heuristických metod pro řešení, ve třetí se spouští samotný výpočet a v poslední je nápověda pro vytvoření disjunktivního grafu a okno o programu. Na obr. 6 můžeme vidět hlavní okno programu, kde je načtený příklad Fisher & Thompson 6x6 a zobrazeny operace, které je nutné vykonat pro vyrobení prvního výrobku.

Obr. 6 Hlavní okno programu 7.2 Nápověda Vzhledem ke složitosti disjunktivního grafu jsem se rozhodl vytvořit i poměrně velké okno s nápovědou pro jeho vytvoření. Každá operace (mimo uzlů 0 a *) může mít více než jednoho přímého předchůdce a více než jednoho přímého následníka. Aby bylo možno vytvořit graf, který by měl možnost pro každou operaci zadat libovolné množství sousedních uzlů,muselo by se zadání vytvořit pomocí dvourozměrného pole, které by mělo rozměr Nt × Nr . Už nejjednodušší příklad (F&F) by měl rozměr tohoto pole 36×36, příklad Lawrence 15 × 15 by měl rozměr dokonce 225×225, čímž by se zadání struktury grafu stalo naprosto nepřehledné. Z důvodu zachování přehlednosti jsem se rozhodl omezit zadání na možnost zadání maximálně dvou přímých předchůdců a dvou přímých následníků každého uzlu. Do kolonky výrobek se potom zadá číslo výrobku a do kolonky pořadí na výrobku se zadá pořadí operace na příslušném výrobku. Na obr. 7 je zobrazena část okna s nápovědou, jak se

Strana 44

7 Realizace programu

můžou zadávat jednotlivé operace.

Obr. 7 Jak vytvořit graf – část nápovědy 7.3 Nastavení parametrů algoritmů Pro rozmanitost výpočtu je nutné mít možnost jednoduché nastavení jednotlivých parametrů pro oba použité algoritmy. Proto jsem vytvořil jeden formulář, který pro plánování i pro rozvrhování zobrazuje pokaždé jinou nabídku podle toho, který z nich nastavuji. Jejich nastavení je na obr. 8 a 9. Pokud zadáváme nový problém, automaticky se definuje defaultní nastavení, které lze následně změnit. Parametry se načítají a ukládají do jednoho souboru se všemi ostatními daty nutnými pro výpočet. Pro ukládání hodnot zadání jsem použil formát souboru „.ini“, který je velice přehledný a snadno konfigurovatelný. Tento soubor je rozdělen na části určené pro algoritmy a pro číselné zadání jednotlivých položek.

Obr. 8 Nastavení genetického algoritmu

Obr. 9 Nastavení simulovaného žíhání


Strana 45

7.4 Výpočet Při spuštění výpočtu se zobrazí okno s informacemi o výpočtu, jak je to vidět na obr. 10. Vzhledem k tomu, že se u každé generace používá na jeden prvek heuristická metoda simulovaného žíhání, může být samotná délka výpočtu velice dlouhá, v řádu stovek vteřin. Proto jsem na příslušný formulář přidal možnost ukončení výpočtu po uplynutí zadaného časového intervalu nebo po projití určitého počtu přijatých prvků. Pokud je některá možnost vybrána, algoritmus si po zpracování každé populace zkontroluje, jestli už některá podmínak nebyla splněna, a pokud ano, tak přeruší výpočet a vrátí dosud nalezené nejlepší řešení. Po skončení výpočtu a zavření informačního formuláře se na hlavním formuláři (pokud byl výpočet úspěšně dokončen s nějakým přípustným řešením) zobrazí tlačítko s možností uložení řešení do souboru s koncovkou .txt a zpřístupní se se zobrazení výrobních dávek, zásob a vypočteného nejlepšího rozvrhu.

Obr. 10 Informační formulář o výpočtu 7.5 Součásti programu Program PlanovaniARozvrhovani.exe se skládá z několika unit, nejdůležitější z nich zde krátce pro přehlednost popíšu . DisjunktivniGraf.pas – v této unitě se nachází vše kolem grafu, jsou zde vytvořeny i zdroje z toho důvodu, že se s nimi v grafu velice často pracuje (hlavně s pořadím operací na jednotlivých zdrojích). Obsahuje i proceduru Sousedni_Rozvrh, která se využívá u algoritmu simulovaného žíhání pro nalezení náhodného sousedního řešení rozvrhu. GA_a_SZ – nejdůležitější a také nejobsáhlejší jednotka programu. V ní se řeší obě heuristické metody. Jejich parametry jsou zadané ve třídách TParametryGA a TParametrySZ. GA se řeší ve třídě TGenetickyAlg, SZ pro optimalizaci rozvrhu obstarává třída TPrvek v proceduře Optimalizuj_Rozvrh. InformForm - informační formulář pro výpis aktuálního stavu výpočtu, je na něm dán progressbar, aby se mohl zobrazovat stav výpočtu při delším trvání Pole – všechny druhy polí, od jednorozměrného až po trojrozměrné. Všechny pole jsou typu integer. To jsem si mohl dovolit, protože jsem u polí, kde se pracuje

Strana 46


s reálnými čísly, převedl jednotlivá reálná čísla na násobky těchto hodnot, se kterými jsem potom pracoval. Problem – jednotka zajišťující koperaci mezi algoritmy, načítání a ukládání hodnot, vytvoření grafů a obsahuje proceduru Vypocet, který zastřešuje optimalizaci výrobních dávek i rozvrhu UnitHlavni – obsahuje základní strukturu programu a hlavní formulář, obhospodařuje otevírání a ukládání hodnot a parametrů, uložení řešení a spuštění výpočtu 7.6 Spuštění výpočtu Jak bylo řečeno o několik řádků výše, po spuštění výpočtu obstarává jeho chod procedura Vypocet z jednotky Problem. Pokud je zadaná pouze jedna perioda, poté se řeší pouze rozvrhování a zpracování je trochu odlišné, většina operací ale probíhá stejně. Proto zde uvedu pouze zjednodušenou podobu pro zpracování prvku procedure TProblem.Vypocet; var pomCas : real; g : integer; begin JeVypocten := false; casVypoctu := GetTickCount; SestavHlGraf; GA = TGenetickyAlg.Create(PocetUzlu,PocetPeriod,PocetZdroju,DelkaPeriody, ParametryGA, ParametrySZ); //vytvořím si genetický algoritmus GA.Generuj_Poc_Populaci;

//vygeneruji si počáteční poulaci

PriradPoleGA;

//přiřadím si jednotlivým polím hodnoty

g := 0; while g < ParGA.PocGeneraci do //pokud je počet generací menší než begin zadaný if UkonceniPoCase then //pokud je zadané ukončení po čase, tak begin zkontroluji délku výpočtu pomCas := round((GetTickCount - casVypoctu)/1000); if round(pomCas) > FDelkaVypoctu then break; end; //jestli už jsem našel optimum, skončím if (makespan = OptimalniDelka) then break; ZpracujPrvky; GA.Vypocet; Inc(g); end;

//zpracuji prvky + sim. žíhání //následně aplikuji genetické operátory

casVypoctu := (GetTickCount - casVypoctu)/1000; JeVypocten := true; end;

7.7 Zpracování prvků a simulované žíhání Zpracování každého prvku a simulované žíhání má na starost procedura ZpracujPrvek * třídy TPrvek. Ta nejdříve upraví grafy, vypočítá hodnoty Y, X, I, následně určí hodnotu C t a pokud je splněna podmínka (28) tak se určí počáteční rozvrh a pokusí se jej optimalizovat.


Strana 47

V této části programu se aplikuje krok č. 4 z navrhovaného algoritmu. Zjednodušená forma této procedury je procedure TPrvek.ZpracujPrvek; var i, j : integer; begin Uprav_Grafy; //upravím si grafy prvku podle vygenerovaných hodnot Oprav_Y; //podle poptávky si upravím hodnoty Y Urci_X; //vypočítám hodoty X Urci_I; //vypočítám hodnoty I Vypocitej_C_Konj; //určím si C * if ProvedPresuny then //pokud se mi povede presunout prvky v konjunktivní begin //struktuře, vypočítám a optimalizuji rozvrh(pokud //je T = 1, má tato fce. vždy hodnotu true) for i := 0 to T - 2 do begin Vypocitej_Poc_Rozvrh(Graf[i]); //určím počáteční rozvrh. Pokud je //graf acyklický, vypočítám C max if Graf[i].JeAcyklicky then Vypocitej_C_Max(Graf[i]); if Graf[i].CMax > DelkaPeriody then begin Optimalizuj_Rozvrh(Graf[i]); //pokud platí tato podmínka, tak //zkusím optimalizovat rozvrh, pokud i //potom platí, tak přesunu produkci if ((Graf[i].CMax > DelkaPeriody) and (T > 1)) then PresunProdukci(Graf[i], 'dopredu'); end; end; for j := T – 1 downto 1 do //postupuji stejně jako v předchozím cyklu begin //jen v jiném pořadí period vypocitej_poc_rozvrh(graf[j]); if Graf[j].JeAcyklicky then Vypocitej_C_Max(Graf[j]); if (Graf[j].CMax > DelkaPeriody then begin Optimalizuj_Rozvrh(Graf[j]); if ((Graf[j].CMax > DelkaPeriody) and (T > 1)) then PresunProdukci(Graf[j], 'dozadu'); end; end; Vypocitej_fit; //vypočítám hodnotu fitness prvku end else //pokud se nepodařilo splnit podmínku (28), tak begin for i := 0 to T - 1 do begin //pro všechny periody určím nějaký rozvrh Vypocitej_Poc_Rozvrh(Graf[i]); //a vypočítám C max prvku if Graf[i].JeAcyklicky then Vypocitej_C_Max(Graf[i]); end; Vypocitej_fit; end; end;

Popsaná procedura se stará o zajištění splnění všech podmínek, úpravy grafu a výpočet základních hodnot polí. Optimalizaci rozvrhu zajišťuje také třída TPrvek v proceduře

Strana 48


Optimalizuj_Rozvrh. Při vytváření cyklu jsem se inspiroval v práci [18], kde byl podrobně popsán, a pozměnil jsem ho v závislosti na potřebách a požadavcích. Při tvorbě sousedního rozvrhu jsem použil relaci sousedství navrženou v kapitole 7.2. Z důvodu velice dlouhého výpočtu jsem jako ukončovací podmínku Tmin dal pevnou hodnotu, jelikož při zadání malé hodnoty by se neúměrně prodloužila doba výpočtu. Při přiblížení se této hodnotě se zvětšuje prohledávané okolí, ve většině případů se najde akceptovatelné nebo optimální řešení. Proměnná pr označuje procentuální pravděpodobnost, se kterou původní řešení přechází do nového rozvrhu. Hodnota loc_t je aktuální teplota, loc_k je počet cyklů, kolikrát se původní řešení překlopilo do nového. procedure TPrvek.Optimalizuj_Rozvrh(aGraf : TGraf); var loc_T, loc_x, loc_k, loc_j, pr : integer; loc_i, loc_n, pom_Cmax : integer; begin loc_T := T_max; loc_k := 1; //nastavím si počáteční podmínky loc_n := n_cyklu; while (loc_T > 400) do begin loc_k := 1; while (loc_k < loc_n) do begin pom_Cmax := pGraf.CMax; aGraf.Sousedni_Rozvrh; //nahodne urci nejaky jine reseni rozvrhu //z mnoziny sousedních reseni (viz. kap. 7.2) Vypocitej_C_Max(pGraf); if aGraf.CMax < pom_CMax then pr := 100 //pokud je nový rozvrh else //lepší než původní, tak je pr 100% //jinak se spočítá podle [14] pr := round(exp((aGraf.CMax- pom_CMax)/loc_T)); if random(100) < pr then begin inc(loc_k); if min_C = aGraf.CMax then aGraf.Zalohuj_Rozvrh; end else aGraf.PrejdiNaRozvrh; end; loc_T := round(alfa/100 * loc_T); loc_n := round(loc_n/100 * k_del_cyklu); end; end;

7.8 Programové řešení genetického algoritmu Genetický algoritmus se aplikuje, když už byly všechny prvky v populaci zpracovány. U selekce se podle zadaní provádí jedna z procedur Urci_Rodice (u ruletové selekce, rodiče se určí pomocí hodnoty fitness a pravděpodobnosti), Turnaj (každý z rodičů se vybere z náhodně určené množiny prvků) a nebo Nahodili_Rodice (náhodně se určí oba rodiče). procedure TGenetickyAlg.Vypocet; var loc_i, loc_j : integer; poc_PridPrvku, poc_Prvku : integer; begin

7 Realizace programu Zkopiruj_Nejlepsiho; poc_Prvku := 1;

Strana 49

//zkopíruji si nejlepší prvek z oldpop

while (poc_Prvku < velPop) do begin case paramsGA.Selekce of //prvně provedu selekci podle zvoleného ruletova : Urci_Rodice; //zadání turnajova : Turnaj; nahodna : Nahodili_Rodice; end; Mutace_Rodicu; Krizeni_Rodicu; Pridej_Rodice; end;

//provedu křížení //provedu mutaci //pridám nově vytvořené rodiče do newpop

for loc_i := 0 to VelPop - 1 do //zkopíruji si newpop do oldpop oldpop.FPrvky.Items[loc_i] := newpop.FPrvky.Items[loc_i]; Makespan := 0; for loc_i := 0 to T - 1 do Makespan := Makespan + oldpop.Nejlepsi_Prvek.Graf[loc_i].CMax; end;

Strana 50


Strana 51

8

VÝPOČETNÍ EXPERIMENTY

Výpočty na testovacích příkladech se prováděly na počítači s procesorem Intel Celeron 2,4 GHz, 256 MB RAM. Každý příklad byl vypočetný 15× a všechny výsledky byly uloženy do souborů pro konečné porovnání. Parametry algoritmů jsem volil s uvážením výsledků již řešených příkladů u mých předchůdců, např. [3], [14], [15]. U omezujících podmínek byl zvolen přístup zachovávající přípustnost z hlediska zásob s posuvem dopředu a dozadu. U většiny výpočtů jsem použil stejně nastavené parametry u heuristických stochastických algoritmů. Nastavení genetického algoritmu: • Počet generací: 50 • Velikost populace: 20 • Pravděpodobnost křížení: 60 % • Pravděpodobnost mutace: 0,3 % • Selekce: ruletová • Křížení: dvoubodové Nastavení simulovaného žíhání: Počáteční teplota: 1000 • Konečná teplota: 30 • Teplotní koeficient: 0,9 • Délka vnitřního cyklu: 20 • Koeficient délky cyklu: 1,22 •

8.1 Příklady zaměřené na hledání optimálního rozvrhu K testování byly použity vzorové příklady, u nichž již bylo nalezeno globální minimum. U každého příkladu je v tabulce uvedna nejnižší hodnota, průměrná hodnota a průměrný čas výpočtu. Z důvodu výpovědní hodnoty jsem do výsledných tabulek zařadil místo hodnoty fitnes hodnotu nejkratší vypočtené délky výroby. Nadpis každé úlohy je ve formátu název a za ním je N × K (počet výrobků × počet strojů). Pokud jsem u rozvrhování nechal projít výpočet s výše uvedenými hodnotami až do konce, tak bylo procházeno více než 75 000 řešení. U složitějších příkladů jsem z důvodu časové délky výpočtu zvolil ukončení výpočtu po projití určitého počtu kroků. I tak byly vypočtené hodnoty srovnatelné nebo lepší než u mých předchůdců, např. [14], [15]. 1. Fisher and Thompson 6 × 6 Optimum

Nejlepší řešení

Průměrná hodnota

55

55

55

Počet Nejkratší čas Nejdelší čas Průměrný čas opakování výpočtu [s] výpočtu [s] výpočtu [s] 15

0,063

1,000

0,342

U tohoto nejjednoduššího příkladu výpočtu nebyl s nalezením optimální hodnoty problém, u téměř 100% pokusů bylo řešení nalezeno výrazně dříve než za 1 s.

Strana 52

8 Výpočetní experimenty

2. Lawrence 10 × 5 Optimum


Průměrná hodnota

666

666

668


0,125

42,625

6,404

Zde nebylo optimální řešení nalezeno pouze ve dvou případech z 15 pokusů, v několika případech byl výpočet úspěšně ukončen už po méně než 1 s. 3. Lawrence 10 × 5 Optimum


Průměrná hodnota

597

597

601


4,875

42,484

35,153

Příklad je co se týká velikosti stejný jako př. 2, výpočet už optimum nenachází tak často, pouze 3×. Při řešení všech možných řešení byl čas výpočtu maximálně 40 s. Ve srovnání s výsledky v práci [15] byly výsledky lepší o 6%, pokud jsem dal ukončení po 5000 přijatých prvcích, byla doba výpočtu rychlejší o vteřinu a se stejnými výsledky. 4. Lawrence 15 × 5 Optimum


Průměrná hodnota

926

926

927


0,063

74,453

14,415

Ve 12 případech nalezeno optimum, pouze 3× bylo prozkoumáno všech více jak 75 000 možností a výpočet byl proveden až do konce, kdy trval přibližně 70 s. Jinak opět řešení za méně než 1 s. 5. Adams, Balas and Zawack 10 × 10 Optimum


Průměrná hodnota

1234

1250

1265


23,453

27,484

24,866

Zde byla patrná menší odchylka od optima, nejlepší řešení mělo odchylku pouze o 1%, ve srovnání s výsledky v [15] bylo řešení lepší o 2% (tam byly tyto hodnoty nalezeny pouze u zakázaného hledání). Zde jsem poprvé použil ukončení po přijatém počtu prvků, jehož hodnotu jsem zvolil 15 000. I proto byl výpočet velice rychlý, za srovnatelnou dobu bylo v [15] vyšetřena pouze 1/3 řešení.


Strana 53

6. Lawrence 20 × 5 Optimum


Průměrná hodnota

1222

1222

1222


0,109

1,000

0,579

Tento příklad byl překvapením, optimum bylo nalezeno vždy, a to maximálně do 1 s. Zlepšení v porovnání se simulovaným žíháním v práci [15], kde optimální hodnota u algoritmu simulovaného žíhání nebyla nalezena. 7. Lawrence 15 × 10 Optimum


Průměrná hodnota

1046

1109

1143


60,688

70,594

63,73

U příkladů s více než 100 operacemi jsem skoro vždy používal omezení ukončení výpočtu po prohledání daného počtu prvků (zvolená hodnota byla 15 000). Vypočtené hodnoty jsou lepší o 3% než v [15], mohou se srovnávat se zakázaným hledáním, nejúspěšnějším algoritmem u předchůdce. Opět se ukázalo, že za stejnou dobu je prověřeno trojnásobné množství řešení. 8. Lawrence 20 × 10 Optimum


Průměrná hodnota

1218

1228

1264


100,656

121,125

111,463

Zde už se projevila větší složitost, kdy i po omezení byl čas výpočtu přes 100 s, ale opět byl výpočet rychlejší a hlavně výsledky byly o 8% lepší než v [15]. Nejlepší nalezená hodnota se liší od optima o méně než 1 %. 9. Lawrence 15 × 15 Optimum


Průměrná hodnota

1268

1337

1362


165,453

178,75

171,270

Toto byl časově nejnáročnější z příkladů na optimalizaci rozvrhu a proto se muselo také použít ukončení po přijatém počtu prvků 15 000. Výsledky jsou ale o 3 % lepší než v [15]. Čas výpočtu je v podstatě srovnatelný, i když se prochází trojnásobné množství řešení. 8.2 Příklad zaměřený na integraci dávek a rozvrhu Pro integrované problémy s více periodami prakticky neexistují vzorové příklady, které bych zde mohl použít. Proto jsem experimenty rozdělil na dvě části, na část s příklady

Strana 54


zaměřenými na rozvrh a na část věnující se intagraci dávek a rozvrhu. Pro test jsem použil příklad Lassere, který je vlastně modifikací příkladu Fisher & Thompson 6 × 6 a skládá se ze tří period. 10. Laserre Zadání problému: 6 výrobků a 6 strojů, optimální hodnota doby výroby : 55 optimální hodnota nákladů: 0 seřizovací náklady: 0 skladovací náklady: 5 Přiřazení operací ke strojům a časy operací: viz následující tabulka Operace 1 Operace 2 Operace 3 Operace 4 Operace 5 Operace 6 Výrobek Stroj Čas Stroj Čas Stroj Čas Stroj Čas Stroj Čas Stroj Čas Job 1

3

1

1

3

2

6

4

7

6

3

5

6

Job 2

2

8

3

5

5

10

6

10

1

10

5

4

Job 3

3

5

4

4

6

8

1

9

2

1

5

7

Job 4

2

5

1

5

3

5

4

3

5

8

6

9

Job 5

3

9

2

3

5

5

6

4

1

3

4

1

Job 6

2

3

4

3

6

9

1

10

5

4

3

1

Optimum


Průměrná hodnota

165

165

165


54,031

70,891

60,872

Zde se předpokládala poněkud větší složitost problému z toho důvodu, že problém je složen ze 3 period, takže zde už dochází k přesunům výroby mezi jednotlivými periodami. Vypočtené řešení je ale optimální, je to z toho důvodu, že se v algoritmu nejdříve řeší úpravy prvků v generaci a přesuny a následně je u nejlepšího prvku optimalizován rozvrh. Jelikož nejnižší hodnotu výrobních nákladů má ten prvek, u kterého se ve všech periodách vyrábějí všechny prvky, tak použitá heuristická metoda nalezla rozvrh poměrně rychle a vždy, protože je použita na každou periodu zvlášť. Optimální hodnota nákladů je nulová z toho důvodu, že seřizovací náklady jsou také nulové a všechny vyráběné prvky jdou přímo na odbyt a ne do skladu. Doba výpočtu problému byla asi 60 s. Podmínky se nemusely omezovat, řešení bylo nalezeno už v první generaci. Vypočtené řešení tohoto problému je lepší něž v práci [14], kde optimální rozvrh nebyl nalezen.


Strana 55

8.3 Porovnání výsledků Pro srovnání nalezených řešení zde připojuji tabulku s mými výsledky a s výsledky mých předchůdců, u př. 1 – 9 je to porovnání s výsledky v [15], u př. 10 je to se [14]. Nejl. Optimum vypočtené řešení

Rozdíl od optima [%]

Rozdíl od předch. výsledků [%]

Číslo úlohy

Název problému

1.

Fisher & Thompson 6×6

55

55

0

0

2.

Lawrence 10 × 5

666

666

0

0

3.

Lawrence 10 × 5

597

597

0

–6

4.

Lawrence 15 × 5

926

926

0

0

5.

Adams, Balack 10 × 10

1234

1250

1

–2

6.

Lawrence 15 × 10

1046

1109

6

–3

7.

Lawrence 15 × 15

1268

1337

5

–3

8.

Lawrence 20 × 5

1222

1222

0

–1

9.

Lawrence 20 × 10

1218

1228

1

–8

10.

Lasserre

165

165

0

–8

Z tabulky je patrné zlepšení proti předchozím výpočtům, např. u úloh č. 3, 9 a 10 bylo snížení nejkratší vypočtené délky o 6 – 8 %. V žádné úloze nedošlo ke zhoršení výsledků.

Strana 56


Strana 57

9

ZÁVĚR

Tato práce byla věnována optimalizaci výrobních dávek a optimalizaci výrobního rozvrhu. U předchozích prací, např. v [3], [17], se řešila buď pouze otázka výrobních dávek, nebo jen optimalizace rozvrhu. Pokud se řešily oba problémy současně, např. v [14], [16], tak se jednalo o přepínání mezi těmito úlohami, tzn. buď probíhalo jen plánování na pevně daném rozvrhu, nebo šlo o rozvrhování u pevně daných výrobních dávek. Zde byl uveden návrh řešení, kdy jsou všechny prvky v generaci upraveny a optimalizovány a následně jsou vzájemně propojeny pomocí GA. Pokusil jsem se vytvořit nové řešení problému optimalizace výrobních dávek a problému optimalizace rozvrhu. Program na testovacích příkladech projevil schopnost řešit problémy a nalézt dostatečně kvalitní řešení blízké optimálnímu. Ve většině případů bylo pravidelně nalezeno optimum pro daný příklad, u příkladu č. 9 byla odchylka jen 5 % a u příkladu č. 7 byla nejmenší odchylka asi 6 %. Časová náročnost výpočtového programu byla v některých případech překvapením, kdy u složitějších problémů po omezení výchozích podmínek u simulovaného žíhání nebyla doba výpočtu větší než 170 s. To je vzhledem k rozsáhlosti zkoumaného prostoru poměrně krátká doba a výsledky jsou na dostatečně kvalitní úrovni. Největší časová náročnost je při optimalizaci rozvrhu, kde by možná bylo vhodné vyzkoušet implementaci některého jiného algoritmu na získání sousedního řešení, nebo modifikovat zde navrženou metodu. Také může být prospěšné upravit výpočet celkové doby výroby. Závěrem lze říci, že zlepšení proti předhozí implementaci bylo zřejmé, i když se objevily některé nedostatky tohoto řešení, které mohou být předmětem dalšího výzkumu.

Strana 58

9 Závěr

Strana 59

10

SEZNAM POUŽITÉ LITERATURY

[1] Kimms, A. A Genetic Algorithm for Multi-Level, Multi-Machine Lot Sizing and Scheduling. Computers & Operations Research, Vol. 26, 1999, pp. 829-848. [2] Dauzére-Péres, S. and Laserre, J. B. Integration of Lotsizing and Scheduling Decisions in a Job-Shop. European Journal of Operational Research Vol. 75, 1994, pp. 413-426 [3] Majer, P. Moderní metody rozvrhování výroby. Disertační práce. FSI VUT, Brno 2003 [4] Dvořák, J.: Koncept habilitační práce. [5] Drexl, A., Kimms, A. Lot Sizing and Scheduling – Survey and Extensions. European Journal of Operational Research, Kiel, Vol. 99, 1996, pp. 221-235. [6] Dvořák, J., Martinek, V. and Král, J. Optimalizace dynamických výrobních dávek při omezených zdrojích pomocí heuristických metod. In Sborník přednášek k 7. ročníku konference Inteligentní systémy pro praxi, Seč u Chrudimi, 2003, s.39-40 + 10 s. na CD ROM . [7] Dvořák, J., Martinek, V. and Král, J. Using Genetic Algorithms to Solve a General Dynamic Lot Sizing Problem. In Proceedings of the 8th International Conference on Soft Computing MENDEL 2002, Brno, Czech Republic, 2002, pp. 125-131. [8] Florian, M., J.K. Lenstra and A.H.G. Rinooy Kan: Deterministic Production Planning and Complexity. Management Science, Vol. 26, 1980, pp. 669-679. [9] ErlenKotter, D., Ford Whitman Harris and the Economic Order Quantity Model, Operations Research, Vol. 35, (1982), pp. 937-946. [10] 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. [11] Xie, J. and Dong, J. A Heuristic Genetic Algorithm to General Capacitated Lot-Sizing Problems, Computers & Mathematics with Applications, Vol. 44, 2002, pp. 263-276. [12] Majer, P. Reprezentace problému rozvrhování zakázkové výroby disjunktivním grafem. Proceedings of XXVI. Seminar ASR '2001 Instrument and Control, Ostrava, 2001, 6 s. [13] 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. [14] Novák, J. Integrace metod pro optimalizaci výrobních dávek a rozvrhů. Diplomová práce. ÚAI FSI VUT, Brno, 2004, 55 s. [15] Zachar, K. Řešení problému rozvrhování výroby, Diplomová práce, ÚAI FSI VUT, Brno 2003, 66 s. [16] Brázdil, L. Integrace metod rozvrhování a optimalizace výrobních dávek, Diplomová práce, ÚAI FSI VUT, Brno, 2003, 53 s. [17] Král, J. Optimalizace dynamických výrobních dávek při omezených zdrojích, Diplomová práce, ÚAI FSI VUT, Brno, 2002, 63 s. [18] Giffler, B.; Thompson, G. Algorithms for Solving Production Scheduling Problems. European Journal of Operational Research, Vol. 8, 1960, pp. 487-503.

VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ PROGRAMOVÝ SYSTÉM PRO PLÁNOVÁNÍ A ROZVRHOVÁNÍ VÝROBY PROGRAM SYSTEM FOR PRODUCTION PLANNING AND SCHEDULING

Recommend Documents