Publication detail

Disjunctive Graph-based Representation of Job Shop Scheduling Problem

MAJER, P.

Czech title

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

English title

Disjunctive Graph-based Representation of Job Shop Scheduling Problem

Type

conference paper

Language

cs

Original abstract

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.

Czech abstract

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.

English abstract

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.

Keywords in English

disjunctive graph, job shop scheduling, heuristic methods

RIV year

2001

Released

26.04.2001

Publisher

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

Location

Ostrava

ISBN

80-7078-890-9

Book

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

Pages count

7

BIBTEX


@inproceedings{BUT6025,
  author="Petr {Majer},
  title="Reprezentace problému rozvrhování zakázkové výroby disjunktivním grafem",
  booktitle="Proceedings of the XXVI. Seminar ASR’2001 Instruments and Control",
  year="2001",
  month="April",
  publisher="Vysoká škola báňská - Technická univerzita Ostrava",
  address="Ostrava",
  isbn="80-7078-890-9"
}