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

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

反相容工件系统的加权完工时间和的重新排序问题(英文)

重新排序问题是指在原始工件已经安排好的情形下,新到的工件集与原始工件集一起重新再排序,这是实际工作中常见一类优化问题。本文考虑了单机上当工件加工时间与权重反相容时,在最大错位量约束下的加权完工时间和最小化的重新排序问题。对于提出的四个问题,即在最大序列错位、最大时间错位、总序列错位和总时间错位约束下的加权完工时间和重新排序,基于问题的结构性质,运用动态规划方法分别给出了这些问题的多项式时间或拟多项式时间算法。