帶沖突約束的兩臺專用機(jī)器調(diào)度問題

龔 悅，張 安，陳光亭，李好好，陳 永

(1.杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018；2.臺州學(xué)院電子與信息工程學(xué)院，浙江 臺州 318000；3.浙江財經(jīng)大學(xué)數(shù)據(jù)科學(xué)學(xué)院，浙江 杭州 310018)

0 引 言

并行專用機(jī)器調(diào)度問題廣泛存在于各類制造業(yè)，更優(yōu)的調(diào)度策略有助于企業(yè)減少成本。Goemans[1]研究并行專用機(jī)器調(diào)度問題，并針對極小化最大完工時間的目標(biāo)提出一個近似比為7/6的近似算法?！安⑿袑Ｓ脵C(jī)器”一詞意味著每個作業(yè)都有1個專門的機(jī)器用于處理該作業(yè)。如果機(jī)器的數(shù)量是任意的且僅有1個非共享資源，該問題是NP-難的[2]。隨后，Kellerer等[3]進(jìn)一步證明了當(dāng)有2種類型的資源，且每種類型的資源恰好有2個單位，每個作業(yè)都將消耗2個單位的資源情況下，2臺并行專用機(jī)器及多臺并行專用機(jī)器的調(diào)度問題仍是NP-難的。Even等[4]針對m臺機(jī)器和單位作業(yè)的情形，證明了任何確定性在線算法的近似比至少為2-1/m；在預(yù)先已知作業(yè)個數(shù)的情況下，還提出了一個近似比為2-1/7的在線算法。即使專用機(jī)器上已知作業(yè)序列，上述提到的幾個調(diào)度問題仍是NP-難的[5-8]。本文討論其中1臺機(jī)器工作序列已知的2臺專用機(jī)器的調(diào)度問題。

1 算法設(shè)計與分析

實際生產(chǎn)中，每個作業(yè)對加工資源都有特定需求，如熟練的技術(shù)人員或?qū)Ｓ霉ぞ?。?dāng)某些作業(yè)對特定資源的總需求超過供應(yīng)量時，這些作業(yè)之間就產(chǎn)生沖突。在任何時刻，2個相互沖突的作業(yè)不允許同時進(jìn)行加工。對并行機(jī)器調(diào)度施加這樣的限制是合理的，因為在制造業(yè)或服務(wù)業(yè)中資源是有限的。在帶有沖突約束的條件下，調(diào)度規(guī)定了將機(jī)器、時間間隔和資源分配給具有沖突約束的作業(yè)。本文研究該問題的一個變體，即其中專用機(jī)器M1上作業(yè)的加工順序已經(jīng)給出，目標(biāo)為極小化最大完工時間。由于該問題是NP-難的，下面給出求解該問題的多項式時間近似算法并從理論上分析得到算法的近似比。

假設(shè)2臺并行專用機(jī)器M1和M2分別用于處理2個不相交的作業(yè)集N1={J1,1,J1,2,…,J1,n1}，N2={J2,1,J2,2,…,J2,n2}，其中n1，n2分別表示2個集合中作業(yè)的個數(shù)。任何1臺機(jī)器在同一時刻最多只能處理1個作業(yè)，每個作業(yè)只能在1臺機(jī)器上被處理，搶占和中斷是不允許的。作業(yè)集N1中的作業(yè)加工順序已經(jīng)固定，令機(jī)器M1上作業(yè)的加工順序為J1,1,J1,2,…,J1,n1，作業(yè)Ji,j,i∈{1,2},j∈{1,2,…,ni}的處理時間為pi,j，且有：

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

(1)

任意給定1個排序，Ci,j表示作業(yè)Ji,j的完工時間，Cmax表示該排序的總完工時間，即Cmax=maxi=1,2,j=1,2,…,ni{Ci,j}，目標(biāo)是尋求最大完工時間的最小排序，即minCmax。

