Hybrid Flow-Shop: a Memetic Algorithm Using Constraint-Based Scheduling for Efficient Search |
| |
Authors: | Antoine Jouglet Ceyda Oğuz Marc Sevaux |
| |
Institution: | 1. HEUDIASYC, UMR CNRS 6599, Centre de Recherche de Royallieu, Université de Technologie de Compiègne, BP 20529, 60205, Compiègne cedex, France 2. Department of Industrial Engineering, Ko? University, Rumeli Feneri Yolu, Sar?yer, 34450, ?stanbul, Turkey 3. UEB—Lab-STICC, UMR CNRS 3192, Centre de Recherche, Université de Bretagne Sud, BP 92116, 56321, Lorient cedex, France
|
| |
Abstract: | The paper considers the hybrid flow-shop scheduling problem with multiprocessor tasks. Motivated by the computational complexity
of the problem, we propose a memetic algorithm for this problem in the paper. We first describe the implementation details
of a genetic algorithm, which is used in the memetic algorithm. We then propose a constraint programming based branch-and-bound
algorithm to be employed as the local search engine of the memetic algorithm. Next, we present the new memetic algorithm.
We lastly explain the computational experiments carried out to evaluate the performance of three algorithms (genetic algorithm,
constraint programming based branch-and-bound algorithm, and memetic algorithm) in terms of both the quality of the solutions
produced and the efficiency. These results demonstrate that the memetic algorithm produces better quality solutions and that
it is very efficient. |
| |
Keywords: | Multiprocessor task scheduling Hybrid flow-shop Genetic algorithm Constraint programming Memetic algorithm |
本文献已被 SpringerLink 等数据库收录! |
|