An efficient polynomial time approximation scheme for semiconductor burn-in scheduling with release dates to minimize maximum delivery time

We study the problem of scheduling n independent jobs without preemption on a batch processing machine so as to minimize the maximum delivery time. This problem arises in the burn-in stage of semiconductor manufacturing. The burn-in oven is modeled as a batch processing machine which can handle up to B (<n) jobs simultaneously. In addition, each job has a release date, when it becomes available for processing, and requires an additional delivery time after completing its processing. The problem involves assigning jobs to batches and sequencing the batches so as to minimize the time by which all jobs are delivered. We develop an efficient polynomial time approximation scheme.