作業(yè)間的沖突約束可通過1個無向二部圖G=(V1∪V2,E)來表示，其中V1=N1和V2=N2對應(yīng)2個作業(yè)集，若作業(yè)J1,s∈N1和作業(yè)J2,t∈N2之間存在沖突，則邊(J1,s,J2,t)∈E，這樣所定義的二部圖稱之為沖突圖。在任何時刻都不能同時處理2個相互沖突的作業(yè)。特別地，屬于同一作業(yè)集的2個作業(yè)不存在沖突約束。

為了解決以上問題，本文提出一種貪婪算法——Longest Processing Time算法，簡稱LPT算法。算法具體描述如下。

(1)機(jī)器M1上的作業(yè)連續(xù)加工，即作業(yè)之間無空閑。

(2)將作業(yè)集N2中的作業(yè)按照加工時間從大到小的順序進(jìn)行排列。

(4)若N2中仍有未加工的作業(yè)，則在J1,n1的完工時間之后開始加工。

LPT算法得到的可行排序如圖1所示。

M1:J1,1J1,2J1,3…J1,n1 M2:J2,1J2,2δ1δ2J2,3…J2,i-1δn1J2,i…J2,n2

圖1 加工序列

證明在LPT算法得到排序中，將作業(yè)集N1(N2)分為2個集合：N11,N12(N21,N22)。N22表示所有在J1,n1的完工時間之后開始加工的作業(yè)集合。N21表示在J1,n1的完工時間之前開始加工的作業(yè)集合。N11表示與N22中至少1個作業(yè)不沖突的作業(yè)集合。N12表示與N22中所有作業(yè)都沖突的作業(yè)集合。令P1,P2,P11,P12,P21,P22分別表示作業(yè)集N1,N2,N11,N12，N21,N22中所有作業(yè)的加工時間總和。則有：

(2)

由于N12中任意作業(yè)與N22中所有作業(yè)之間均存在沖突，則有：

(3)

接下來，分2種情況進(jìn)行討論。

(2)若

P11>2/3P1

(4)

接下來證明

(5)

(6)

所以有：

(7)

又因為：

(8)

所以有：

p2,j2>δj1

(9)

(10)

又由式(8)可知：

(11)

所以有：

(12)

將式(4)代入式(12)，可得：

P21>1/3P1

(13)

令δ=δ1+δ2+…+δn1，因為

P21+δ=P1

(14)

所以有：

δ<2/3P1

(15)

則有：

(16)

2 算法緊例

圖2 作業(yè)沖突圖

假設(shè)機(jī)器M1和機(jī)器M2分別處理2個互不相交的作業(yè)集合，N1={J1,1,J1,2,J1,3}，N2={J2,1,J2,2,J2,3,J2,4,J2,5,J2,6}機(jī)器M1上作業(yè)的加工順序為J1,1,J1,2,J1,3，且min{p1,1,p1,2,p1,3}≥max{p2,1,p2,2,p2,3,p2,4,p2,5,p2,6}，需要加工的作業(yè)用job來表示，每個作業(yè)的加工時間如表1所示，其沖突圖如圖2所示。

表1 作業(yè)加工時間

通過運(yùn)行LPT算法得到的算法解如圖3所示，不難發(fā)現(xiàn)最優(yōu)解如圖4所示。

M1:111M2:1/2+ε1/2+ε1/21/21/21/2

M1:111M2:1/21/21/21/21/2+ε1/2+ε

3 結(jié)束語

本文研究了具有沖突約束且1臺機(jī)器作業(yè)順序已定的并行專用機(jī)器調(diào)度問題，基于最大加工時間優(yōu)先原則設(shè)計了近似比為5/3的近似算法。后續(xù)將從2個方面進(jìn)行研究，首先對算法進(jìn)行進(jìn)一步改進(jìn)，由于算法僅僅采用了貪婪算法的思想，若在此基礎(chǔ)上增加匹配，改進(jìn)后的算法可能得到更好的近似比。其次，目標(biāo)函數(shù)可以變?yōu)榈?臺機(jī)器上的最大完工時間，在沖突圖不同的情況下證明該問題的復(fù)雜性。