| 求带释放时间的半导体煅烧排序的最短交付时间的一个高效PTAS |
| |
| 引用本文： | 张少强,马希荣.求带释放时间的半导体煅烧排序的最短交付时间的一个高效PTAS[J].应用数学,2006,19(2):374-380. |
| |
| 作者姓名： | 张少强 马希荣 |
| |
| 作者单位： | 天津师范大学计算机与信息工程学院,天津,300384 |
| |
| 摘 要： | 本文研究一个目标是最小化最大交付时间的能分批处理的非中断单机排序问题．这个问题来源于半导体制造过程中对芯片煅烧工序的排序．煅烧炉可以看成一个能同时最多加工B（〈n）个工件的处理机．此外，每个工件有一个可以允许其加工的释放时间和一个完成加工后的额外交付时间．该问题就是将工件分批后再依批次的排序加工，使得所有工件都交付后所需的时间最短．我们设计了一个用时O（f（l／ε）n^5/2）的多项式时间近似方案，其中关于1／ε的指数函数厂（1／ε）对固定的ε是个常数.
|
| 关 键 词： | 排序 分批 多项式时间近似方案 煅烧工序 |
| 文章编号： | 1001-9847(2006)02-0374-07 |
| 收稿时间： | 2005-03-24 |
| 修稿时间： | 2005年3月24日 |
An Efficient PTAS for Semiconductor Burn-in Scheduling with Release Dates to Minimize Maximum Delivery Time |
| |
| ZHANG Shao-qiang,MA Xi-rong.An Efficient PTAS for Semiconductor Burn-in Scheduling with Release Dates to Minimize Maximum Delivery Time[J].Mathematica Applicata,2006,19(2):374-380. |
| |
| Authors: | ZHANG Shao-qiang MA Xi-rong |
| |
| Institution: | College of Cornp. and In fo. Eng. , Tianjin Narmal University , Tianjin 300384, China |
| |
| Abstract: | 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(1/ε)n5/2), where f(1/ε) is a constant for fixed ε that is exponential in 1/e. |
| |
| Keywords: | Scheduling Batch Polynomial time approximation scheme Burn-in |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
