Publication result detail

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

ŠEDA, M.

Original Title

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

English Title

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

Type

Chapter in a book

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.

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.

Key words in English

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

Authors

ŠEDA, M.

Released

01.10.2005

Publisher

DAAAM International

Location

Wien (Austria)

ISBN

3-901509-43-7

Book

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

Edition

DAAAM International Scientific Book

ISBN

1726-9687

Periodical

DAAAM International Scientific Book

State

Republic of Austria

Pages from

579

Pages count

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"
}