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

• 作者: 张少强 马希荣
• 来源期刊: 应用数学
• 学科: 工学
• 关键词: 排序 分批 多项式时间近似方案 煅烧工序
• 年，卷（期）: 2006,（2）
• 页码范围: 374-380
• 页数: 7页
• 分类号: O224|TP301.6
• 字数: 1916字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-9847.2006.02.024

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	马希荣	天津师范大学计算机与信息工程学院	31	296	9.0	16.0
2	张少强	天津师范大学计算机与信息工程学院	13	15	3.0	3.0