Setup-oriented dispatching rules – a survey

Abstract

This paper provides a survey of dispatching rules that explicitly take into account setup times in their decision making. Rules are classified into the categories of purely setup-oriented, composite and family-based rules, and the most promising rules from the three categories are identified from the literature. These rules are then compared empirically on various job shop problems with sequence-dependent setup times for their performance regarding mean setup time, mean flow time, mean tardiness and proportion of tardy jobs. The setup times are modelled using setup time matrices, and five different types of matrices are applied to assess the influence of this factor on the relative performance of a setup-oriented dispatching rule. Experimental results indicate that the choice of the best rule is often dependent on the setup time matrix structure. While good family-based rules exist for reducing the mean setup time and mean flow time, they are clearly outperformed by effective composite rules for due date-related criteria. Moreover, the better rules all seem to rely on queue information rather than only job attributes.

Keywords:

• dispatching rules
• sequence-dependent setup times
• scheduling

Acknowledgements

The authors would like to thank Torsten Hildebrandt and Jens Heger from the BIBA institute at the University of Bremen for providing the simulation environment, and Robert J. Nickerson for conducting a preliminary study. This research has been supported by the German Research Council (DFG) under Grant BR 1592/7-1.