求带释放时间的半导体煅烧排序的最短交付时间的一个高效PTAS(英文)

An Efficient PTAS for Semiconductor Burn-in Scheduling with Release Dates to Minimize Maximum Delivery Time

本文研究一个目标是最小化最大交付时间的能分批处理的非中断单机排序问题.这个问题来源于半导体制造过程中对芯片煅烧工序的排序.煅烧炉可以看成一个能同时最多加工B(<n)个工件的处理机.此外,每个工件有一个可以允许其加工的释放时间和一个完成加工后的额外交付时间.该问题就是将工件分批后再依批次的排序加工,使得所有工件都交付后所需的时间最短.我们设计了一个用时O(f(1/ε)n5/2)的多项式时间近似方案,其中关于1/ε的指数函数f(1/ε)对固定的ε是个常数.

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 modelled 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 （PTAS） for it running in time O（ f（l/ε）n^5/2）, where f（l/ε） is a constant for fixed ε that is exponential in l/ε.