分布式估計算法在考慮差異工件的并行批處理機調度中的應用①

張 建

(中國科學技術大學 管理學院,合肥 230026)

引言

在工業生產中,集成電路芯片的制造包括生產、探測、裝配和測試環節[1-3].在測試過程中,需要將半導體芯片置于高溫烤箱中進行耐溫測試以檢測出潛在的風險.為了提高測試效率,芯片被分成不同的批次集中放在烤箱中處理.這里,半導體芯片就類似于工件,烤箱類似于機器.這是一個典型的批處理機調度的例子.

批調度問題不同于傳統的機器加工問題，一個批處理機能同時加工處理多個工件,從而有效提高資源的利用率.研究批調度問題,通過優化調度有效提高生產效率,降低生產成本,對于提高生產管理水平、獲取更高的經濟效益有著重要的現實意義[4].

人們對批調度問題的研究由來已久.Gimple 和Ikura[5]最先研究了工件尺寸相同、到達時間和交貨期相一致的單機批調度問題.Lee 和Uzsoy[6]提出了動態規劃的方法來解決此類調度問題,優化目標是最小化最大延遲時間和最小化延遲工件數,局限性在于這種基于動態規劃的精確求解方式需要較長的計算時間.Uzsoy[7]首次將工件尺寸相同的性質擴展到差異工件.在此基礎上,Zhou[8]融入了工件動態到達的限制,并結合距離矩陣提出了構造性啟發式算法,這些一次性啟發式算法在處理大規模工件問題時雖然在運行時間上占優,但解的質量并不太好.

在實際生活中,工廠往往采用多臺機器并行處理的方式來提高生產效率.Chang[9]、Damodaran 和Chang[10]等考察了并行批處理機調度問題,優化目標是最小化制造跨度.其中Chang 采用模擬退火算法,通過交換初始解中不同批中的工件生成鄰域解,這導致初始解的質量對最終解的質量有很大影響,從而影響算法的性能.Chen[11]在并行機基礎上納入了動態到達的約束,并結合蟻群算法和遺傳算法以及ERT-LPT 規則來優化完工時間,并且取得了不錯的效果.

元啟發式算法也被越來越多的學者應用到調度問題中.例如基于構建性的蟻群算法[12],基于鄰域搜索的模擬退火算法[3,9]和進化算法，其中進化算法包含但不限于遺傳算法[13]、粒子群算法[14]、差分進化算法[15]等.分布式估計算法作為一種較新的基于種群的進化算法,在求解組合優化問題方面具有良好的表現,比如置換流水車間問題[16],護士排班問題[17],但是在并行機調度方面的應用研究卻很有限.因此,本論文采用分布式估計算法求解考慮差異工件的并行批處理機調度問題.

論文組織如下：第1 章節為問題描述;第2 章節詳細介紹分布式估計算法在考慮差異工件的并行批處理機調度中的應用;第3 章節為仿真實驗;第4 章節為結論與展望.

1 問題描述

1.1 數學模型

論文考慮包含差異工件的并行批處理機調度問題,相關假設如下：

(1)將n個工件分配到m個批處理機加工;

(2)工件具有不同的尺寸和加工時間;

(3)各臺機器容量一致,工件j只需在其中一臺機器上加工,且它在所有機器上加工時間相同;

(4)工件集中分批,按照批次順序安排在機器上加工;

(5)批的尺寸等于批中所有工件尺寸之和,且不能超過機器容量限制,批的加工時間等于批中工件最大加工時間;

(6)一旦某個批次開始加工,加工過程不能中斷且不能有新的工件加入到當前批中;

(7)優化目標是makespan,也就是使最后離開加工系統的批次的完工時間最小;

該問題采用調度理論中的三元組法[18]可表示為Pm|batch,B,sj|Cmax,以下給出相關參數定義及混合整數規劃模型：

① 集合

工件集合：{j|j=1,2,3,···,n}

批集合：{b|b=1,2,3,···;b≤n}

