Publication detail

Scheduling Flow Shops

ŠEDA, M.

Czech title

Rozvrhování proudové výroby

English title

Scheduling Flow Shops

Type

conference paper

Language

en

Original abstract

In this paper, two different approaches to permutation flow shop scheduling problem are investigated. The first one is based on a mixed integer programming model and is solved by an optimization package GAMS. As the problem belongs to NP-complete problems, this approach is limited to smaller instances, its reasonable bounds are indicated using benchmarks from OR-Library. For large instances, an approach using genetic algorithm is proposed including its appropriate parameter settings. Finally, a modification of the problem using uncertain processing times of jobs is presented.

Czech abstract

V příspěvku jsou zkoumány dva různé přístupy k řešení permutačního problému rozvrhování proudové výroby. První z nich je vychází z modelu smíšeného celočíselného programováním a je řešen v optimalizačním programu GAMS. Protože problém patří mezi NP-úplné, je tento přístup omezen na menší instance. Hranice řešitelnosti jsou indikovány pomocí testovacích úloh z OR-Library. Pro větší instance je navržen přístup využívající genetický algoritmus včetně vhodného nastavení jeho parametrů. Nakonec je ještě prezentována modifikace problému pro případ úloh s neurčitými časy provedení jejich operací.

English abstract

In this paper, two different approaches to permutation flow shop scheduling problem are investigated. The first one is based on a mixed integer programming model and is solved by an optimization package GAMS. As the problem belongs to NP-complete problems, this approach is limited to smaller instances, its reasonable bounds are indicated using benchmarks from OR-Library. For large instances, an approach using genetic algorithm is proposed including its appropriate parameter settings. Finally, a modification of the problem using uncertain processing times of jobs is presented.

Keywords in English

flow shop, mixed integer programming, heuristic, genetic algorithm

RIV year

2005

Released

29.08.2005

Publisher

VUT FEKT

Location

Brno

ISBN

80-214-2976-3

Book

Proceedings of the International Conference CEEPUS Summer School 2005 Intelligent Control Systems

Pages count

101

BIBTEX


@inproceedings{BUT15920,
  author="Miloš {Šeda},
  title="Scheduling Flow Shops",
  booktitle="Proceedings of the International Conference CEEPUS Summer School 2005 Intelligent Control Systems",
  year="2005",
  month="August",
  publisher="VUT FEKT",
  address="Brno",
  isbn="80-214-2976-3"
}