帶有資源沖突的Seru 在線并行調度算法

江煜舟 李冬妮 靳洪博 殷 勇

隨著大規模定制發展的趨勢,傳統的生產系統,如流水線(Flow line)、豐田生產系統(Toyota production system,TPS)、作業車間(Job shop)、單元制造系統(Cellular manufacturing system,CMS)等,難以適應對動態不確定市場的快速響應需求,賽如生產系統(Seruproduction system,SPS)應運而生[1-3].

Yin 等[4]的研究展示了傳統生產系統轉化為SPS的重要性,Liu 等[5-6]的研究也表明SPS 具有傳統生產系統難以企及的先進性和發展前景[7].自二十世紀九十年代起,SPS 已經逐漸被亞洲的眾多電子企業采用,如三星、佳能、LG、索尼、松下、富士通、NEC、富士康等[8-10].

Seru代指SPS 下的最小生產單元,脫胎自基于精益(Lean)思想[11]的裝配流水線,一個Seru通常是生產一種或多種產品的裝配單元,包含若干設備和工人.

一個SPS 至少包含一個Seru.SPS 中的每一個Seru都能夠頻繁地在短時間內被重構,這給SPS 帶來了極大的靈活性.可以快速頻繁地建立、改變、拆除和轉化,以響應頻繁波動的市場需求[9-10].

SPS 運作管理的基本原則為面向 “組織”的準時生產原則(Just-in-time organisation system,JIT-OS),是TPS 傳統的面向 “物料”的準時生產原則(Just-in-time material system,JIT-MS)的延伸.JIT-MS 指在合適的時間地點投入合適的物料,強調的是物料.而JIT-OS 強調的是組織,對應到SPS,即在合適的時間地點構建合適的Seru.這讓SPS 可以通過調整生產組織結構快速獲得相應的生產能力,為重構的實施提供了有效的載體和途徑[1].

SPS 的運作可以被劃分為Seru構建與Seru調度兩個部分,Seru構建指如何依據訂單任務對人員進行分配與組合,Seru調度指如何在有限的空間下安排各個Seru的構建順序及時間,目前相關研究大都側重于Seru構建.如Liu 等提出的解決工人分配問題的三段式啟發模型[12]、Yu 等提出的以產品流通時間和總勞動時間為目標的一種非支配排序遺傳算法[13]、Yu 等結合局部搜索算法提出的第二代非支配排序遺傳算法[14]、吳旭輝等聯合Seru構建與訂單分配提出的一種協同進化算法[7]、賈凌云等[15]與田云娜等[16]對跨單元調度問題的研究等.

目前對Seru調度這一方面的研究相對較少,難以充分體現SPS 調整結構的動態性,但要想充分發揮出SPS 的靈活性,快速響應 “小批量,多品種”市場的動態變化,在提高Seru構建效率之外,還需要考慮結構上的變化,即Seru調度.如何在有限的位置上安排Seru的構建順序及時間也是SPS 運作管理基本原則JIT-OS 的一項重要內容.

據此,本文對Seru在線并行調度問題展開了研究,該問題具體是指,將隨時間動態構建的n個Seru安排到有限的m個位置上,以總加權完工時間最小為目標,在線決策各Seru的構建順序及時間.同時,考慮到具體的生產環境,為了增強算法的實用性,本文還將對帶有資源沖突的Seru在線并行調度問題進行討論.

本文接下來的內容安排如下:第1 節,給出具體的問題模型;第2 節,給出AD-SWPT 算法優化后得到的具有良好常數競爭比的在線算法;第3 節,給出帶有資源沖突的Seru在線并行調度算法,并計算特殊實例下算法的競爭比;第4 節,設計相關實驗,展示實驗結果,分析實驗數據;第5 節為結論部分.

1 問題描述與分析

本文所研究的帶有資源沖突的Seru在線并行調度問題是指,如何在有限個Seru的可用位置上在線安排多個帶有資源沖突的Seru,以提高生產效率,具體描述如下:

