帶沖突約束的兩臺(tái)專(zhuān)用機(jī)器調(diào)度問(wèn)題

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

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

0 引 言

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

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

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

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

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

(1)

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

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

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

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

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

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

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個(gè)集合：N11,N12(N21,N22)。N22表示所有在J1,n1的完工時(shí)間之后開(kāi)始加工的作業(yè)集合。N21表示在J1,n1的完工時(shí)間之前開(kāi)始加工的作業(yè)集合。N11表示與N22中至少1個(gè)作業(yè)不沖突的作業(yè)集合。N12表示與N22中所有作業(yè)都沖突的作業(yè)集合。令P1,P2,P11,P12,P21,P22分別表示作業(yè)集N1,N2,N11,N12，N21,N22中所有作業(yè)的加工時(shí)間總和。則有：

(2)

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

(3)

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

(2)若

P11>2/3P1

(4)

接下來(lái)證明

(5)

(6)

所以有：

(7)

又因?yàn)椋?/p>

(8)

所以有：

p2,j2>δj1

(9)

(10)

又由式(8)可知：

(11)

所以有：

(12)

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

P21>1/3P1

(13)

令δ=δ1+δ2+…+δn1，因?yàn)?/p>

P21+δ=P1

(14)

所以有：

δ<2/3P1

(15)

則有：

(16)

2 算法緊例

圖2 作業(yè)沖突圖

假設(shè)機(jī)器M1和機(jī)器M2分別處理2個(gè)互不相交的作業(yè)集合，N1={J1,1,J1,2,J1,3}，N2={J2,1,J2,2,J2,3,J2,4,J2,5,J2,6}機(jī)器M1上作業(yè)的加工順序?yàn)镴1,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來(lái)表示，每個(gè)作業(yè)的加工時(shí)間如表1所示，其沖突圖如圖2所示。

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

通過(guò)運(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é)束語(yǔ)

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