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


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


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 < /div>
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.