批可獲得性條件下帶運輸?shù)淖骞ぜ判?/H1>
發(fā)布時間：2018-06-18 11:33
本文選題：排序 + 工件族�。� 參考：《鄭州大學》2016年碩士論文
【摘要】：帶有工件運輸?shù)呐判蚴桥判蜓芯款I(lǐng)域中一個非常重要的現(xiàn)代排序模型.在該排序模型中,工件先在機器上進行加工,然后通過一些車輛將工件運輸給顧客,目標是讓運輸完工時間最短.本文我們研究帶運輸?shù)淖骞ぜ娜舾膳判騿栴}.在這些問題中,同一個工件族里的工件可以在一起加工從而形成一個加工批,只有一輛車來運輸已經(jīng)加工完的工件,不同工件族的工件不能在一批運輸,而且當機器從一個工件族的加工批變成另一個工件族的加工批的時候,需要增加一個安裝時間.目標函數(shù)是讓這一輛車將最后一個運輸批運輸給顧客并且返回到機器的時間最小.在批可獲得性條件下,文中研究的四個問題用三參數(shù)表示法可記為：(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等價于兩臺機器上的流水作業(yè)問題F2‖Cmax,因而Johnson規(guī)則得到的排序就是問題1DFB的最優(yōu)解.然后我們用等規(guī)模劃分問題進行歸結(jié)證明了在沒有GT假設的條件下,問題1DFB是NP-困難的,并且對問題1DFB給出了一個近似比是7/4的近似算法.在第三章,我們研究問題1DFB(t),它是問題1DFB在所有工件的運輸時間都相等的特殊情形,即t_i=t.我們證明了在第一章中針對問題1DFB的近似算法對問題1DFB(t)來說近似比是5/3.在第四章,我們研究問題1DFB(s),它是問題1DFB在所有工件族的安裝時間都相等的特殊情形,即s_i=s.以第一章中針對問題1DFB的近似算法為基礎(chǔ),我們對問題1DFB(s)給出了一個近似比是5/3的近似算法.在第五章,我們研究問題1DFB(s,t),它是問題1DFB在所有工件族的安裝時間都相等并且所有工件的運輸時間也都相等的特殊情形,即t_i=t且s_i=s.以第一章中針對問題1DFB的近似算法為基礎(chǔ),我們對問題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
本文鏈接：http://sikaile.net/kejilunwen/yysx/2035336.html
本文選題：排序 + 工件族�。� 參考：《鄭州大學》2016年碩士論文
【摘要】：帶有工件運輸?shù)呐判蚴桥判蜓芯款I(lǐng)域中一個非常重要的現(xiàn)代排序模型.在該排序模型中,工件先在機器上進行加工,然后通過一些車輛將工件運輸給顧客,目標是讓運輸完工時間最短.本文我們研究帶運輸?shù)淖骞ぜ娜舾膳判騿栴}.在這些問題中,同一個工件族里的工件可以在一起加工從而形成一個加工批,只有一輛車來運輸已經(jīng)加工完的工件,不同工件族的工件不能在一批運輸,而且當機器從一個工件族的加工批變成另一個工件族的加工批的時候,需要增加一個安裝時間.目標函數(shù)是讓這一輛車將最后一個運輸批運輸給顧客并且返回到機器的時間最小.在批可獲得性條件下,文中研究的四個問題用三參數(shù)表示法可記為：(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等價于兩臺機器上的流水作業(yè)問題F2‖Cmax,因而Johnson規(guī)則得到的排序就是問題1DFB的最優(yōu)解.然后我們用等規(guī)模劃分問題進行歸結(jié)證明了在沒有GT假設的條件下,問題1DFB是NP-困難的,并且對問題1DFB給出了一個近似比是7/4的近似算法.在第三章,我們研究問題1DFB(t),它是問題1DFB在所有工件的運輸時間都相等的特殊情形,即t_i=t.我們證明了在第一章中針對問題1DFB的近似算法對問題1DFB(t)來說近似比是5/3.在第四章,我們研究問題1DFB(s),它是問題1DFB在所有工件族的安裝時間都相等的特殊情形,即s_i=s.以第一章中針對問題1DFB的近似算法為基礎(chǔ),我們對問題1DFB(s)給出了一個近似比是5/3的近似算法.在第五章,我們研究問題1DFB(s,t),它是問題1DFB在所有工件族的安裝時間都相等并且所有工件的運輸時間也都相等的特殊情形,即t_i=t且s_i=s.以第一章中針對問題1DFB的近似算法為基礎(chǔ),我們對問題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
本文鏈接：http://sikaile.net/kejilunwen/yysx/2035336.html
最近更新
教材專著
