Heuristics for minimizing total weighted tardiness in complex job shops

Abstract

Semi-conductor manufacturing is arguably one of the most complex manufacturing processes in existence today. A semi-conductor wafer fabrication facility is comprised of batching machines, parallel machines, machines with sequence-dependent set-ups, and re-circulating product flow. The individual job release times and due dates combine with the other processing environment characteristics to form a ‘complex’ job shop scheduling problem. We first present a mixed-integer program (MIP) to minimize total weighted tardiness in a complex job shop. Since the problem is NP-hard, we compare a heuristic based on the MIP (MIP heuristic) with both a tuned version of a modified shifting bottleneck heuristic (SB heuristic) and three dispatching rules using random problem instances of a representative model from the literature. While the MIP heuristic typically produces superior schedules for problem instances with a small number of jobs, the SB heuristic consistently outperforms the MIP heuristic for larger problem instances. The SB heuristic's superior performance as compared to additional dispatching rules is also demonstrated for a larger, ‘real world’ dataset from the literature.

Keywords:

• Scheduling
• Integer programming
• Shifting bottleneck
• Heuristic

Acknowledgements

This research was partially supported by the Semiconductor Research Corporation (97-FJ-492 and 2001-NJ-880) and the National Science Foundation (DMI-9713750). The authors would like to thank the two anonymous referees who helped to significantly improve the content and quality of this paper.