论文部分内容阅读
带有工件运输的排序是排序研究领域中一个非常重要的现代排序模型。在该排序模型中，工件先在机器上进行加工，然后通过一些车辆将工件运输给顾客，目标是让运输完工时间最短。 本文我们研究带运输的族工件的若干排序问题。在这些问题中，同一个工件族里的工件可以在一起加工从而形成一个加工批，只有一辆车来运输已经加工完的工件，不同工件族的工件不能在一批运输，而且当机器从一个工件族的加工批变成另一个工件族的加工批的时候，需要增加一个安装时间。目标函数是让这一辆车将最后一个运输批运输给顾客并且返回到机器的时间最小。在批可获得性条件下，文中研究的四个问题用三参数表示法可记为： (1)1→D,f|v=1,Si,Ci,ti|Cmax.(1DFB)。 (2)1→D,f|v=1,Si,Ci,ti=t|Cmax.(1DFB(t))。 (3)1→D,f|v=1,Si=S,Ci,ti|Cmax.(1DFB(s))。 (4)1→D,f|v=1,Si=S,Ci,ti=t|Cmax.(1DFB(s,t))。 在第二章，我们研究问题1DFB。我们证明了在GT假设下，问题1DFB等价于两台机器上的流水作业问题FSUCmax,因而Johnson规则得到的排序就是问题1DFB的最优解。然后我们用等规模划分问题进行归结证明了在没有GT假设的条件下，问题1DFB是 NP-困难的，并且对问题1DFB给出了一个近似比是7/4的近似算法。 在第三章，我们研究问题1DFB(t),它是问题1DFB在所有工件的运输时间都相等的特殊情形，即ti=t。我们证明了在第一章中针对问题1DFB的近似算法对问题1DFB(t)来说近似比是5/3。 在第四章，我们研究问题1DFB(s),它是问题1DFB在所有工件族的安装时间都相等的特殊情形，即si=s。以第一章中针对问题1DFB的近似算法为基础，我们对问题1DFB(s)给出了一个近似比是5/3的近似算法。 在第五章，我们研究问题1DFB(s,t),它是问题1DFB在所有工件族的安装时间都相等并且所有工件的运输时间也都相等的特殊情形，即ti=t且si=s。以第一章中针对问题1DFB的近似算法为基础,我们对问题1DFB(s,t)给出了一个近似比是3/2的近似算法。