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

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

0 引 言

1 問題描述

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

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

(1)

Hong等[4]已經(jīng)證明該情形是強(qiáng)NP-難。

2 算法設(shè)計(jì)與分析

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

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

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

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

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

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

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

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

圖1 MLPT算法所得排序類型

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

(2)

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

(3)

顯然，有

0≤b4

(4)

最優(yōu)排序需加工完J1和J2中的所有工件，又由于A4和B5的沖突關(guān)系，最優(yōu)排序中這兩個(gè)集合中的工件的加工時(shí)間窗口不允許重疊，則最優(yōu)排序的最大完工時(shí)間需滿足：

(5)

(6)

圖2 J1,x時(shí)間窗口內(nèi)加工情況

(7)

圖3 J1,y時(shí)間窗口內(nèi)加工情況

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

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

(8)

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

(9)

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

(10)

3 算法緊例

專用機(jī)M1和M2分別加工工件集J1={J1,1,J1,2}和J2={J2,1,J2,2,J2,3,J2,4}，M1上工件的加工順序?yàn)镴1,1,J1,2。各工件的加工時(shí)間如表1所示，沖突圖如圖4所示。

表1 實(shí)例中各工件的加工時(shí)間表

圖4 實(shí)例的沖突圖

圖5 加工實(shí)例的排序結(jié)果

4 結(jié)束語