Using Genetic Algorithm in the Multiprocessor Flow Shop to Minimize the Makespan
- 1 October 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 2 (21611890) , 1228-1233
Abstract
In this paper, we consider the k-stage multiprocessor flow shop scheduling problem. Our study aims to provide a good approximate solution to this specific problem with the makespan minimization (Cmax) as the objective function. Considering, the success of the genetic algorithms developed for scheduling problems, we apply this metaheuristic to tackle with this problem. We develop a genetic algorithm with a new crossover operator which is a combination between the SJOX crossover operator proposed by Ruiz and Maroto (2006) and the NXO crossover operator proposed by Oguz and Ercan (2005). The design of our genetic algorithm is different compared to the classical structure of the genetic algorithm especially in the encoding of solutions. For the calibration of our metaheuristic's parameters, we conduct several experimental designs. Our algorithm is tested with benchmark problems presented. The results show that the proposed genetic algorithm is an efficient approach for solving the multiprocessor flow shop problemKeywords
This publication has 10 references indexed in Scilit:
- A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibilityEuropean Journal of Operational Research, 2006
- A Genetic Algorithm for Hybrid Flow-shop Scheduling with Multiprocessor TasksJournal of Scheduling, 2005
- A new approach to solve hybrid flow shop scheduling problems by artificial immune systemFuture Generation Computer Systems, 2004
- Solving hybrid flow shop problem using energetic reasoning and global operationsOmega, 2001
- Sequencing three-stage flexible flowshops with identical machines to minimize makespanIIE Transactions, 2001
- Hybrid flow shop scheduling: A surveyComputers & Industrial Engineering, 1999
- Heuristic algorithms for the two-stage hybrid flowshop problemOperations Research Letters, 1997
- Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hardEuropean Journal of Operational Research, 1996
- Two-Stage, Hybrid Flowshop Scheduling ProblemJournal of the Operational Research Society, 1988
- Bounds for Certain Multiprocessing AnomaliesBell System Technical Journal, 1966