有一系列的訂單任務隨著時間發布,每一個訂單任務對應一個Seru,Seru間可能存在資源沖突,在無優先級的情況下,將它們安排到m個Seru的可用位置上進行處理,存在資源沖突的兩個Seru不能同時被處理,每一個Seru都對應一個訂單任務發布時間rj,一個處理時間pj和一個權重wj,所有關于Seru的信息在訂單任務發布前都是未知的.同樣,Seru的總數量也無法提前得知.

在線算法的優劣通常用它的競爭比ρ來評價(對任意實例,算法的目標函數值都不大于ρ倍的最優離線目標值).

問題的基本假設如下:

1)車間中有m個Seru的可用位置,共有n個訂單任務會發布(m與n均為正整數);

2)所有發布的訂單任務都可以被完成,不考慮由工人技術或車間規模限制而導致的拒單;

3)一個訂單任務只能在一個Seru中完成,不考慮拆分;

4)一個Seru的可用位置同一時間段最多安排一個Seru;

5)一旦Seru構建完成,被安排到某一空的可用位置上,在結束任務前Seru的位置不會發生改變,任務進程不會被打斷;

6)不考慮由工具損壞或自然災害等不可控因素導致的生產中斷;

7)車間24 小時運轉不停工.

問題描述所需的符號變量如下:

t表示當前時間;

m表示Seru的可用位置數目;

j為Seru的序號索引 (j=1,2,3,···) ;

k為車間內Seru可用位置的序號索引 (k=1,2,3,···) ;

rj表示Seru對應的訂單任務發布時間(rj≥0);

pj表示Seru的處理時間(pj＞0);

wj表示Seru的權重(wj≥0);

Sj表示Seru的構建時間(Sj≥rj);

Cj表示Seru的完工時間(Cj=Sj+pj).

決策變量:

目標量總加權完工時間的表示為:

根據實際生產中的問題特性和約束,本文的約束條件描述如下:

其中,式(1)表示訂單任務發布之前,一切信息未知,無法構建相應Seru;式(2)表示任意時刻工廠內最多容納m個Seru運作;式(3)表示任意時刻同一位置上最多容納一個Seru運作;式(4) 表示Seru一旦構建,將會持續運作至完成訂單任務,中途不會被打斷.

目前尚無專門針對有資源沖突的Seru在線并行調度問題的相關研究,考慮類似的并行機調度問題構建.Seru的空間位置對應到并行機,將Seru安排在相應的位置上.并行機調度問題的跨領域應用在控制系統的故障診斷中也有體現[17-18].

對并行機調度問題,Anderson和Potts 率先提出了單機器下競爭比為2 的最優確定性在線算法,最小加權處理時間(Shortest weighted processing time,SWPT)算法[19].多機器下,Hall 等設計了一個競爭比為(4+ε)的算法[20],其中ε為任意小的正數.Megow和Schulz 將競爭比改進為3.28[21].Correa和Wagner 又提出了競爭比為2.618 的無優先級α調度(Non-preemptiveαscheduling,NAS)算法[22].Sitters 設計了 O NLINE(ε) 算法[23],并證明其競爭比不大于在并行機數量較少時該算法遠優于NAS 算法,但在并行機數量增大時NAS 算法的競爭比趨近1.79,優于 O NLINE(ε) 算法.隨機化被允許時,可以得到更好的算法,這里不再贅述[22,24-25].

通過推廣Megow和Schulz 設計的單機器下的算法[21],Tao 提出一個以總加權完工時間最小為目標的并行機在線調度算法,即平均延遲最短加權處理時間(Average delayed shortest weighted processing time,AD-SWPT) 算法,算法競爭比為(2.5-1/(2m))[26].對AD-SWPT 進行改進,Tao 等提出一個競爭比為4m) 的算法[27],是目前文獻中以總加權完工時間最小為目標的并行機在線調度算法中競爭比最小的一個.但無論是AD-SWPT 算法還是其改進算法,所得到的競爭比都不是一個常數,后者還極為復雜.

