Genetic algorithm based scheduling of parallel batch machines with incompatible job families to minimize total weighted tardiness

This research is motivated by a scheduling problem found in the diffusion and oxidation areas of semiconductor wafer fabrication, where the machines can be modelled as parallel batch processors. We attempt to minimize total weighted tardiness on parallel batch machines with incompatible job families. Given that the problem is NP-hard, we propose two different versions of a genetic algorithm (GA), each consisting of three different phases. The first version forms fixed batches, then assigns batches to the machines using a GA, and finally sequences the batches on individual machines. The second version assigns jobs to machines using a GA, then forms batches on each machine for the jobs assigned to it, and finally sequences these batches. Heuristics are used for the batching phase and the sequencing phase. For both these versions an additional fourth phase can be included wherein the sequenced batches are modified using pairwise swapping techniques. Using stochastically generated test data we show that algorithms of the first version of the GA outperform (1) traditional dispatching rules with respect to solution quality and (2) the algorithms of the second version with respect to both solution quality and computation time.