Publication detail

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

ŠEDA, M.

English title

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

Type

Chapter in a book

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.

Released

2005-10-01

Publisher

DAAAM International

Location

Wien (Austria)

ISBN

3-901509-43-7

ISSN

1726-9687

Book

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

Pages from–to

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