先基于AD-SWPT 算法及其改進算法得到一個競爭比為常數的算法,有利于將原本針對于并行機調度問題的算法應用于SPS,以及在無資源沖突的Seru在線并行調度算法上添加沖突機制后對算法性能展開數學上的理論分析.

非常數的競爭比會讓對帶有資源沖突的Seru在線并行調度算法競爭比的計算變得更加復雜,甚至難以推進.同時,一個具有常數競爭比的算法也能為本領域及并行機調度等相關領域的后續研究提供更加便捷與直觀的參照.

因此,本文針對Seru在線并行調度問題,首先考慮無資源沖突的情況,對AD-SWPT 算法競爭比不為常數的局限性,設計α

AD-SWPT 算法,采用實例歸約的方法來計算競爭比,得到一個具有良好常數競爭比的算法,再在αAD-SWPT 算法的基礎上,針對帶有資源沖突的Seru在線并行調度問題,將問題轉化為計算具有特殊結構實例的競爭比,可以得到某些特殊情況下的優化算法.

2 α AD-SWPT 在線算法

2.1 AD-SWPT 算法簡介

AD-SWPT 算法.對并行機的在線調度問題,一旦出現空機器和一些可以被安排的任務時,在所有已生成但未安排的任務中,選擇處理時間與權重比值pj/wj(后文中用加權處理時間來代指這個比值)最小的一個.當出現相等的情況時,選擇處理時間較小的.記被選擇的任務為Ji,計算時刻t所有機器上正在運作的任務的剩余處理時間總和.這個值根據表1 中的符號可以被寫作.那么如果

表1 基本符號說明Table 1 Basic symbolic explanation

就在t時刻將Ji安排在空機器上;否則,等下一個時刻重復以上整個過程.

對一般情況下AD-SWPT 算法的競爭比,有:

定理1[26].對以總加權完工時間為目標量的無優先級并行機在線調度問題,AD-SWPT 算法的競爭比區間為 [2,2.5-1/(2m)].

定理1 的證明采用了實例歸約,該思想在對兩個半在線單調度問題的分析中被首次提出[28-29].在證明中發現,AD-SWPT 算法可以被進一步優化.

2.2 α AD-SWPT 算法簡介

AD-SWPT 算法的競爭比(2.5-1/(2m))不為常數,而其優化算法的競爭比4m),雖然在數值上略有減小,卻更為復雜.于是,本文在AD-SWPT 算法的基礎上,設計了一種競爭比為常數的調度算法.記為αAD-SWPT (α-average delayed shortest weighted processing time)算法.

在式(5)右側添加調節參數α(當α=1 時,優化算法退化為AD-SWPT 算法,m→∞時,新發布的任務無需等待可立即被安排,可以認為α＞1[27]),將t變為αt,同時將并行機的調度問題,對應到Seru的調度問題上,如圖1 所示.AD-SWPT 算法變化如下:

圖1 AD-SWPT 與 α AD-SWPT 算法流程圖Fig.1 The flow charts of AD-SWPT and α AD-SWPT

α AD-SWPT 算法.一旦出現空位置和一些可以被構建的Seru時,在所有對應訂單任務已發布但未構建的Seru中選擇加權處理時間pj/wj最小的一個.當出現相等的情況時,選擇處理時間較小的.記被選擇的Seru為Ji,計算時刻t所有位置上正在處理的Seru的剩余處理時間總和.這個值根據表1 中的符號可以被寫作.那么如果

就在t時刻將Ji安排在空位置上;否則,等下一個時刻重復以上整個過程.

2.3 α AD-SWPT 算法競爭比的計算

盡管競爭比是指在所有可能的實例中所能達到的最壞性能比,但窮舉搜索是不可能的,因為集合所包含的實例數目是無窮的.

性能比與競爭比的概念類似,在接下來的證明過程中,為了不至于造成誤解,將非一般實例集合下的競爭比稱為性能比.

