批可获得性条件下带运输的族工件排序

发布时间：2018-06-18 11:33

  本文选题：排序 + 工件族　； 参考：《郑州大学》2016年硕士论文

【摘要】：带有工件运输的排序是排序研究领域中一个非常重要的现代排序模型.在该排序模型中,工件先在机器上进行加工,然后通过一些车辆将工件运输给顾客,目标是让运输完工时间最短.本文我们研究带运输的族工件的若干排序问题.在这些问题中,同一个工件族里的工件可以在一起加工从而形成一个加工批,只有一辆车来运输已经加工完的工件,不同工件族的工件不能在一批运输,而且当机器从一个工件族的加工批变成另一个工件族的加工批的时候,需要增加一个安装时间.目标函数是让这一辆车将最后一个运输批运输给顾客并且返回到机器的时间最小.在批可获得性条件下,文中研究的四个问题用三参数表示法可记为：(1)1→D,f|v=1,s_i,c_i,t_i|Cmax.(1DFB)(2)1→D,f|v=1,s_i,c_i,t_i=t|Cmax.(1DFB(t))(3)1→D,f|v=1,s_i=s,c_i,t_i|Cmax.(1DFB(s))(4)1→D,f|v=1,s_i=s,c_i,t_i=t|Cmax.(1DFB(s,t))在第二章,我们研究问题1DFB.我们证明了在GT假设下,问题1DFB等价于两台机器上的流水作业问题F2‖Cmax,因而Johnson规则得到的排序就是问题1DFB的最优解.然后我们用等规模划分问题进行归结证明了在没有GT假设的条件下,问题1DFB是NP-困难的,并且对问题1DFB给出了一个近似比是7/4的近似算法.在第三章,我们研究问题1DFB(t),它是问题1DFB在所有工件的运输时间都相等的特殊情形,即t_i=t.我们证明了在第一章中针对问题1DFB的近似算法对问题1DFB(t)来说近似比是5/3.在第四章,我们研究问题1DFB(s),它是问题1DFB在所有工件族的安装时间都相等的特殊情形,即s_i=s.以第一章中针对问题1DFB的近似算法为基础,我们对问题1DFB(s)给出了一个近似比是5/3的近似算法.在第五章,我们研究问题1DFB(s,t),它是问题1DFB在所有工件族的安装时间都相等并且所有工件的运输时间也都相等的特殊情形,即t_i=t且s_i=s.以第一章中针对问题1DFB的近似算法为基础,我们对问题1DFB(s,t)给出了一个近似比是3/2的近似算法.
[Abstract]:Scheduling with the transport of jobs is a very important modern sorting model in the field of sorting research. In this sort model, the workpiece is processed on the machine first, and then transported to the customer by some vehicles. The goal is to make the transportation finish the shortest time. In this paper, we study some scheduling problems of the family of jobs with transport. In these problems, the workpieces in the same workpiece family can be processed together to form a processing batch, only one car can transport the finished workpiece, and the workpieces of different workpiece families cannot be transported in one batch. And when the machine from one workpiece family of processing batches to another workpiece family of processing batches, need to add an installation time. The objective function is to let the car ship the last shipment to the customer and return to the machine with minimal time. 鍦ㄦ壒鍙�鑾峰緱妫�

本文编号：2035336