發(fā)布時(shí)間：2018-03-28 23:35

  本文選題：平行機(jī)　切入點(diǎn)：可中斷排序　出處：《鄭州大學(xué)》2016年博士論文

【摘要】：本文研究了兩個(gè)具有運(yùn)送協(xié)調(diào)性的平行機(jī)排序問(wèn)題。目標(biāo)函數(shù)都是求最小化最大運(yùn)送完成時(shí)間,即將所有工件加工完畢后運(yùn)送到顧客,且運(yùn)送車(chē)輛返回到生產(chǎn)車(chē)間的時(shí)間。由于工件的作業(yè)是由加工和運(yùn)送兩個(gè)階段構(gòu)成,我們稱(chēng)這樣的間題為兩階段排序問(wèn)題。在第二章,我們研究了平行機(jī)工件可中斷兩階段排序問(wèn)題,其中N={1,2,…,n}是n個(gè)工件的集合。這n個(gè)工件首先在m臺(tái)平行機(jī)上可中斷地加工,然后由一輛汽車(chē)運(yùn)送給顧客,每次只能運(yùn)送一個(gè)工件。該問(wèn)題的一個(gè)排序包括n個(gè)工件在m臺(tái)平行機(jī)上可中斷加工的方案以及n個(gè)工件的運(yùn)送方案。一個(gè)工件j可以被運(yùn)送只有當(dāng)它加工完畢并且車(chē)輛可用。令Dj是工件j的運(yùn)送完成時(shí)間,也即是工件j運(yùn)送到它對(duì)應(yīng)的顧客并且車(chē)輛返回到工廠的時(shí)間。我們使用Dmax來(lái)表示所有工件的最大運(yùn)送完成時(shí)間。按照Graham等人[23]對(duì)排序問(wèn)題的表示方法,本章研究的問(wèn)題可以表示為P|pmtn|Dmax。我們證明了該問(wèn)題是強(qiáng)NP-困難的并給出了一個(gè)3/2-近似算法。在第三章,我們研究了在ADT(assignable delivery times)假設(shè)下平行機(jī)工件不可中斷兩階段排序問(wèn)題。在該問(wèn)題中,n個(gè)工件的集合N={1,2,…,n}首先在m臺(tái)平行機(jī)上加工,然后由一輛汽車(chē)將它們運(yùn)送到顧客,一次只能運(yùn)送一個(gè)工件。在ADT假設(shè)下,n個(gè)運(yùn)送時(shí)間的集合提前給定,但每個(gè)運(yùn)送時(shí)間并不附屬于某個(gè)特定的工件。該問(wèn)題的一個(gè)排序包括n個(gè)工件在m臺(tái)機(jī)器上的一個(gè)加工方案,n個(gè)運(yùn)送時(shí)間與n個(gè)工件的一個(gè)分配,以及n個(gè)工件的一個(gè)運(yùn)送方案,其中一個(gè)工件j只有當(dāng)它加工完畢且車(chē)輛可用才能夠分配一個(gè)運(yùn)送時(shí)間且被汽車(chē)運(yùn)送。令Dj是工件j的運(yùn)送完成時(shí)間,也即是工件j運(yùn)送到它的顧客且汽車(chē)返回工廠的時(shí)間。我們用Dmax來(lái)表示所有工件的最大的運(yùn)送完成時(shí)間。按照Graham等人[23]對(duì)排序問(wèn)題的經(jīng)典的表示方法,本章研究的問(wèn)題可以表示為P|ADT|Dmax。注意到經(jīng)典的強(qiáng)NP-困難的排序問(wèn)題P||Cmax是問(wèn)題P|ADT|Dmax的一個(gè)特殊形式。因此,問(wèn)題P|ADT|Dmax也是強(qiáng)NP-困難的。對(duì)問(wèn)題P|ADT|Dmax,我們給出了一個(gè)3/2-近似的算法和一個(gè)多項(xiàng)式時(shí)間近似方案(PTAS)。
[Abstract]:In this paper, we study the scheduling problem of two parallel machines with transport coordination. The objective function is to minimize the maximum delivery time, that is, after all the jobs are processed, they are transported to the customers. And the time when the transport vehicle returns to the workshop. Since the work of the workpiece is made up of two stages of processing and transporting, we call this the two-stage scheduling problem. In this paper, we study the problem of interruptible two-stage scheduling of parallel machine workpieces, where N = {1k2, 鈥，

本文編號(hào)：1678594