機器集合：{k|k=1,2,3,···,m}

② 參數

sj：工件j尺寸;

pj：工件j加工時間;

B：機器容量;

③ 決策變量

PTbk：在機器k上加工的批b的加工時間;

CTbk：批b在機器k上的完工時間;

Cmax：最終完工時間;

xjbk：工件j分在批b中安排在機器k上加工時為1,否則為0;

數學模型如下：

式(1)為優化目標;式(2)保證一個工件只能分配在一個批中只能在一個機器上加工;式(3)保證批的容量不超過機器的容量限制;式(4)說明批的加工時間為批中最長加工時間;式(5)表明前后批完工時間之間的關系;式(6)為Cmax的計算方法;式(7)是對變量xjbk的取值約束.

1.2 問題下界

為了能更有效評估后續算法中解的質量,我們考慮這樣一個下界：假設存在某種單位工件ej具有單位尺寸單位工時,一個尺寸為sj、加工時間為pj的普通工件可表示為sj*pj個ej,此時問題轉化成若干個性質相同的單位工件的并行機調度問題.理想狀態下所有單位工件能完美分配到批中,即批中所有工件尺寸之和恰好等于批的容量,然后均勻分配到各臺機器上加工,可得：

顯然這樣計算得出的結果是一個有效的下界,其中批的利用率達到最高.

2 分布式估計算法在考慮差異工件的并行批處理機調度中的應用

2.1 分布式估計算法

分布式估計算法是一種基于概率模型的進化算法,最早于1996年由Mühlenbein,Bendisch[19]等人提出,是當前國際進化計算領域的研究熱點.根據變量之間的相關性,算法可分為三類：變量無關、雙變量相關和多變量相關;按照變量的類型可分為離散變量的分布式估計算法和連續域上的分布式估計算法.

分布式估計算法不同于經典的遺傳算法,它摒棄了遺傳算法中采用選擇、交叉、變異的方式生成子代種群的策略,轉而采用概率模型來更新下一代種群,通過收集統計全局信息,學習優勢個體特征來更新概率模型進行采樣,然后生成新的個體.該算法基本流程如圖1所示.

2.2 編碼與解碼

論文采用基于工件序列的編碼方式,每個工件有相應的序列編號,根據不同的排列可得到不同的調度方案.

圖1 EDA 基本流程圖

給定一個工件序列,首先我們采用FF (First-Fit)規則進行分批,然后根據LPT (Longerst Processing Time)方法選擇當前處于空閑狀態的機器進行調度.FF 規則如下：

步驟1：選擇工件序列中第一個工件加入到當前批中,若違反機器容量約束,考慮下一個工件;

步驟2：每當工件完成分批,則從序列中去除該工件;若當前批容量已滿或不能容納其它任何工件,則新建一個批;

步驟3：重復步驟1～2,直到所有工件完成分批;

分批完成后,按批次的加工時間由長到短重新排列,并根據此排列順序選擇非加工狀態的機器進行加工,若存在多臺非加工狀態的機器,則任選其中之一進行加工.

考慮10 個工件在兩臺機器上加工,假設各臺機器容量均為15,工件序列為[4,5,1,3,6,2,9,10,7,8],工件屬性及分批調度結果如圖2所示.

2.3 概率模型與更新機制

算法采用概率矩陣P來表征分布估計模型,Pij(t)表示第t代中工件i出現在位置j周圍的概率,這里用“周圍”是因為我們考慮了幾種不同的更新策略來計算工件i在位置j左右的概率，而不是僅僅在固定位置j上.

圖2 10 工件調度示意圖

算法初始階段所有概率值均設為1/n,以保證工件能被均勻抽樣.對于每一代種群,設種群規模為Q,我們根據個體的Cmax值計算適應度值(fitness),然后挑選最優SP_Size個個體估計其概率分布,通過對其學習來更新概率矩陣.這里的fitness及SP_Size計算如下：

其中,α為優勢個體選擇比例,0＜α＜1.