αAD-SWPT 算法競爭比的計算方法與ADSWPT 算法同源[26],同樣采用實例歸約.

實例歸約的思路是在實例空間中找出最壞的情況,證明部分實例的競爭比不小于其他實例,從而縮小搜索空間,在更小的集合內對算法的性能比進行分析.這些更小集合里的實例擁有的特殊性質,可以使對性能比計算的分析更加深入.

本文中,最壞的情況可能從兩類實例集中得到.可以推測,這兩類實例性能比的表達式中含有調節參數α.

2.3.1 相關定義與性質

αAD-SWPT 算法中由于存在延遲機制,所以在一些位置上會出現空余的時間段.

為了方便敘述,參考AD-SWPT 算法競爭比計算中的定義[26]:

稱一個位置在時刻t為 “閑置”,如果這個位置在時間段 (t-ε,t+ε) 閑置;稱一個位置在時刻t為 “運作”,如果這個位置在時間段 (t-ε,t+ε) 不閑置,其中ε為無窮小的正數.

稱時刻t是一個位置的 “運作起點”(記為SPoint),如果這個位置在時間段 (t-ε,t) 閑置,在時間段 (t,t+ε) 不閑置;稱時刻t是 一個位置的“運作終點”(記為EPoint),如果這個位置在時間段(t-ε,t) 不閑置,在時間段 (t,t+ε) 閑置.

根據Tao 在論文中的描述,可以證明,最壞情況下的實例在αAD-SWPT 算法下產生的調度方案中,所有位置最早的SPoint和最晚的EPoint 之間,不存在時刻t,滿足所有位置都在時刻t閑置[26].

記滿足上述性質的實例為I1.

σ(I1) 中的Seru按照構建時間排列,記作J1,J2,···,Jn.以隊列內Seru的加權處理時間非減為原則,可將Seru分割為若干個子隊列,每個子隊列最后一個Seru的加權處理時間大于下一個子隊列第一個Seru的加權處理時間,如圖2 所示.

圖2 按照 α AD-SWPT 安排方案的構建時間示意圖Fig.2 Processing sub-queues in terms of starting time in the α AD-SWPT schedule

2.3.2 實例歸約

首先引入一個重要引理[28],這個引理會在接下來的分析中被反復使用.

引理1.f(x)和g(x) 是定義在區間 [u,v] 上的兩個正值函數,且f(x) 為凸函 數,g(x) 為凹函 數.f(x)/g(x) 的最大值在區間端點處取到,即:

證 明.?x ∈[u,v],?a∈[0,1],s.t.x=au+(1-a)v.又f(x) 為凸函數,g(x) 為凹函數,那么有:

f(x)≤af(u)+(1-a)f(v)

g(x)≥ag(u)+(1-a)g(v)

又f(x)和g(x) 是定義在區間[u,v] 上的兩個正值函數,那么有:

可以證明,在區間的某個端點開放時引理也成立,此時f(x)/g(x) 的上確界存在于相對應的端點處.□

按照Tao 的處理方式,將I1在性能比不減的情況下,化歸為兩類特殊實例,它們在αAD-SWPT 算法下生成的安排方案具有更多簡單特殊的子隊列結構.

第一類,實例中的Seru擁有相同的加權處理時間,記作I2;第二類,實例中部分Seru的權重趨近于無窮大,記作I3.

記為一個過渡實例,它在αAD-SWPT 算法下生成的安排方案滿足最后一個子隊列中所有Seru具有相同的加權處理時間.

直接引用Tao 在論文中給出的定理,有:

表2 無沖突時的特殊實例符號說明Table 2 Symbolic explanation of four special instances without conflicts

引理2[26].對任意實例I1,都能通過修改I1中Seru的權重來找到一個過渡實例,使得:

引理3[26].對任意實例,都能通過修改中Seru的權重來構建一個實例I2或I3,使得:

2.3.3 競爭比的計算

