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