A memetic algorithm for Permutation Flow Shop Problems

Author

Rahman, Humyun F. ; Sarker, Ruhul A. ; Essam, Daryl L.

Author_Institution

Sch. of Eng. & Inf. Technol., Univ. of New South Wales, Canberra, NSW, Australia

fYear

2013

fDate

20-23 June 2013

Firstpage

1618

Lastpage

1625

Abstract

The Permutation Flow Shop Scheduling Problem (PFSP) is a well-known combinatorial optimization problem. In this paper, a Genetic Algorithm (GA) based approach has been developed to solve PFSP, with the objective of minimizing the makespan for a set of jobs. Two new priority rules; such as Gap Filling (GF) technique and Job Shifting (JS), have been introduced to enhance the performance of the GA. The algorithm has been used to solve a set of standard benchmark problems and the results have been compared with state-of-the-art algorithms. The comparison demonstrates that the overall performance of the algorithm is quite satisfactory.

Keywords

combinatorial mathematics; flow shop scheduling; genetic algorithms; GA based approach; GF technique; JS; PFSP; combinatorial optimization problem; gap filling technique; genetic algorithm based approach; job makespan minimization; job shifting; memetic algorithm; permutation flow shop scheduling problem; priority rules; standard benchmark problems; Algorithm design and analysis; Filling; Genetic algorithms; Job shop scheduling; Schedules; Sociology; Statistics; Flow Shop Scheduling; Genetic Algorithm; Makespan; Memetic Algorithm;

fLanguage

English

Publisher

ieee

Conference_Titel

Evolutionary Computation (CEC), 2013 IEEE Congress on

Conference_Location

Cancun

Print_ISBN

978-1-4799-0453-2

Electronic_ISBN

978-1-4799-0452-5

Type

conf

DOI

10.1109/CEC.2013.6557755

Filename

6557755