A joint GA plus DP approach for single burn-in oven scheduling problems with makespan criterion

This research is motivated by the scheduling problem found in the burn-in operation of semiconductor final testing, where jobs are associated with release times, processing times, and sizes. The burn-in ovens are modeled as batch-processing machines which can process a batch of several jobs as long as the total sizes of the jobs do not exceed the machine capacity, and the processing time of a batch is equal to the longest time among all the jobs in the batch. Moreover, this paper attempts to schedule jobs on a single batch-processing machine to minimize makespan. A joint GA+DP algorithm is proposed involving two stages: (1) the formation of job sequence by genetic algorithm operators, and (2) the formation of batches by a dynamic programming algorithm. Computational experiments are given to examine the performance of the proposed algorithm. The experimental results indicate that the joint GA+DP approach has well improved on all instances with respect to solution quality and runtime.