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

作者：张少强; 马希荣

来源：应用数学, 2006, 19(2): 374-380.

DOI：10.3969/j.issn.1001-9847.2006.02.024

• 排序
• 分批
• 多项式时间近似方案
• 煅烧工序

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

• 出版日期2006
• 单位天津师范大学