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

【摘要】：本文研究了兩個具有運送協(xié)調(diào)性的平行機排序問題。目標函數(shù)都是求最小化最大運送完成時間,即將所有工件加工完畢后運送到顧客,且運送車輛返回到生產(chǎn)車間的時間。由于工件的作業(yè)是由加工和運送兩個階段構(gòu)成,我們稱這樣的間題為兩階段排序問題。在第二章,我們研究了平行機工件可中斷兩階段排序問題,其中N={1,2,…,n}是n個工件的集合。這n個工件首先在m臺平行機上可中斷地加工,然后由一輛汽車運送給顧客,每次只能運送一個工件。該問題的一個排序包括n個工件在m臺平行機上可中斷加工的方案以及n個工件的運送方案。一個工件j可以被運送只有當(dāng)它加工完畢并且車輛可用。令Dj是工件j的運送完成時間,也即是工件j運送到它對應(yīng)的顧客并且車輛返回到工廠的時間。我們使用Dmax來表示所有工件的最大運送完成時間。按照Graham等人[23]對排序問題的表示方法,本章研究的問題可以表示為P|pmtn|Dmax。我們證明了該問題是強NP-困難的并給出了一個3/2-近似算法。在第三章,我們研究了在ADT(assignable delivery times)假設(shè)下平行機工件不可中斷兩階段排序問題。在該問題中,n個工件的集合N={1,2,…,n}首先在m臺平行機上加工,然后由一輛汽車將它們運送到顧客,一次只能運送一個工件。在ADT假設(shè)下,n個運送時間的集合提前給定,但每個運送時間并不附屬于某個特定的工件。該問題的一個排序包括n個工件在m臺機器上的一個加工方案,n個運送時間與n個工件的一個分配,以及n個工件的一個運送方案,其中一個工件j只有當(dāng)它加工完畢且車輛可用才能夠分配一個運送時間且被汽車運送。令Dj是工件j的運送完成時間,也即是工件j運送到它的顧客且汽車返回工廠的時間。我們用Dmax來表示所有工件的最大的運送完成時間。按照Graham等人[23]對排序問題的經(jīng)典的表示方法,本章研究的問題可以表示為P|ADT|Dmax。注意到經(jīng)典的強NP-困難的排序問題P||Cmax是問題P|ADT|Dmax的一個特殊形式。因此,問題P|ADT|Dmax也是強NP-困難的。對問題P|ADT|Dmax,我們給出了一個3/2-近似的算法和一個多項式時間近似方案(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, 鈥，

本文編號：1678594