引理4.在αAD-SWPT 算法下,對于特殊實例I2,有:

證明.參考Tao 在計算AD-SWPT 算法下競爭比時的推理過程[26],在不影響性能比大小的情況下,對I2中所有的Seru進行標準化.

記σ(I2) 中最后一個SPoint 為rL,在rL之后,每一個位置上Seru都被連續安排,不存在有位置空閑的時間段.下面分為兩種情況討論:

1) 在σ(I2) 中不存在對應訂單任務先于rL發布,但于rL或之后構建的Seru.將σ(I2) 中于rL或之后構建的Seru,按照構建時間的順序排列,記為J1,J2,···,Jn,剩余Seru構成的過渡實例記為.

2)在σ(I2) 中存在至少一個Seru,對應訂單任務于rL之前發布,但于rL或之后構建,記為Jk.

將σ(I2) 中于rL或之后完成的Seru,按照構建時間的順序排列,記為J1,J2,···,Jn,剩余Seru構成的過渡實例記為.

將{J1,J2,···,Jn}分為如下兩個集合:

引理5.在αAD-SWPT 算法下,對于特殊實例I3,有:

圖3 f (α) 與 g (α) 的圖像Fig.3 Graphs of f (α) and g(α)

證明.參考Tao 在計算AD-SWPT 算法下競爭比時的推理過程[26],將σ(I3) 中最后一個子隊列中所有Seru的集合記為Q∞,將Q∞中最早發布的訂單任務的發布時間記為rf,將σ(I3) 中最后一個SPoint 記為rL.下面分為三種情況討論:

1)rL≤rf.

將Q∞中的Seru按照構建時間的順序排列,記為J1,J2,···,Jn.記.可以得到σ(I3) 的一個上界以及 π (I3) 的一個下界:

其中 O (1) 表示一個有限的數值.

當δ→+∞時,顯然有:

2)rL＞rf,且σ(I3) 中所有于rL時刻運作的Seru全部屬于Q∞.剔除I3中的某些Seru,可以得到rL不是最后一個SPoint 的過渡實例,進而有:

3)rL＞rf,且σ(I3) 中 于rL時 刻運作的Seru中至少存在一個不屬于Q∞.下面再分為兩種情況討論:

a) 在σ(I3) 中,Q∞中不存在對應訂單任務于rL之前發布,但構建于rL或之后的Seru.這種情況下,所有對應訂單任務于rL或之后發布的Seru也于rL或之后構建.從I3中剔除這些Seru之后可以得到一個過渡實例.

b) 在σ(I3) 中,Q∞中至少存在一個對應訂單任務于rL之前發布,且構建于rL或之后的Seru.

將σ(I3) 中,于rL時刻運作,但不屬于Q∞的Seru組成的集合記為Q′.根據αAD-SWPT 算法,這些Seru一定于rf之前構建.

將Q∞中于rL之后完成的Seru分為如下兩個集合:

同引理4 的證明,可以得到:

從而有如下定理:

