MINIMIZING TOTAL COMPLETION-TIME ON BATCH PROCESSING MACHINES

We study the problem of minimizing total completion time on single and parallel batch processing machines. A batch processing machine is one which can process up to B jobs simultaneously. The processing time of a batch is equal to the largest processing time among all jobs in the batch. This problem is motivated by burnin operations in the final te sting stage of semiconductor manufacturing and is expected to occur in other production environments. We provide an exact solution procedure for the single-machine problem and heuristic algorithms for both sing le and parallel machine problems. While the exact algorithms have limi ted applicability due to high computational requirements, extensive ex periments show that the heuristics are capable of consistently obtaini ng near-optimal solutions in very reasonable CPU times.