A genetic algorithm for a re-entrant job-shop scheduling problem with sequence-dependent setup times

Abstract

This article addresses a re-entrant job-shop scheduling problem with sequence-dependent setup times. The disjunctive graph model with the objective of the minimum makespan is used to capture the interactions between machines. On the basis of this representation, two heuristic procedures and a genetic algorithm are proposed to obtain near-optimal solutions for this problem. Also, an experimental design method for determining the various genetic parameters based on the Taguchi approach is presented. A comparative study is conducted to examine the performance of these proposed algorithms and the results show that the genetic algorithm outperforms the other heuristic procedures, which are modified versions of recently published existing methods.

Keywords:

• job-shop scheduling
• re-entrant work flows
• sequence-dependent setup
• genetic algorithm
• Taguchi method

Acknowledgements

This work was supported by Hankuk University of Foreign Studies Research Fund of 2008.