An efficient genetic algorithm for a hybrid flow shop scheduling problem with time lags and sequence-dependent setup time
Department of Mathematic, Payame Noor University, Tehran, Iran
2 Department of Industrial Engineering, Bu-Ali Sina University, Hamedan, Iran
3 Department of Industrial Engineering, Birjand University of Technology, Birjand, Iran
* e-mail: firstname.lastname@example.org
Accepted: 23 November 2014
In this paper, a hybrid flow shop scheduling problem with a new approach considering time lags and sequence-dependent setup time in realistic situations is presented. Since few works have been implemented in this field, the necessity of finding better solutions is a motivation to extend heuristic or meta-heuristic algorithms. This type of production system is found in industries such as food processing, chemical, textile, metallurgical, printed circuit board, and automobile manufacturing. A mixed integer linear programming (MILP) model is proposed to minimize the makespan. Since this problem is known as NP-Hard class, a meta-heuristic algorithm, named Genetic Algorithm (GA), and three heuristic algorithms (Johnson, SPTCH and Palmer) are proposed. Numerical experiments of different sizes are implemented to evaluate the performance of presented mathematical programming model and the designed GA in compare to heuristic algorithms and a benchmark algorithm. Computational results indicate that the designed GA can produce near optimal solutions in a short computational time for different size problems.
Key words: Hybrid flow shop / Scheduling / Sequence-dependent time lags / Sequence-dependent setup times / Genetic algorithm
© M. Farahmand-Mehr et al., Published by EDP Sciences, 2014
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.