論文中采用FF-LPT 規則解碼,因此工件的位置對于批的形成有很大影響,相鄰位置的工件就越有可能分配到同一個批中.我們考慮4 種更新機制來完善概率矩陣,第一種更新機制學習優勢個體中當前位置工件的概率分布;第二種更新機制學習當前位置及其之前位置工件的概率分布;第三種更新機制與第二種相反,通過學習優勢個體中當前位置及其之后位置工件的概率分布;第四種更新機制考慮當前位置及其鄰域內工件的概率分布.具體更新方式如下：

其中,β為學習率,0＜β＜1;vj為單邊鄰域大小,例如當vj= 2 時,位置5 的鄰域為位置3,4,5,6,7,|v5|為5;位置1 的鄰域為位置1,2,3,|v1|為3.

為了闡明概率矩陣更新過程,我們用一個包含5 個工件的算例示范.假設挑選4 個優勢個體,如圖3所示.設vj為1,根據4 種更新機制統計各個位置的工件信息,構建優勢個體的概率分布矩陣,結果如圖4所示.通過學習優勢個體的概率分布特征來更新概率矩陣P,然后基于比例選擇采用輪盤賭的方式依次決定各個位置上工件編號,即可獲得新的個體.

圖3 挑選的4 個優勢個體

2.4 面向差異工件的并行批處理機調度問題的分布式估計算法

綜上,面向差異工件的并行批處理機調度問題的分布式估計算法如算法1 所示.

算法1.面向差異工件的并行批處理機調度問題的分布式估計算法初始化參數Q,α,β,gen(迭代次數),隨機生成初始種群;t= 0 ;Whilet＜gen采用FF-LPT 規則對種群中個體進行解碼,計算適應度值;根據適應度值選取最優的SP_Size個個體,并估計其概率分布;選取2.3 中的更新策略對概率矩陣進行更新;根據新的概率矩陣采樣生成新的種群;令t=t+1;end輸出最優調度方案及makespan.

3 實驗設計與結果分析

3.1 實驗設計

本實驗根據文獻[9]提出的方法生成隨機算例,算例規模按3 個標準劃分：工件數量n,工件尺寸s,加工時間p;其中s、p均服從離散均勻分布;機器數量m為2 或4,容量均為20.具體參數見表1.

每類算例提供一個編號.例如包含50 個工件,工件尺寸服從[1,10]分布,加工時間滿足[1,20],在兩臺機器上加工的一類算例編號為J2S3P2M1.每類算例隨機生成10 個子算例,每個算例計算10 次.

圖4 不同更新機制下優勢個體概率矩陣計算結果

表1 算例規模

影響EDA 性能的參數主要有4 個：Q,α,β,gen.其中,優勢個體的選擇比例α對概率矩陣的更新有很大影響,若比例選擇過小,子代種群與當代個體相似度較高,則容易陷入局部最優;若比例選擇過大,個體的優勢特征弱化,導致概率矩陣的學習效果差.為此,論文考慮3 種不同的α值進行預實驗.為了選取合適的參數值展開后續實驗,我們采用田口方法對不同水平的參數進行評估,將參數作為因子,并對每個因子設置3 水平的參考值,具體的參數設置見表2.

表2 參數設置

算法提供了4 種更新策略,為方便表述,依次記為EDA1,EDA2,EDA3,EDA4,其中EDA3 表示采取第三種更新策略.由于EDA4 中需要考慮單邊鄰域v,因此為EDA4 單獨設立5 因素3 水平的實驗,參數順序為Q,α,β,v,gen.v具有3 水平,分別是[2,3,5],其余因素同表2.

察爾汗鹽湖是我國最大可溶性鉀鎂鹽礦床。1958年，第一批鹽湖人深入戈壁荒漠，正式開啟我國鉀肥工業生產序幕。60年來，我國鉀肥工業從無到有、從小到大、從弱到強，形成了科研、設計、設備制造、施工安裝、生產、銷售、農化服務等一套完整工業體系，產品市場競爭力不斷增強，鉀肥生產技術和單套生產能力均達國際領先水平。

