Publication detail
Mixed Integer Programming vs. Genetic Algorithm Approach to Scheduling Permutation Flow Shop
ŠEDA, M.
Czech title
Smíšené celočíselné programování vs. genetický algoritmus při rozvrhování proudové výroby
English title
Mixed Integer Programming vs. Genetic Algorithm Approach to Scheduling Permutation Flow Shop
Type
book chapter
Language
en
Original abstract
Flow shop scheduling problems represent scheduling a set of jobs (composed of tasks) in shops with a product machine layout. Thus, the jobs have the same manufacturing order. A permutation flow shop scheduling problem (PFSSP) is a special version of the problem where each machine processes the jobs in the same order. In this paper, two different approaches to PFSSP with makespan objective are investigated. First a mixed integer programming model is formulated and it is used for solving the problem by an optimisation package GAMS. Since 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. Computational results show a good performance of genetic algorithm. For suitable parameter settings presented in the paper, this approach is able to find the optimal solution almost in all cases or at least a solution very close to optimum when the test is executed several times.
Czech abstract
Problémy rozvrhování proudové výroby představují rozvrhování výrobních prací složených z dílčích úkolů (operací) v prostředí sériové výroby. To znamená, že práce musí procházet přes stejnou posloupnost strojů. Permutační problém rozvrhování proudové výroby je speciální verzí problému, kdy na každý stroj vstupují jednotlivé práce se svými operacemi na nich prováděných ve stejném pořadí. V příspěvku jsou zkoumány dva různé přístupy pro problém s účelovou funkcí danou dobou provedení všech operací. Nejdříve je zformulován model smíšeného celočíselného programování, který je pak použit pro řešení problému 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ů. Výsledky výpočtů ukazují, že pro nastavení parametrů uvedené v příspěvku je možné najít optimální řešení nebo alespoň řešení optimálnímu blízké téměř ve všech případech, je-li stochastický algoritmus spuštěn několikrát.
English abstract
Flow shop scheduling problems represent scheduling a set of jobs (composed of tasks) in shops with a product machine layout. Thus, the jobs have the same manufacturing order. A permutation flow shop scheduling problem (PFSSP) is a special version of the problem where each machine processes the jobs in the same order. In this paper, two different approaches to PFSSP with makespan objective are investigated. First a mixed integer programming model is formulated and it is used for solving the problem by an optimisation package GAMS. Since 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. Computational results show a good performance of genetic algorithm. For suitable parameter settings presented in the paper, this approach is able to find the optimal solution almost in all cases or at least a solution very close to optimum when the test is executed several times.
Keywords in English
permutation flow shop, integer programming, NP-complete problems, stochastic heuristics, genetic algorithm
RIV year
2005
Released
01.10.2005
Publisher
DAAAM International
Location
Wien (Austria)
ISBN
3-901509-43-7
ISSN
1726-9687
Book
Katalinic, B. (ed.): DAAAM International Scientific Book 2005
Journal
DAAAM International Scientific Book
Pages count
12
BIBTEX
@inbook{BUT55413,
author="Miloš {Šeda},
title="Mixed Integer Programming vs. Genetic Algorithm Approach to Scheduling Permutation Flow Shop",
journal="DAAAM International Scientific Book",
booktitle="Katalinic, B. (ed.): DAAAM International Scientific Book 2005",
year="2005",
month="October",
publisher="DAAAM International",
address="Wien (Austria)",
isbn="3-901509-43-7",
issn="1726-9687"
}