XXVI. ASR '2001 Seminar, Instruments and Control, Ostrava, April 26 - 27, 2001
Paper 39
Reprezentace problému rozvrhování zakázkové výroby disjunktivním grafem MAJER, Petr Ing.,
ÚAI FSI VUT, Technická 2, 61669 Brno,
[email protected]
Abstrakt: Práce se zabývá problémem rozvrhování zakázkové výroby (job shop scheduling). Problém rozvrhování je složitý kombinatorický problém, k jehož řešení se používají především heuristické metody, konkrétně simulované žíhání, tabu search a genetické algoritmy. Při použití heuristických metod je důležitá volba reprezentace dat. V tomto příspěvku je detailně popsána reprezentace dat pomocí disjunktivního grafu a její použití ve spojení s výše uvedenými metodami. Na základě naměřených hodnot na vzorových příkladech je porovnána reprezentace pomocí disjunktivního grafu s reprezentací pomocí preferenčního seznamu. Klíčová slova: rozvrhování zakázkové výroby, disjunktivní graf, heuristické metody, job shop scheduling
1 Úvod Jednou z nezbytných podmínek zvyšování efektivnosti výroby je využívání matematických modelů a metod pro podporu řízení, a to zvláště na operativní úrovni. Na této úrovni je důležitým problémem zejména tvorba výrobních rozvrhů. Problém rozvrhování je dán konečnou množinou výrobků, které je potřeba vyrobit, a omezeným počtem výrobních strojů, které jsou k dispozici. Výroba každého výrobku se skládá z operací a každé operaci je přidělen určitý stroj. Pořadí provádění operací u každého výrobku je dáno technologickým postupem a není možné jej měnit. Pokud pořadí strojů smí být pro každý výrobek různé, mluvíme o rozvrhování zakázkové výroby (job shop scheduling). Ve speciálním případě, kdy je pořadí strojů u všech výrobků stejné, mluvíme o rozvrhování proudové výroby (flow shop scheduling). Úkolem je najít optimální rozvrh, to jest optimální pořadí výrobků na jednotlivých strojích. Jako kriteria kvality rozvrhu je možné použít celkovou dobu trvání výroby, délku prostojů strojů, ztráty spojené s nesplněním prací v požadovaných termínech, stupeň rozpracovanosti apod. Obecně patří problémy rozvrhování mezi NP-složité problémy. To znamená, že klasickými exaktními algoritmy je možné řešit pouze úlohy malého rozsahu a rozsáhlejší úlohy musejí být řešeny pomocí heuristických metod. Často se používají stochastické heuristické metody založené na principech genetických algoritmů (genetic algorithms), simulovaného žíhání (simulated annealing) a zakázaného prohledávání (tabu search). Obecně jsou tyto metody popsány například ve [Kvasnička 1997, Reeves 1993] a na deterministický problém rozvrhování výroby jsou aplikovány např. ve [Krishna 1995, Nowicki 1996, Yamada 1995].
2 Rozvrhování zakázkové výroby Nyní se zaměříme na problém rozvrhování zakázkové výroby. V klasické obecné podobě byl tento problém popsán ve [Blazewicz 1996]. Máme dánu množinu prací (jobů) J = {J1 ,..., J n } a množinu strojů (machines) M = {M 1 ,..., M m } . Je potřeba vykonat všech n jobů. Každý job se skládá z určitého, obecně nestejného, počtu operací. Doby trvání operací u různých dvou -1-
jobů mohou být různě dlouhé a doba trvání některé operace může být i nulová. Pořadí operací u každého jobu je dáno technologickým postupem a nelze jej měnit. Množina všech operací všech jobů je O = {O1 ,..., Oo } . Doba trvání k-té operace je pk . Pro provedení každé operace je zapotřebí jednoznačně přiřazený stroj z množiny M. Na jednom stroji lze současně provádět nejvýše jednu operaci jednoho jobu a provádění operace nelze přerušit. Vykonání každého jobu tedy znamená provedení všech jeho operací v zadaném pořadí na daných strojích. Přiřazení jakýchkoliv proveditelných pořadí π operacím na všech strojích z M se nazývá rozvrh (schedule). Ukázka takového rozvrhu pro n = 3 joby a m = 3 stroje je na obrázku 1.
Obrázek 1 – Rozvrh pro pro n = 3 joby a m = 3 stroje Úkolem rozvrhování je optimalizovat rozvrh π tj. nalézt nejvhodnější pořadí úloh na daných strojích. Jako kriterium kvality rozvrhu se nejčastěji volí čas dokončení všech úloh (makespan). Označme symbolem rk nejdříve možný termín začátku operace k-té operace a ck termín dokončení k-té operace. Platí: ck ≥ rk + pk
(1)
Úkolem je potom minimalizovat největší z těchto hodnot: Minimalizovat C max (π ) = max{ck } .
(2)
1≤ k ≤o
Často je pro každý job zadán termín jejího dokončení Ti . V takovém případě je naším úkolem nalezení rozvrhu, který minimalizuje ztráty spojené s nedodržením termínů, které mohou být vyjádřeny například takto: n
Minimalizovat
∑ [z
i
i =1
max{0, c Last ( i ) − Ti }],
(3)
kde Last (i ) je funkce, která vrací index poslední operace v i-tém jobu a zi je koeficient ztráty spojené s opožděným dokončením i-tého jobu. V případě systému výroby JIT (just in time) nám vadí též případné předčasné dokončení jobů, které je například spojeno se ztrátami spojenými s nutností skladování předčasně dokončených výrobků: n
Minimalizovat
∑ [z i =1
i
max{0, c Last ( i ) − Ti } + si max{0, Ti − c Last ( i ) }],
-2-
(4)
kde si je koeficient ztráty spojené s předčasným dokončením i-tého jobu. Pro optimalizaci se používají heuristické metody ve spojitosti s vhodnou reprezentací dat.
3 Reprezentace problému rozvrhování Pod pojmem reprezentace dat rozumíme vytvoření určitého způsobu zápisu posloupnosti operací na strojích do určitého druhu seznamu, který nám umožní provádění výpočtů na počítačích a optimalizaci řešení pomocí heuristických metod. V průběhu posledních několika let bylo navrženo několik způsobů reprezentace problému rozvrhování zakázkové výroby [Cheng 1996, Šeda 1999]. Nejpoužívanější jsou reprezentace pomocí disjunktivního grafu a reprezentace pomocí preferenčního seznamu. Preferenční seznam je seznam, který se skládá z m řetězců. Každý řetězec přísluší jednomu stroji a obsahuje čísla operací, prováděná na tom stroji. Tyto řetězce nepopisují pořadí operací na strojích, ale jsou to pouze preference operací. Skutečný rozvrh je pak odvozen z preferenčního seznamu prostřednictvím simulace, která analyzuje stavy operací čekajících ve frontách na své stroje. Pokud je nutné rozhodnout o přednosti operací na některém stroji, vybere se nejdříve ta operace, která je v preferenčním seznamu první na řadě. Výhodnější než reprezentace preferenčním seznamem se však z hlediska použití heuristických metod jeví reprezentace pomocí disjunktivního grafu, proto zde bude popsána podrobněji. 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 jobů. Množina uzlů V obsahuje navíc dva speciální uzly, počáteční 0 a koncový uzel *. 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 jobů. 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 jobů a hrany vycházející z posledních operací jobů a směřující do koncového uzlu *. Disjunktivní hrany vyjadřují vzájemné pořadí operací, které musejí být provedeny na stejném stroji. Na začátku algoritmu jsou disjunktivní hrany neorientované. Množina disjunktivních hran tvoří m kompletních podgrafů, z nichž každý přísluší jednomu stroji, kde m je počet strojů. Příklad reprezentace problému se třemi joby a třemi stroji disjunktivním grafem představuje obrázek 2.
Obrázek 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. Celková doba zpracování všech úloh 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 u (π ) .
-3-
Máme-li vytvořen acyklický orientovaný graf, můžeme určit kritickou cestu. Než k tomu přistoupíme, můžeme ještě graf zjednodušit. Všimněme si, každý uzel grafu G (π ) , s výjimkou uzlů 0 a *, má nejvýše dva bezprostřední následníky a nejvýše dva bezprostřední předchůdce. Důležité je, ž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. Protože platí trojúhelníková nerovnost, můžeme z grafu vypustit ty disjunktivní hrany, které nespojují bezprostředně po sobě následující operace (viz obrázek 3).
Obrázek 3 – Zjednodušený orientovaný disjunktivní graf Kostra algoritmu nalezení kritické cesty vypadá takto: 1. Položíme r0 = 0 a přečíslujeme všechny uzly v grafu tak, že pokud existuje přímá cesta z uzlu i do uzlu j, pak i < j . Metoda pro přečíslování uzlů je popsána v [Klapka 1996]. 2. Uzly procházíme vzestupně podle indexů a počítáme nejdříve možné termíny začátků operací. Nejdříve možný termín začátku j-té operace je roven r j = max{rk + pk } , kde k∈P ( j )
P( j ) je množina uzlů, z nichž do uzlu j vstupují orientované hrany. 3. Délka kritické cesty C max (π ) je rovna termínu nejdříve možného začátku posledního uzlu r* . Termín nejpozději možného konce posledního uzlu je d* = r* , protože p* = 0 . 4. Nyní procházíme uzly sestupně podle indexů a počítáme nejpozději možné termíny ukončení operací. Nejpozději možný konec j-té operace je roven d j = min {d k − p k } , kde k∈N ( j )
N ( j ) je množina uzlů, do kterých z uzlu j vstupují orientované hrany. 5. Prodlevy na každém uzlu vypočítáme wk = d k − (rk + pk ) . Uzly, pro které je wk = 0 , leží na kritické cestě.
4 Metody řešení založené na kódování disjunktivním grafem Množina všech operací O může být přirozeně rozdělena do m podmnožin O k , 1 ≤ k ≤ m , kde každá z nich odpovídá množině operací prováděných na k-tém stroji. Pořadí operací na k-tém stroji může být definováno jako permutace π k , která se vytvoří pouze z operací příslušné množiny O k . Výrobní rozvrh π je tedy definován také jako množina permutací π = {π k | k ∈ {1,..., m}} operací na strojích 1,..., m , pro kterou je disjunktivní graf acyklický. Problém rozvrhování zakázkové výroby můžeme znovu formulovat jako hledání proveditelného výrobního rozvrhu π , který minimalizuje účelovou funkci. Obvykle se používá účelová funkce (2). Hodnota této funkce se rovná délce kritické cesty v grafu G (π ) . Víme, že kritická cesta u (π ) v grafu G (π ) je posloupnost kritických operací u (π ) = (u1 ,..., uv ) , kde v je počet operací na kritické cestě. Kritická cesta je rozdělena do podsekvencí nazývaných kritické bloky Bh . Kritické bloky jsou maximální podskupiny operací kritické cesty, které obsahují operace prováděné na stejném stroji. Kritická cesta u (π ) je tedy posloupnost kritických bloků u (π ) = ( Bh | h ∈ (1,..., g )) , kde g je počet kritických -4-
bloků na kritické cestě u (π ) . Definice kritických bloků je důležitá, protože pomocí ní se lze definovat operátory heuristických metod. Při nasazení heuristických metod v problémech rozvrhování musíme řešit následující otázky: 1. jak nalézt počáteční proveditelný rozvrh, 2. jak definovat vztah sousedství, 3. jak nalézt proveditelný rozvrh s co nejlepším ohodnocením. První a druhý úkol je společný pro mnoho heuristických metod. Třetí úkol závisí na algoritmu konkrétní heuristické metody. Pro počáteční rozvržení disjunktivních hran v grafu lze použít tento algoritmus: Deklarace : Nechť Q0 je množina všech již rozvržených operací. Nechť Q1 je množina všech rozvrhovaných operací. Nechť Q2 je množina všech nerozvržených operací. Množiny Q0 , Q1 a Q2 jsou disjunktní a jejich sjednocením získáme množinu všech operací O. Účelem algoritmu je nalezení počátečních rozvržení posloupností operací π = {π 1 ,...,π m } . Inicializace : Posloupnosti π 1 ,..., π m jsou na počátku algoritmu prázdné. Množina Q0 je prázdná. Množina Q1 obsahuje první operace všech jobů. Množina Q2 obsahuje všechny ostatní operace. Nejdříve možný termín zahájení je pro všechny operace rk = 0 , pro 1 ≤ k ≤ o . Dokud (Q1 ∪ Q2 ) není prázdné, opakuj { 1. V množině Q1 najdeme operaci O' , jejíž termín dokončení c ' je nejmenší c' = min{ck | Ok ∈ Q1 | ck = rk + pk } . Nechť M ' je stroj, na kterém je operace O' prováděna. Posloupnost z množiny π přiřazenou stroji M ' označme π ' . 2. Zavedeme množinu K (konfliktní množina). Nechť množina K obsahuje všechny operace z Q1 , které se provádějí na stroji M ' a jejichž nejdříve možný termín zahájení je menší než nejdříve možný termín dokončení operace O' . Konfliktní množina K = {Ok | stroj(Ok ) = M ' | rk < c' } . 3. Náhodně vybereme operaci O ' ' z množiny K a rozvrhneme ji. Rozvržení operace O ' ' v tomto případě znamená přiřazení jejího indexu na konec posloupnosti operací π ' . 4. Operaci O ' ' vypustíme z množiny Q1 a zařadíme ji do množiny Q0 . 5. Pro všechny operace z množin Q1 ∪ Q2 , které jsou prováděny na stroji M ' přepočítáme nejdříve možné termíny zahájení rk = c' ' . 6. Do množiny Q1 přemístíme z Q2 následující operaci v rámci jobu právě rozvržené operace O ' ' . } Sousedství lze definovat jako množinu rozvrhů, které lze získat aplikováním operátoru přechodu do jiného rozvrhu. Bylo popsáno mnoho způsobů [Blazewicz 1996], jak měnit orientace disjunktivních hran v grafu, aby se co nejefektivněji prohledal prostor řešení. Pro metody, kde se v každém kroku prohledává celé sousedství (metoda lokálního hledání, tabu search), je výhodné použití sousedství S1 : vzájemná výměna blízko hranice bloků na jediné kritické cestě [Nowicki 1996]. Uvažujeme jedinou libovolně zvolenou kritickou cestu -5-
u (π ) v grafu G (π ) , která se skládá z kritických bloků B1 ,..., Bg . Sousední rozvrhy získáme, pokud vyměníme první dvě (a poslední dvě) operace v každém bloku B2 ,..., Bg −1 a to v každém bloku, který se skládá nejméně ze dvou operací. V prvním bloku vyměníme poslední dvě operace a analogicky v posledním bloku vyměníme pouze první dvě. Pro metody, kde se v každém kroku neprohledává celé sousedství aktuálního řešení, je výhodné sousedství definovat šířeji než u předchozích metod. Důsledkem toho je důkladnější prohledání prostoru řešení. Pro metodu simulované žíhání a mutaci u genetického algoritmu se osvědčil způsob volby sousedství S 2 : posun náhodného kritického uzlu na kritické cestě na úplný začátek nebo konec v kritickém bloku [Blazewicz 1996]. Pro takto definované operátory přechodu do jiného rozvrhu S1 , S 2 bylo dokázáno, že pokud výchozí graf je acyklický, potom také každý vzniklý graf je acyklický, tedy jemu odpovídající rozvrh je proveditelný. Při použití heuristických metod (simulovaného žíhání, zakázaného prohledávání a genetických algoritmů) je řešením, které v tomto problému optimalizujeme (u GA chromozómem) samotný disjunktivní graf. Sousedství aktuálního řešení může být definováno jedním ze způsobů uvedených výše a účelovou funkcí (u GA fitness) je například podle (2) délka kritické cesty v grafu. Vlastní principy použitelných heuristických metod jsou shodné s metodami, které se používají i pro jiné kombinatorické problémy a jsou popsány např. v [Reeves 1993].
5 Výsledky experimentů Na základě počítačového programu bylo provedeno srovnání reprezentací pomocí disjunktivního grafu (DG) a preferenčního seznamu (PS). Testy byly provedeny na vzorových příkladech [Beasley 1996] se známou minimální délkou rozvrhu. V tabulce jsou zaznamenány průměrné a nejlepší dosažené hodnoty účelové funkce (2) z 10-ti spuštění algoritmů při použití optimalizačních metod: SA - simulované žíhání, TS - tabu search, GA - genetický algoritmus. Tabulka 1: Srovnání kódování disjunktivním grafem (DG) a preferenčním seznamem (PS). příklad metoda kódování nejlepší Průměr Fischer a Thomson 6x6 SA PS 76 89 soubor: ft06.prb TS PS 59 59 rozsah: 6 jobů, 6 strojů SA DG 55 55 optimální hodnota: 55 TS DG 55 55 doba optimalizace: 60s GA DG 55 56 Lawrence 10x5 SA PS 919 967 soubor: la03.prb TS PS 769 796 rozsah: 10 jobů 5 strojů SA DG 630 645 optimální hodnota: 597 TS DG 597 607 doba optimalizace: 120s GA DG 642 646 Adams, Balas a Zawack 10x10 SA PS 1930 2049 soubor: abz5.prb TS PS 1787 1827 rozsah: 10 jobů 10 strojů SA DG 1267 1275 optimální hodnota: 1234 TS DG 1247 1268 doba optimalizace: 300s GA DG 1385 1420
-6-
U heuristických metod byly použity následující specifikace parametrů: • SA: počáteční teplota = 10000, součinitel snižování teploty = 0.9, způsob volby sousedství: S 2 . • TS: délka zakázaného seznamu = 7, způsob volby sousedství: S1 , strategie prohledávání sousedství: výběr nejlepšího řešení z celého sousedství. • GA: velikost populace = 50, způsob selekce: binární turnajová selekce, způsob křížení: více-krokové křížení [Yamada 1995]. Z porovnání účinnosti způsobů kódování mezi disjunktivním grafem a preferenčním seznamem je patrné, že metody používající kódování disjunktivním grafem jsou ve všech případech účinnější. Metody založené na kódování preferenčním seznamem jsou sice schopny pro svou jednoduchost za stejnou dobu vykonat řádově více svých kroků, ale nejsou schopny dosáhnout optima i u poměrně jednoduchých příkladů. I přes svou časovou náročnost lze metody kódované disjunktivním grafem upřednostnit před metodami používajícími kódování preferenčním seznamem. Vzhledem k současnému překotnému vývoji výpočetních systémů lze metody založené na kódování disjunktivním grafem doporučit i pro řešení rozsáhlejších problémů rozvrhování zakázkové výroby.
6 Závěr Tento příspěvek se zaměřuje na řešení problému rozvrhování zakázkové výroby (job shop scheduling) pomocí moderních heuristických metod: simulovaného žíhání, zakázaného prohledávání a genetického algoritmu. Detailně je zde popsán problém rozvrhování zakázkové výroby a reprezentace jeho dat disjunktivním grafem. Jsou zde též popsány související algoritmy potřebné pro implementaci problému na počítači (algoritmus nalezení kritické cesty, algoritmus vytvoření počátečního proveditelného rozvrhu). Z porovnání metod používajících kódování disjunktivním grafem a jinými klasickými způsoby (např. preferenčním seznamem) vyplývá, že jasně výkonnější jsou metody používající kódování disjunktivním grafem. Tato práce je také východiskem pro naši budoucí práci, která se zaměří na studium neurčitostí, které se často vyskytují v praktických aplikacích problému rozvrhování zakázkové výroby. Jsou to neurčitosti v délkách trvání operací a neurčitosti v termínech dokončení jobů. Tyto neurčitosti lze modelovat pomocí teorie fuzzy množin. Pro implementování neurčitých veličin do disjunktivního grafu bude zřejmě nutné použít fuzzifikovanou metodu hledání kritické cesty a konstruovat vhodné účelové funkce pro aplikaci heuristických metod. Poděkování. Problém je řešen v rámci vědecko-výzkumného záměru CEZ: J22/98: 261100009 Netradiční metody studia komplexních a neurčitých systémů.
7 Literatura BEASLEY, J. E. OR – library. Technical report, The Management School Imperial College, London, 1996. http://www.mscmga.ms.ic.ac.uk/pub/jobshop.txt . BLAZEWICZ, J. et al. Scheduling Computer and Manufacturing Processes. Springer-Verlag, Berlin, 1996. 491 p. CHENG, R., GEN M. & TSUJIMURA, Y. A Tutorial Survey of Job-Shop Scheduling Problems Using Genetic Algorithms - I. Reprezentation. Computers ind. Engng Vol.30, No 4, pp. 983-997, 1996. KLAPKA, J., DVOŘÁK, J. & POPELA, P. Metody operačního výzkumu. VUT Brno, 1996. KRISHNA, K., GANESHAN, K. & JANAKI R. D. Distributed Simulated Annealing Algorithms for Job Shop Scheduling. IEEE Transactions on Systems, Man, and Cybernetics, Vol. 25. No. 7, 1995. pp. 1102-1109. KVASNIČKA, V. a kol. Úvod do teórie neuronových sietí. Bratislava, IRIS 1997. -7-
NOWICKI, E. & SMUTNICKI, C. A Fast Taboo Search Algorithm for the Job Shop Problem. Management Science, Vol. 42, No. 6, 1996. pp. 797-813. REEVES, C.R. (ed.). Modern Heuristic Techniques for Combinatorial Problems. Blackwell Scientific Publication, Oxford, 1993. ŠEDA, M., DVOŘÁK, J. & BURDA, J.: Scheduling Job Shops Using Genetic Algorithms and Local Search Framework, In Proceedings of the 6th International Conference on Soft Computing MENDEL '1999, Brno, Czech Republic, 1999, pp. 131-138. YAMADA, T. & NAKANO, R. 1995. A Genetic Algorithm with Multi-Step Crossover for Job Shop Scheduling Problems. In: Proceedings of the International Conference GALESIA '95, Sheffield, pp. 146-151.
-8-