引理2.對無資源沖突的Seru在線并行調度問題,αAD-SWPT 算法的最優競爭比在α=(1+時取得,為

圖4 給出了AD-SWPT 算法、AD-SWPT 的改進算法以及αAD-SWPT 算法的競爭比對比圖,可以看出與AD-SWPT 算法比較,雖然Seru的可用位置數目m=1,2 時,αAD-SWPT 算法競爭比偏大,但是到m＞2 時,AD-SWPT 算法的競爭比不斷增大,競爭比恒為常數的αAD-SWPT 算法的性能明顯更優.

圖4 三個算法的競爭比Fig.4 Graphs of each algorithm＇ competitive ratio

而αAD-SWPT 算法的競爭比雖略大于A DSWPT 的改進算法,不具有競爭比上的絕對優勢,但隨著m的增大,二者之間的細微差距在不斷縮小,直至可以忽略不計.對此,后文會通過計算機模擬實驗在有資源沖突的情況下進行驗證.

3 存在資源沖突時的特殊情況

3.1 特殊情況的介紹

若有兩個Seru由于人力資源或物力資源上的沖突,不能同時被安排,就稱這兩個Seru是具有資源沖突的.記本文所設計的帶有資源沖突情況下的調度算法為αAD-I (α-average delayed shortest weighted processing time-improved)算法.

α AD-I 算法.一旦出現空位置和一些可以被安排的Seru時,在所有對應訂單任務已發布但未構建的Seru中選擇加權處理時間pj/wj最小的一個.當出現相等的情況時,選擇處理時間較小的.記被選擇的Seru為Ji,計算時刻t所有位置上正在處理的Seru的剩余處理時間總和.這個值根據表1中的符號可以被寫作.那么如果

并且Ji與正在運作的Seru間無資源沖突,就在t時刻將Ji安排在空位置上;否則,等下一個時刻重復以上整個過程.

沿用實例歸約的方法,對有資源沖突的Seru在線并行調度問題展開討論,對具有特殊結構的實例進行競爭比的計算.

將αAD-I 算法構建的Seru中具有資源沖突的Seru記為沖突集合F.若存在這樣的實例,F中先構建的Seru Jv與后構建的Seru Jk完工時間的比值滿足pv/pk≤(1+1/m)/2,則記這樣的實例為I*.

圖5 α AD-I 算法流程圖Fig.5 The flow chart of α AD-I

3.2 α AD-I 算法競爭比的計算

顯然,對于I*,第2.3.2 節和第2.3.3 節中的分析都是適用的.那么有如下引理:

引理6.對任意實例I*,都可以通過將I*中部分Seru提出,以及修改權重來構建出一個實例或,使得:

引理7.在αAD-I 算法下,對于特殊實例,有:

證明.σ() 中,同引理4 的證明,在不影響性能比大小的情況下,對中所有的Seru進行標準化,考慮σ(I2) 中最后的一個SPoint,記為rL.也就是說,在rL之后,每一個位置上Seru都被連續安排,不存在有位置空閑的時間段.

引理4 的證明分為了兩種情況討論,顯然,情況1)下的證明不會發生改變.

而對情況2),對于對應訂單任務在rL之前發布,但構建于rL或之后的所有Seru,若存在一個Seru使得式(6)不成立,證明過程不會發生改變;若對其中的任意Seru,式(6)均成立,根據αAD-I算法,有:

在該類子情況下,存在一個Seru,記為Jk,對應訂單任務于rL之前發布,但構建于rL或之后,Jk∈F.將F中于rL時刻運作的Seru記為Jv,則pv/pk≤(1+1/m)/2 .

將于rL或之后構建的Seru,按構建時間順序排列,記為J1,J2,···,Jn.

將{J1,J2,···,Jn}{Jk}視作一 個單獨的實例,且將其中所有Seru的對應的訂單任務發布時間放縮到rL.同引理4 情況1)的證明,可以給出π() 的一個下界:

又rk＞rL-pv,因為加權處理時間相同時會選擇處理時間較小的Seru來安排,那么根據式(7)、式(8),有不等式如本頁下方所示.

再結合 (pk+A)/(αm)≤rL,以 及pv/pk≤(1+1/m)/2 .最終有:

引理8.在αAD-I 算法下,對于特殊實例,有:

證明.σ() 中,最后一個子隊列所有Seru的權重趨近于無窮,同引理5 的證明,將σ() 中最后一個子隊列中所有Seru的集合記為Q∞,將Q∞中所有Seru間最早的訂單任務發布時間記為rf,將σ() 中最后一個SPoint 記為rL.

引理8 的證明分為了三種情況討論:

1)rL≤rf,證明同引理5 情況1).可得:

2)rL＞rf,且σ() 中于rL時刻運作的Seru全部屬于Q∞,證明同引理7,從剔除掉一部分Seru后可得到rL不為最后一個SPoint 的過度實例.可得:

