Reprezentace problému rozvrhování zakázkové výroby disjunktivním grafem

Disjunctive Graph-based Representation of Job Shop Scheduling Problem

conference paper

cs

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.

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.

This work deals with a problem of job shop scheduling. It is a hard combinatorial problem and therefore real-world problems are usually solved by heuristic methods. Frequently used heuristic methods are simulated annealing, taboo search and genetic algorithms. When applying heuristic method, the choice of problem representation is important. In this paper two representations are described: the disjunctive graph-based representation and the preference list-based representation. These representations are compared for standard job shop benchmarks solved by the above-mentioned methods.

disjunctive graph, job shop scheduling, heuristic methods

2001

26.04.2001

Vysoká škola báňská - Technická univerzita Ostrava

Ostrava

80-7078-890-9

Proceedings of the XXVI. Seminar ASR’2001 Instruments and Control

7