Column generation for minimizing total completion time on a single machine with parallel batching

In manufacturing of integrated circuits, burn in operations are key operations to improve the quality by detecting early failures. Such operations are performed in the so-called batch ovens, able to process several circuits at the same time. In this paper, the problem of deciding in which sequence to process a given number of circuit boards in a batch oven is addressed. This corresponds to a single-machine scheduling problem on a machine with parallel batch job processing. A column generation algorithm is developed for the minimization of the total completion time when circuits have an individual size. The computational results show the efficiency and effectiveness of the proposed algorithm, able to solve instances up to 100 jobs.