表3 有沖突時的特殊實例符號說明Table 3 Symbolic explanation of four special instances with conflicts

3)rL＞rf,且σ(I3) 中于rL時刻運作的Seru中至少存在一個不屬于Q∞,再分為兩種情況:

a) 在σ(I3) 中,Q∞中不存在對應訂單任務于rL之前發布,但構建于rL或之后的Seru.且所有于rL或之后構建的Seru所對應的訂單任務也于rL或之后發布,從I3中剔除這些Seru得到過渡實例,證明同引理5 情況3) a).可得:

4 實驗與分析

4.1 特殊實例 I* 下 α AD-I 算法的性能檢測

本節對特殊實例I*下αAD-I 算法的性能進行檢測,在NAS 算法[22]以及 O NLINE(ε) 算法[23]中加入與αAD-I 算法相同的沖突處理機制,通過計算機實驗比較I*下三個算法的性能.

參考Savelsbergh 等[30]以及Gu[31]在論文中采用的方法構建測試用例.對于不屬于沖突集合F的Seru,訂單任務發布時間按照參數為λ的泊松分布隨機生成,λ為單位時間內平均發布的訂單任務個數.對應低、平均、高三種不同的負載,將λ分別取為0.5、1.0和3.0;Seru的處理時間和權重從[1,100]中隨機生成.

對于屬于沖突集合F的Seru,訂單任務發布時間和權重從[1,100]中隨機生成,處理時間按照I*的定義生成,先構建Seru與后構建Seru完工時間的比值不大于 (1+1/m)/2 .

再考慮位置數目m,不屬于F的Seru數目n1,以及屬于F的Seru數目n2之間的不同組合.

取m∈{2,5,10,20,50},

n1∈{m,2m,4m,50,100,200},

n2∈{2,3,4,5},

λ ∈{0.5,1.0,3.0},

且n1≥n2,則共有312 種不同的組合,每一種負載下有104 種組合.

按照上述規則,每組隨機生成1 000 個測試用例,定義Seru的處理時間除以m后單機器下最優算法SWPT[19]的目標值為模擬最優解,計算αADI 算法、添加沖突處理機制后的NAS 以及 ONLINE(ε)算法下的目標值與相應模擬最優解的比值,稱其平均值為模擬競爭比.

結果如圖6 所示,縱坐標為模擬競爭比,橫坐標是不同的組合,按m、n1、n2的主次排序依據升序排列.

圖6 α AD-I 算法在特殊實例 I* 下的實驗結果Fig.6 The experimental results of α AD-I in I*

從圖6 中可以看出,對不同的負載,均有特殊實例I*下αAD-I 算法的性能明顯優于添加沖突機制后的NAS 算法以及 O NLINE(ε) 算法.且在m相同時,模擬競爭比隨著n1、n2的增大而減小,算法性能與n1、n2呈正相關.

除此之外,橫向對比,相同負載及相同n1、n2下,m增大到一定程度時,再繼續增大,模擬競爭比不增反減,算法性能反而提高;縱向對比,相同m、n1、n2下,負載增大,模擬競爭比減小,算法性能提高.實驗結果說明在特殊實例I*下,算法對大規模定制的市場環境具有良好的適應性,能夠體現SPS的靈活性.

4.2 一般實例下 α AD-I 算法的性能檢測

本節對一般實例下αAD-I 算法的性能進行檢測,同樣與添加沖突機制后的NAS 算法以及 ONLINE(ε)算法進行比較.

測試用例的生成與上小節類似,唯一的區別在于,對屬于沖突集合F的Seru,處理時間從[1,100]中隨機生成.同樣對312 種不同的組合分別隨機生成1 000 個測試用例,計算不同算法在每種組合下的模擬競爭比.

