最小化时间表长的带有多个工件组有界继列批单机在线排序

摘要：

在制造系统和半导体流水线上经常需要考虑的是在线继列分批问题。本文所考虑的问题中，每个工件具有各自的安装时间和加工时间(s, p)，属于同一组的工件才能在同一批中加工，每一批最多可以加工b个工件，批的安装时间和加工时间分别为这一批中工件的最大安装时间和加工时间之和，目标函数是最小化工件的最大完工时间。利用对手法证明了任何一个在线算法的竞争比都不小于max{b2b+1,1+α}，且给出了一个渐近意义下最好的竞争比是2的在线算法。

关键词：单机排序、在线、继列分批、组、竞争比

分类号：O224(运筹学)

资助基金：The National Natural Science Foundation of China11071142,11201259,11201121;the Basic and Advanced Technology Research Project of Henan Province082300410070;the Nature Science Foundation of the Education Department of Henan Province2011B110007,2011B110008;the Nature Science Foundation of Shandong ProvinceZR2010AM034;the Science Foundation of Henan Uni-versity of Technology10XZR010

在线出版日期：2014-07-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：417-423