Minimizing the total completion time in a two-machine flowshop with sequence-independent setup times

Abstract

We consider the problem of minimizing the sum of completion times in a two-machine permutation flowshop subject to setup times. We propose a new priority rule, several constructive heuristics, local search procedures, as well as an effective multiple crossover genetic algorithm. Computational experiments carried out on a large set of randomly generated instances provide evidence that a constructive heuristic based on newly derived priority rule dominates all the proposed constructive heuristics. More specifically, we show that one of our proposed constructive heuristics outperforms the best constructive heuristic in the literature in terms of both error and computational time. Furthermore, we show that one of our proposed local search-based heuristics outperforms the best local search heuristic in the literature in terms of again both error and computational time. We also show that, in terms of quality-to-CPU time ratio, the multiple crossover genetic algorithm performs consistently well.

Keywords:

• scheduling
• flowshop
• total completion time
• independent setup times
• heuristics
• genetic local search algorithm

Acknowledgements

The first author would like to thank Fatimah Alnijris's Research Chair for Advanced Manufacturing Technology for the financial support provided for this research. Also, the authors would like to thank Anis Gharbi for his suggestions regarding the improvement of this paper.