Rozvrhování zakázkové výroby


Dvořák, Jiří1, Šeda, Miloš2 & Vláčil, Tomáš3

1 RNDr., CSc., Ústav automatizace a informatiky, VUT FS v Brně, Technická 2, Brno, 616 69  jdvorak@kinf.fme.vutbr.cz

2 RNDr., Ing.,  mseda@kinf.fme.vutbr.cz

3 diplomant oboru Matematické inženýrství,  vlacil@kinf.fme.vutbr.cz

1. Abstrakt

This paper focuses on manufacturing scheduling, particularly job-shop scheduling, and proposes a new approach which extends standard mathematical formulation using transfer batches in production process. The proposed modification of mathematical model does not change the size of model and it makes possible to determine starting times for transfer batches processing from a solution of the modified model. This modification can be easily transformed into a disjunctive graph-based representation and therefore the given problem can be solved by any heuristic method based on this representation.

2. Úvod

Jednou z nezbytných podmínek pro 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í (scheduling) 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. Řešení tohoto problému spočívá v nalezení nejlepších pořadí prací na zadaných strojích (sekvenční problém). V jednodušším případě jsou stroje uspořádány sériově a všechny práce přes ně procházejí ve stejném pořadí (flow shop scheduling). Složitější případ představuje tzv. job shop scheduling (JSS), kde pořadí prací na jednotlivých strojích mohou být obecně různá. Při řešení mohou být sledovány různé cíle, jako např. minimalizace celkové doby zpracování, minimalizace ztrát spojených s nesplněním prací v požadovaných termínech, minimalizace prostojů, minimalizace rozpracované výroby apod.

V tomto příspěvku se zaměřujeme na job shop scheduling (to bývá překládáno jako rozvrhování zakázkové výroby), přičemž jako kritérium uvažujeme celkovou dobu zpracování (makespan). V klasické podobě [Blazewicz 1996] lze tento problém popsat takto: Je dáno m strojů a n prací. Každá práce se skládá z posloupnosti operací, přičemž každé operaci je jednoznačně přiřazen určitý stroj (na rozdíl od problému typu flow shop odpovídá každé práci obecně jiná posloupnost strojů). V každém okamžiku se na každém stroji může provádět nejvýše jedna operace a operace jsou nepřerušitelné. V praxi je možno se setkat s řadou modifikací klasického problému JSS (různé výrobní způsoby, volitelnost strojů, omezená kapacita meziskladů, omezené zdroje, neurčitost informací). Tento příspěvek se zabývá souběžným způsobem výroby, při němž se každá práce předává na následující operaci ne po výrobních dávkách, ale po dávkách dopravních.

V následující kapitole se nejprve zabýváme klasickým problémem JSS a metodami jeho řešení. Vycházíme přitom z formulace problému JSS jako úlohy celočíselného programování [Shapiro 1993] a popisujeme reprezentaci této úlohy ve formě disjunktivního grafu. Další kapitola je pak věnována problematice rozvrhování při souběžném výrobním způsobu. Je zde navržena jednoduchá modifikace celočíselného modelu, která nezvyšuje jeho rozsah, a je uveden postup, pomocí něhož lze z řešení modifikovaného modelu odvodit rozvrh zohledňující dopravní dávky. Dále je popsána konstrukce disjunktivního grafu pro modifikovanou úlohu.

3. Klasický problém JSS a přístupy k jeho řešení

Zaveďme následující označení:
n
počet prací (jobů, výrobků);

počet operací v práci i; operace mají indexy , kde
;
N
celkový počet operací;
m
počet strojů;

množina operací přiřazených stroji k;

doba provádění operace j na výrobní dávce příslušného výrobku;

termín zahájení operace j;
T
horní mez celkové doby trvání všech prací;
Cmax
celková doba trvání všech prací (čas dokončení poslední práce);
proměnná popisující precedenční vztah mezi operacemi ;

Problém optimalizace výrobního rozvrhu pak můžeme matematicky formulovat takto:

(1)

za podmínek

,

(2)

,

(3)

;

;

,

(4)

,

(5)

,

(6)

;

;

, ,

.

(7)

