A novel hybrid genetic algorithm to solve the make-to-order sequence-dependent flow-shop scheduling problem

Subject Areas : Mathematical Optimization

Mohammad Mirabi ¹ , S. M. T. Fatemi Ghomi ² , F . Jolai ³

1 - Group of Industrial Engineering, Ayatollah Haeri University of Meybod, P.O. Box 89619-55133, Meybod, Iran
2 - Department of Industrial Engineering, Amirkabir University of Technology, P.O. Box 15916-34311, Tehran, Iran
3 - Department of Industrial Engineering, College of Engineering, University of Tehran, P.O. Box 14395-515, Tehran, Iran

Received: 2020-10-02 Accepted : 2020-10-02 Published : 2014-06-01

Keywords: Hybrid genetic algorithm  Scheduling  Permutation flow, shop  Sequence dependent,

Abstract :

Flow-shop scheduling problem (FSP) deals with the scheduling of a set of n jobs that visit a set of m machines in the same order. As the FSP is NP-hard, there is no efficient algorithm to reach the optimal solution of the problem. To minimize the holding, delay and setup costs of large permutation flow-shop scheduling problems with sequence-dependent setup times on each machine, this paper develops a novel hybrid genetic algorithm (HGA) with three genetic operators. Proposed HGA applies a modified approach to generate a pool of initial solutions, and also uses an improved heuristic called the iterated swap procedure to improve the initial solutions. We consider the make-to-order production approach that some sequences between jobs are assumed as tabu based on maximum allowable setup cost. In addition, the results are compared to some recently developed heuristics and computational experimental results show that the proposed HGA performs very competitively with respect to accuracy and efficiency of solution.