帶沖突約束的兩臺專用機器調度問題

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

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

0 引 言

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

1 算法設計與分析

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

假設2臺并行專用機器M1和M2分別用于處理2個不相交的作業集N1={J1,1,J1,2,…,J1,n1}，N2={J2,1,J2,2,…,J2,n2}，其中n1，n2分別表示2個集合中作業的個數。任何1臺機器在同一時刻最多只能處理1個作業，每個作業只能在1臺機器上被處理，搶占和中斷是不允許的。作業集N1中的作業加工順序已經固定，令機器M1上作業的加工順序為J1,1,J1,2,…,J1,n1，作業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表示作業Ji,j的完工時間，Cmax表示該排序的總完工時間，即Cmax=maxi=1,2,j=1,2,…,ni{Ci,j}，目標是尋求最大完工時間的最小排序，即minCmax。

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

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

(1)機器M1上的作業連續加工，即作業之間無空閑。

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

(4)若N2中仍有未加工的作業，則在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算法得到排序中，將作業集N1(N2)分為2個集合：N11,N12(N21,N22)。N22表示所有在J1,n1的完工時間之后開始加工的作業集合。N21表示在J1,n1的完工時間之前開始加工的作業集合。N11表示與N22中至少1個作業不沖突的作業集合。N12表示與N22中所有作業都沖突的作業集合。令P1,P2,P11,P12,P21,P22分別表示作業集N1,N2,N11,N12，N21,N22中所有作業的加工時間總和。則有：

(2)

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

(3)

接下來，分2種情況進行討論。

(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 作業沖突圖

假設機器M1和機器M2分別處理2個互不相交的作業集合，N1={J1,1,J1,2,J1,3}，N2={J2,1,J2,2,J2,3,J2,4,J2,5,J2,6}機器M1上作業的加工順序為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}，需要加工的作業用job來表示，每個作業的加工時間如表1所示，其沖突圖如圖2所示。

表1 作業加工時間

通過運行LPT算法得到的算法解如圖3所示，不難發現最優解如圖4所示。

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

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

3 結束語

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