Problém JSS je obecně NP-těžký, což znamená, že klasické metody (celočíselné programování, metoda větví a mezí) jsou použitelné pouze pro modely malého rozsahu Pro řešení lze např. využít systém GAMS ([Brooke 1992], [Charamza 1993]), využívající metodu větví a mezí. Větší úlohy je nutné řešit heuristickými metodami, mezi nimiž se v posledních letech prosazují zejména tyto metody: simulované žíhání [Yamada 1994], [Krishna 1995], tabu search [Nowicki 1996] a genetické algoritmy [Cheng 1996], [Yamada 1995]. Přehled aplikací a srovnání těchto a dalších metod je uveden v práci [Vaessens 1996]. Jako nejlepší je zde vyhodnocena metoda založená na tabu search, kterou navrhli Nowicki a Smutnicki.

Důležitou roli při použití heuristických metod hraje reprezentace problému a jeho řešení. Popis používaných reprezentací je možno najít v práci [Cheng 1996] (tato práce je sice věnována genetickým algoritmům, ale uvedené reprezentace jsou použitelné i v dalších metodách). Velmi často je používána reprezentace pomocí disjunktivního grafu, která je také využita v již zmíněné práci [Nowicki 1996].

Disjunktivní graf je definován takto:

,

kde
V Je množina uzlů, reprezentujících operace všech prací a obsahující navíc dva speciální uzly, počáteční uzel 0 a koncový uzel N+1. Tyto speciální uzly jsou ohodnoceny nulami a ostatní uzly jsou ohodnodnoceny dobami trvání odpovídajících operací.
C je množina orientovaných konjunktivních hran. Tyto hrany zachycují uspořádání operací v rámci jednotlivých prací. Dále jsou zde hrany vedoucí z počátečního uzlu 0 do uzlů příslušných prvým operacím jobů a hrany směřující z posledních operací jobů do koncového uzlu (pro každý job tedy uzel 0 představuje fiktivní počáteční operaci a uzel N+1 fiktivní koncovou operaci).
D je množina neorientovaných disjunktivních hran reprezentujících dvojice operací, které musejí být prováděny na témže stroji.

Stanovit výrobní rozvrh znamená určit pořadí operací, které musejí být prováděny na stejném stroji. To může být učiněno změnou neorientovaných disjunktivních hran na orientované. Množina S orientovaných disjunktivních hran se nazývá selekce. Selekce S určuje přípustný rozvrh tehdy a pouze tehdy, když výsledný orientovaný graf je acyklický. V takovém případě se S nazývá úplnou selekcí. Celková doba zpracování všech prací (makespan) je dána délkou nejdelší cesty z počátečního do koncového uzlu v orientovaném grafu , kde S je úplná selekce. Tato cesta se nazývá kritickou cestou a skládá se z kritických operací. Maximální posloupnost navazujících kritických operací prováděných na témže stroji se nazývá kritický blok.

V heuristických metodách založených na lokálním hledání se pracuje s tzv. sousedstvím aktuálního řešení, což je množina řešení, dosažitelných z aktuálního řešení aplikací určitých operátorů na toto řešení. V případě reprezentace pomocí disjunktivního grafu se sousedství aktuálního řešení definuje záměnami operací v rámci kritického bloku. Úspěšnost metody [Nowicki 1996] je založena mimo jiné na tom, že sousedství se omezuje pouze na řešení, získaná záměnami sousedících operací, nacházejících se na hranicích kritických bloků.

4. Zohlednění dopravních dávek

Při souběžném způsobu výroby se každá práce předává na následující operaci ne po výrobních dávkách, ale po dávkách dopravních. To znamená, že když je stroj přiřazený j-té operaci volný, pak se nečeká na dokončení celé výrobní dávky na předcházejícím pracovišti, ale tato operace se provede vždy hned po dokončení a předání dopravní dávky z předchozí operace. Dopravní dávky můžeme v matematickém modelu zohlednit následovně. Zaveďme následující symboly:

počet dopravních dávek pro i-tou práci

počet dopravních dávek při j-té operaci;

platí pro ;

termín zahájení j-té operace na r-té dopravní dávce;

doba zpracování dopravní dávky při j-té operaci; ;

Příslušný matematický model pak vypadá takto:

(8)

za podmínek

(9)

,

;

;

(10)

,

;

;

(11)

;

(12)

(13)

(14)

;

;

, ,

;

.

(15)

Termíny zahájení operací na dopravních dávkách je však možno odvodit z řešení méně rozsáhlého modelu, který vznikne z modelu (1) - (7) tak, že omezení (3) se nahradí omezením

