《2016 Heuristics for minimizing total weighted tardiness in complex job shops》.pdf

International Journal of Production Research, Vol. 43, No. 10, 15 May 2005, 1943–1963 Heuristics for minimizing total weighted tardiness in complex job shops S.J. MASONy*, J.W. FOWLERz, W.M. CARLYLE} and D.C. MONTGOMERYz yDepartment of Industrial Engineering, 4207 Bell Engineering Center, University of Arkansas, Fayetteville, Arkansas 72701 zDepartment of Industrial Engineering, Arizona State University, P.O. Box 875906, Tempe, Arizona 85287-5906 }Operations Research Department, Naval Postgraduate School, Monterey, California 93943 (Received August 2004) Semi-conductor manufacturing is arguably one of the most complex manufactur- ing 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 character- istics 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 heur- istic (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 lar