從圖7 中可以看出,在一般實例下αAD-I 算法的性能也優于添加沖突機制后的NAS 算法以及ONLINE(ε) 算法.且具有和特殊實例I*下相似的實驗結果.m相同時,算法性能與n1、n2呈正相關.橫向對比,m增大到一定程度再繼續增大,算法性能反而提高;縱向對比,負載增大,算法性能提高.實驗結果同樣說明在市場需求大幅度波動的情況下,算法具有良好的適應性,能夠體現SPS 的靈活性.

圖7 α AD-I 算法在一般實例下的實驗結果Fig.7 The experimental results of α AD-I in general instances

4.3 特殊實例 I* 與一般實例下的實驗結果對比

在分別對特殊實例I*以及一般實例下αAD-I算法的性能進行檢測后,再將兩種情況進行對比.

圖8 中展示了特殊實例I*與一般實例下αADI 算法模擬競爭比的對比,可以看出,相同負載下,在Seru的可用位置數目m相同時,隨著n1、n2的增大,一般實例下的模擬競爭比與特殊實例I*之間的差距不斷縮小直至可以忽略.且隨著負載的增大,這種趨勢的進程在不斷加快.實驗結果從一定程度上驗證了,在大規模定制的市場環境中,一般實例下的αAD-I 算法同特殊實例I*下一樣具有良好的性能.

圖8 α AD-I 算法在I*與一般實例下實驗結果對比Fig.8 The comparision between α AD-I in I* and α AD-I in general instances

4.4 一般實例下 α AD-I 算法與AD-SWPT 改進算法的實驗結果對比

根據第2.3.3 節的討論,可知具有常數競爭比的αAD-SWPT 算法對比AD-SWPT 的改進算法不具有競爭比數值上的絕對優勢,但是隨著m的增大,二者競爭比間本就細微的差距在不斷減小,因此在大規模定制的市場環境下這種微乎其微的差距可以忽略不計.

本節在一般實例下,對基于αAD-SWPT 算法的αAD-I 算法與添加沖突機制后的AD-SWPT 的改進算法進行計算機模擬實驗,測試用例的生成同第4.2 節.

從圖9 中可以看出,相同負載下,在m相同時,隨著n1與n2的增大,αAD-I 算法的模擬競爭比較之添加沖突機制后的AD-SWPT 的改進算法,呈現從略大于到最后幾乎相等的趨勢,中間甚至有αAD-I 算法更加優越的情況出現.且隨著負載和m的增大,這種趨勢的進程在不斷加快.λ=1,m=50 時,以及λ=3,m=20,50 時,兩個算法的模擬競爭比曲線幾乎完全重合.

圖9 α AD-I 算法與AD-SWPT 改進算法在一般實例下的實驗結果對比Fig.9 The comparision between α AD-I and improved AD-SWPT in general instances

實驗結果表明,在大規模定制的市場環境下可以忽略αAD-SWPT 算法在競爭比數值上的細微差距.為了推進算法競爭比的計算,在添加沖突機制時,選用具有常數競爭比的αAD-SWPT 算法是合理的.

5 結論

本文針對帶有資源沖突的Seru在線并行調度問題,以總加權完工時間最小為目標,決策Seru的構建順序及時間.先基于并行機在線調度問題的AD-SWPT 算法,針對無資源沖突的情況,采用實例歸約的方法,引入調節參數α,得到競爭比為常數的αAD-SWPT 算法.

再針對有資源沖突的情況,基于αAD-SWPT算法添加沖突處理機制,得到帶有資源沖突的Seru在線并行調度算法,即αAD-I 算法.沿用實例歸約的方法,在特殊實例I*下可證明其競爭比同αADSWPT 算法,也為常數.

最后通過計算機模擬實驗對αAD-I 算法的性能進行檢測,對比添加沖突機制后的NAS 算法與ONLINE(ε) 算法,αAD-I 算法在特殊實例I*與一般實例下均具有更好的性能.且在市場需求大幅度波動的情況下,算法具有良好的適應性,能夠發揮SPS 靈活的特點.且有,在大規模定制的市場環境中,一般實例與特殊實例I*下的αAD-I 算法均具有良好的性能.