Heuristics for minimizing total weighted tardiness in complex job shops

S. J. Mason, John Fowler, W. M. Carlyle, Douglas Montgomery

Research output: Contribution to journalArticlepeer-review

38 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)1943-1963
Number of pages21
JournalInternational Journal of Production Research
Issue number10
StatePublished - May 15 2005


  • Heuristic
  • Integer programming
  • Scheduling
  • Shifting bottleneck

ASJC Scopus subject areas

  • Strategy and Management
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Heuristics for minimizing total weighted tardiness in complex job shops'. Together they form a unique fingerprint.

Cite this