Detail publikace

Mixed Integer Programming vs. Genetic Algorithm Approach to Scheduling Permutation Flow Shop

ŠEDA, M.

Originální název

Mixed Integer Programming vs. Genetic Algorithm Approach to Scheduling Permutation Flow Shop

Typ

kapitola v knize

Jazyk

angličtina

Originální abstrakt

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.

Klíčová slova v angličtině

permutation flow shop, integer programming, NP-complete problems, stochastic heuristics, genetic algorithm

Autoři

ŠEDA, M.

Rok RIV

2005

Vydáno

1. 10. 2005

Nakladatel

DAAAM International

Místo

Wien (Austria)

ISBN

3-901509-43-7

Kniha

Katalinic, B. (ed.): DAAAM International Scientific Book 2005

Edice

DAAAM International Scientific Book

ISSN

1726-9687

Periodikum

DAAAM International Scientific Book

Stát

Rakouská republika

Strany od

579

Strany do

590

Strany počet

12

BibTex

@inbook{BUT55413,
  author="Miloš {Šeda}",
  title="Mixed Integer Programming vs. Genetic Algorithm Approach to Scheduling Permutation Flow Shop",
  booktitle="Katalinic, B. (ed.): DAAAM International Scientific Book 2005",
  year="2005",
  publisher="DAAAM International",
  address="Wien (Austria)",
  series="DAAAM International Scientific Book",
  pages="12",
  isbn="3-901509-43-7"
}