Heuristics for minimizing total weighted tardiness in complex job shops

Heuristics for minimizing total weighted tardiness in complex job shops

0.00 Avg rating0 Votes
Article ID: iaor20053094
Country: United Kingdom
Volume: 43
Issue: 10
Start Page Number: 1943
End Page Number: 1963
Publication Date: Jan 2005
Journal: International Journal of Production Research
Authors: , , ,
Keywords: heuristics
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.

Reviews

Required fields are marked *. Your email address will not be published.