A hybrid genetic algorithm to minimize makespan for the single batch machine dynamic scheduling problem

This paper considers a single batch machine dynamic scheduling problem, which is readily found in the burn-in operation of semiconductor manufacturing. The batch machine can process several jobs as a batch simultaneously, within the capacity limit of the machine, and the processing time is represented by the longest processing time among all jobs in a batch. For a single batch machine problem with arbitrary job release time, we proposed an improved algorithm (merge-split procedure) to refine the solution obtained by the LPT-BFF heuristic, and two versions of a hybrid genetic algorithm (GA) are introduced in this paper. Each version of the hybrid GA diversifies job sequences using the GA operators in stage 1, forms batches in stage 2, and finally sequence the batches in stage 3. The difference is that merge-split procedures are involved in the second version of the hybrid GA. Computational experiments showed that the hybrid GA would obtain satisfactory average solution quality and the merge-split procedures would be good at reinforcing the solution consistency of the hybrid GA.