Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times

Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times

0.00 Avg rating0 Votes
Article ID: iaor20062604
Country: United Kingdom
Volume: 32
Issue: 11
Start Page Number: 2731
End Page Number: 2750
Publication Date: Nov 2005
Journal: Computers and Operations Research
Authors: , , ,
Keywords: heuristics
Abstract:

This research is motivated by a scheduling problem found in the diffusion and oxidation areas of semiconductor wafer fabrication, where the machines can be modeled as parallel batch processors. We attempt to minimize total weighted tardiness on parallel batch machines with incompatible job families and unequal ready times of the jobs. Given that the problem is NP-hard, we propose two different decomposition approaches. The first approach forms fixed batches, then assigns these batches to the machines using a genetic algorithm (GA), and finally sequences the batches on individual machines. The second approach first assigns jobs to machines using a GA, then forms batches on each machine for the jobs assigned to it, and finally sequences these batches. Dispatching and scheduling rules are used for the batching phase and the sequencing phase of the two approaches. In addition, as part of the second decomposition approach, we develop variations of a time window heuristic based on a decision theory approach for forming and sequencing the batches on a single machine.

Reviews

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