,

(16)

kde

.

Tento model odpovídá případu, kdy se sice uvažují dopravní dávky, ale současně se požaduje, aby celá výrobní dávka byla zpracována bez přerušení. Lze snadno dokázat, že optimální hodnota účelové funkce takto upraveného modelu je rovna optimální hodnotě účelové funkce modelu (8) - (15), a že pro optimální řešení těchto modelů platí

Řešení modelu (8) - (15) může být tedy odvozeno z řešení upraveného modelu (1) -(7) pomocí následujícího algoritmu, kde a b(j) označuje operaci, která na témže stroji bezprostředně předchází operaci j:

for  to n do
  begin
    ; ;
    for  to  do
      ;
    for  to  do
      begin
        ;
        for  to  do
          ;
      end;
  end;

Model (1) - (7), v němž omezení (3) je nahrazeno omezením (16), je možno rovněž řešit heuristickými metodami využívajícími reprezentaci pomocí disjunktivního grafu. Disjunktivní graf je však v tomto případě nutno upravit tak, že místo ohodnocení uzlů se provede následující ohodnocení hran:

Tato úprava nemá vliv na podstatu metod, které jsou na použití disjunktivního grafu založeny.

5. Závěr

Příspěvek se zabývá problematikou rozvrhování výroby při souběžném výrobním způsobu, při němž se práce předávají mezi operacemi v dopravních dávkách. Je zde navržena jednoduchá modifikace klasického modelu problému JSS, jež umožňuje použít k řešení jakoukoli metodu opírající se o reprezentaci pomocí disjunktivního grafu (jako nejvhodnější se jeví metoda, kterou navrhli Nowicki a Smutnicki a která je založena na tabu search). Ze získaných výsledků lze snadno odvodit termíny zahájení operací na jednotlivých dopravních dávkách pomocí algoritmu popsaného v předchozí kapitole.

6. Literatura

BLAZEWICZ, J., ECKER, K. H., PESCH, E, SCHMIDT, G. & WEGLARZ, J. 1996. Scheduling Computer and Manufacturing Processes. Berlin : Springer-Verlag, 1996, 491 pp.

BROOKE, A., KENDRICK, D. & MEERAUS, A. 1992. GAMS, Release 2.25. A User's Guide. Massachussetts (USA) : Boyd & Fraser Publishing Company, 1992.

CHARAMZA, P., POPELA, P. et al. 1993. Modelovací systém GAMS. Praha :MFF UK Praha, 1993, 130 s.

CHENG, R., GEN, M. & TSUJIMURA, Y. 1996. A Tutorial Survey of Job-Shop Scheduling Problems Using Genetic Algorithms - I. Representation. Computers ind. Engng. Vol.30, No.4, 1996, pp. 983-997.

KRISHNA K., GANESHAN K. & JANAKI R. D. 1995. Distributed Simulated Annealing Algorithms for Job Shop Scheduling. IEEE Transactions on Systems, Man, and Cybernetics, Vol. 25., No.7, 1995, pp. 1102-1109.

NOWICKI, E. & SMUTNICKI, C. 1996. A Fast Taboo Search Algorithm for the Job Shop Problem. Management Science, 1996, Vol.42, No.6, pp.797-813.

SHAPIRO, J. F. 1993. Mathematical Programming Models and Methods for Production Planning and Scheduling. In Graves, S. C., Rinnooy Kan, A. H. G., Zipkin, P. M. (eds.) Logistics of Production and Inventory. North-Holland, 1993.

VAESSENS, R. J. M., AARTS, E. H. L. & LENSTRA, J. K. 1996. Job Shop Scheduling by Local Search. INFORMS Journal on Computing, 8, 1996, pp.302-317.

YAMADA, T. & NAKANO, R. 1995. A Genetic Algorithm with Multi-Step Crossover for Job Shop Scheduling Problems. In Proc. of the 1st IEE/IEEE Int. Conf. on Genetic Algorithms in Engineering Systems: Innovations and Applications GALESIA '95. Sheffield, England, 1995, pp. 146-151.

YAMADA, T., ROSEN, B. E. & NAKANO, R. 1994. A Simulated Annealing Approach to Job Shop Scheduling Using Critical Block Transition Operators. In Proceedings of the IEEE International Conference on Neural Networks. Orlando, Florida, 1994, pp. 4687 - 4692.