帶沖突約束兩臺平行專用機排序的一個改進算法

張 亮，張 安，陳 永，陳光亭

(1.杭州電子科技大學理學院，浙江 杭州 310018；2.臺州學院電子與信息工程學院，浙江 臺州 318000)

0 引 言

1 問題描述

本文研究的是PD2conflict,seq1Cmax問題的一種特殊情形，即各個工件的加工時間需滿足

min{p1,1,p1,2,…,p1,n1}≥max{p2,1,p2,2,…,p2,n2}

(1)

Hong等[4]已經證明該情形是強NP-難。

2 算法設計與分析

對于滿足式(1)假設的PD2conflict,seq1Cmax問題，文獻[5]提出一種基于工件加工時間非增順序(Largest Processing Time first，LPT)規則的近似算法，簡稱LPT算法，主要步驟如下。

(1)將J1中的工件按給定的次序從零時刻開始無空閑地在M1上加工，直至完工。

(2)將J2中的工件按照加工時間非減次序排列。

(3)對J1中任意一個工件J1,j，其加工時間窗口為[S1,j,S1,j+p1,j]。從j=1到j=n1，在J2的序列中挑選出當前尚未加工且與J1,j不沖突的工件，在M2上的時間窗口[S1,j,S1,j+p1,j]內無空閑地加工該工件，除非該工件的完工時間超出上述時間窗口。

(4)若J2中仍有未加工的工件，則從S1,n1+p1,n1時刻開始，在M2上無空閑地加工這些工件，否則結束算法。

(1)令S1,1=0，即將工件J1,1安排在M1的零時刻加工。

(3)若J2中仍有未加工的工件，則在J1,n1的時間窗口中的最后一個工件的完工時，開始在M2上無空閑地加工這些工件，否則結束算法。

證明在J1,n1完工時間之后，才開始加工的那部分工件的集合，記為B5，B5可以為空集；J1中，在其時間窗口內，M2上工件加工時間之和不小于自身加工時間的工件的集合記為A1；J1/A1中，與B5中所有工件均沖突的工件的集合記為A4；J1/(A1∪A4)中，在其加工窗口內，M2上只加工專屬工件的工件的集合記為A3；記A2=J1/(A1∪A3∪A4)。在A1,A2,A3,A4中，工件的時間窗口內，M2上加工的工件集合分別記為B1,B2,B3,B4。MLPT算法所得排序類型如圖1所示。

圖1 MLPT算法所得排序類型

根據MLPT算法步驟，算法所得排序的最大完工時間可以表示為：

(2)

由A1,B1的定義及MLPT算法的步驟2，可知

(3)

顯然，有

0≤b4

(4)

最優排序需加工完J1和J2中的所有工件，又由于A4和B5的沖突關系，最優排序中這兩個集合中的工件的加工時間窗口不允許重疊，則最優排序的最大完工時間需滿足：

(5)

(6)

圖2 J1,x時間窗口內加工情況

(7)

圖3 J1,y時間窗口內加工情況

由a1,a2,a3和T1間的大小關系，MLPT算法的近似比分析分為以下兩種情形。

由式(2)、式(3)、式(5)可知，

(8)

由式(6)、式(7)可知，

(9)

由式(2)、式(5)和式(9)可知，

(10)

3 算法緊例

專用機M1和M2分別加工工件集J1={J1,1,J1,2}和J2={J2,1,J2,2,J2,3,J2,4}，M1上工件的加工順序為J1,1,J1,2。各工件的加工時間如表1所示，沖突圖如圖4所示。

表1 實例中各工件的加工時間表

圖4 實例的沖突圖

圖5 加工實例的排序結果

4 結束語