根據實驗參數和因子水平，選取正交陣列L9(34)和L27(35),其中L9(34)表示針對3 因素4 水平的問題設計9 種實驗.我們針對50 規模的工件,生成12(3×2×2)個算例,每個算例采取9 次試驗,算5 次,一共計算12×9×5 次;對于EDA4,需要計算12×27×5 次.最后的平均響應變量值(ARV)計算方式如下：

其中,n為算例個數.顯然,ARV 越小越好.

圖5中各子圖橫坐標為因子水平值,縱坐標為ARV,分析可知,EDA1 最優參數組合為：Q=60,α=0.2,β=0.1,gen=500;EDA2 最優組合為：Q=60,α=0.1,β=0.1,gen=500;EDA3 最優組合為：Q=50,α=0.1,β=0.3,gen=500;EDA4 最優組合為：Q=60,α=0.1,β=0.3,ν=2,gen=500.

3.2 實驗結果及分析

為了評估算法的性能,我們將和文獻[9]提出的模擬退火算法(SA)以及經典的遺傳算法(GA)作對比.SA 中各項參數與原文獻一致,GA 中種群規模和迭代次數同EDA 一樣,變異概率設為0.1.所有的算法均由Matlab 實現,實驗環境為4 核3.4 GHz、8 GB RAM 的Windows10 系統.

表3、表4分別給出了2 臺和4 臺機器環境下所有算例的結果.實驗中分別統計了各個算法運行得到的最優值、平均值、最差值及運行時間等,這里只給出了比值ratio，計算公式為：

ratio越小,說明結果越接近下界,所得到的解越接近最優解.

圖5 不同更新機制下EDA 的因子水平趨勢

從表3、表4中可以看出,對于絕大部分算例,我們提出的4 種EDA 得到的解均是要優于SA 算法的.對于2 臺機器,EDA1 的ratio均值為1.24,GA 為1.27,SA 為1.44.隨著工件規模的增加,算法的解的質量也越來越好,尤其是在較多并行機的情況下.

值得注意的是,4 種EDA 算法中,EDA1 的性能是最好的,其次是EDA2,EDA3 的性能最差.EDA2 與EDA3 的更新機制是截然相反的,EDA3 考慮當前位置及其之后位置工件的概率,但是由于采樣時我們是按照順位比例選擇的方式依次決定各個位置的工件,這導致EDA3 效率較低.而EDA1 只考慮當前位置的工件的概率分布,使得概率分布極為“精純”,所以性能較好.

另外,GA 的性能比想象中好很多,對于小規模算例,GA 的解甚至比EDA1 還要占優;但對于大規模工件,EDA1 得到的解的質量要優于GA.

表3 M1 類算例結果

表4 M2 類算例結果

運行時間方面,4 種EDA 均是要長于GA、SA 的.這是由于EDA 生成下一代種群需要反復對概率矩陣采樣生成新的個體,這一過程相對于SA 中鄰域搜索或GA 中交叉、變異要繁雜很多，因此造成時間上的冗余.

圖6給出了J2S2P1M1 類典型算例的收斂趨勢圖.從中可以看出EDA1 的收斂性更好.其他類算例的收斂趨勢與此類似.

圖6 J2S2P1M1 類典型算例收斂趨勢圖

4 結論與展望

本文研究了分布式估計算法在考慮差異工件的并行批處理機調度中的應用問題.首先提出了一個混合整數規劃模型和一個下界,然后采用FF-LPT 規則實現對工件的分批和排序;對于基于概率矩陣的分布式估算法,提出了4 種不同的更新機制,并通過仿真實驗和SA、GA 對比,驗證了算法的有效性.經比較知,對于采取不同更新機制的EDA,EDA1 的性能最好,EDA2 次之,EDA3 性能最差.

未來的研究可考慮通過局部優化來進一步優化算法的性能,以及考慮多階段并行機調度問題或不同的優化目標等.