分支定界算法求解帶有釋放時間的單機雙代理調度問題

梁建恒, 薛含鈺, 白丹宇, 苗蘊慧

(1.沈陽化工大學 經濟與管理學院，遼寧 沈陽 110142; 2.大連海事大學 航運經濟與管理學院，遼寧 大連 116026)

0 引言

本文研究帶有釋放時間的單機雙代理調度問題，其中來自兩個不同代理的工件需要在同一臺機器上加工，目標是求得一個可行調度，使得兩個代理的最大完工時間之和極小化。與經典的調度模型不同，雙代理調度模型從客戶的角度考慮優化目標。例如，富士康工廠同時為蘋果和三星兩家公司代工組裝不同型號的手機，為了使兩個公司各自制定的目標都盡可能最優化，采用雙代理調度模型安排生產是最好的方案之一。

考慮到該問題具有NP困難性，即在多項式時間內無法求得問題的最優解，因此采用近似與精確算法分別求解不同規模問題。針對大規模問題，提出了優勢代理優先啟發式算法并證明了其漸近最優性。針對小規模問題，提出了分支定界算法進行最優求解。為了提高算法性能，加快求解速度，設計了基于釋放時間的分支策略和基于可中斷的問題下界。隨機數值測試驗證了分支定界算法的有效性。

本文的其余部分組織如下：第一節為文獻綜述，簡要介紹相關研究結果，第二節建立了整數規劃模型，第三節分析了啟發式算法的漸近最優性，第四節介紹了分支定界算法，第五節為數值實驗結果，最后得出本文結論。

1 文獻綜述

為了方便起見，本文采用由Graham等[1]提出的三參數表示法描述調度問題。最初，Agnetis等[2]在生產調度模型中引入了多代理模式。據作者所知，目前多代理調度問題按照機器類型分類主要有三種形式：單機多代理，并行機多代理及流水車間多代理。本文主要針對單機多代理調度問題進行綜述。

2 混合整數規劃模型

Nx={1,2,…,nx}，代理x∈{a,b}。

Y=充分大的正數。

單機雙代理調度問題整數規劃模型：

約束條件：

(1)

(2)

(3)

(4)

(5)

(6)

約束(1)和(2)確保每個工件在給定排序中具有唯一性。約束(3)保證工件滿足設定的加工要求。約束(4)是工件加工順序的約束，排在后面的工件都必須等排在前面的工件完工才能開始加工。約束(5)限制加工先后順序和每個相鄰工件的連續關系。約束(6)設定0-1變量和非負限制。

3 啟發式算法漸近分析

ADA啟發式：

將兩個代理中的工件分別采用先到先加工規則進行排序，選擇其中目標函數值較小的代理作為優勢代理。一旦機器出現空閑時，在所有可用工件中優先選擇優勢代理中的工件進行加工。若無工件可用，則保持機器空閑直至有工件釋放。

證明請參見文獻[12]中關于算法1最優性的證明過程。證畢

定理1對于帶有釋放時間的單機雙代理極小化最大完工時間和問題的實例，有

ZADA-ZPADA

證明對于給定的序列，其中最后完工代理的目標值與序列無關，因此優勢代理會引起可中斷與不可中斷排序之間的差異。顯然，干擾工件必定是非優勢代理中最后中斷的工件。令a代理為優先代理，將干擾工件表示為jb，那么

(7)

ZOPT表示最優目標值。

ZADA-ZOPT≤ZADA-ZPADA

(8)

根據定理1，得出(8)式中最后一個不等號成立。將不等式兩端同時除以n并取極限，有

(9)

整理(9)可得定理結論。證畢

4 分支定界算法

分支定界算法是一種基于枚舉思想的優化算法，通過系統搜索解空間求得最優解。分支定界算法的性能主要取決于其分支策略和下界的效果，用以剪掉更多的分支節點加快計算速度。通常分支定界算法包括深度優先和廣度優先搜索方法。本文主要采用深度優先搜索來尋找搜索樹上的有效節點。根節點?在第0層上表示一個空集合，剩余的每個節點位于τ層部分序列為π(τ)=([1]，[2]，…，[τ])，工件[j]在機器上第j個位置加工，1≤j≤τ，1≤τ≤n。下面分別給出有效的分支策略、下界和算法框架。

4.1 分支策略

顯然，如果人為延遲可用工件的開始加工時間，則會引起可行解的目標函數值惡化。基于此思想，可以得到以下性質。

性質1假設已經排好了j-1個工件的加工順序，接下來準備加工工件jx。若存在工件qx滿足

則剩下的工件會被延遲加工且目標函數值將會變大，式中N′表示未排序工件的集合，1≤j≤n，x∈{a,b}。

證明顯然，工件qx可以在工件jx之前加工而不延遲工件jx的開始加工時間。否則N′中工件的開始加工時間會被延遲，目標函數值會變大。證畢

證明(i)的結論可直接由先到先加工規則求解1|rj|Cmax問題的最優性求得。(ii)可通過工件交換得出結論。證畢

因此，結合性質1和2可以給出分支定界算法的分支策略，即：若j-1工件已經排在搜索樹中的j-1層，當且僅當滿足分支規則時，工件jx∈N被刪除。在分支的過程中，該規則可以有效地刪除多個節點，并顯著降低計算量。

4.2 有效下界

在分支定界算法中，剪支的多少主要取決于下界的有效性。若某節點的下界不小于當前最好上界，則剪掉該節點，節省運行時間。設計下界是分支定界算法的核心。下面介紹下界的計算規則。

(10)

4.3 算法框架

(1)初始化：設置變量的初始值，節點層次τ=0，未排工件集合N′=N，分支節點集合G0=?，加工序列π=?。按照ADA啟發式計算初始上界ZUB。

(7)結束：算法終止，當前的上界對應的序列就是最優解。

5 計算結果

本文通過一系列數值仿真驗證所提出算法的性能。算法采用C語言編寫，Visual Studion 2010 編譯。實驗使用的電腦配置為：Intel(R)Core(TM)i5- 4590(3.3GHz)CPU，4.00GB內存，460GB硬盤，操作系統為Windows 7(64位)旗艦版。每次實驗中，工件的加工時間與釋放時間分別通過離散均勻分布[1,10]與[0,5n]隨機生成，其中需要保證至少有一個工件的釋放時間為0。

分支定界算法是基于枚舉的搜索方法，只適用于求解小規模問題。本文測試的問題規模分別為15,20,25,30個工件，每種問題規模下進行5次獨立實驗，共20組實驗。為了說明分支定界算法的優良性能，對于同一問題實例，分別采用分支定界算法和CPLEX軟件進行求解，記錄各自的運行時間和最優值。若半小時(1800s)內無法求得最優解，則輸出當前最好解進行比較，實驗結果詳見表1。

表1 分支定界實驗結果

表1中的數據分別為分支定界算法和CPLEX求得的(當前)最優值和CPU時間。實驗結果表明分支定界算法能夠在0.1秒內最優求解50%的實例，CPU時間范圍是[0.003,82.462]秒。另一方面，CPLEX能夠在[1,5]秒內最優求解15%的實例，CPU時間范圍是[1.4125,21.5892]秒。顯然，CPLEX的求解時間明顯長于分支定界算法所花費的時間。除此之外，對于75%的問題實例，CPLEX求得的目標函數值遠遠大于分支定界算法的計算結果。以上結果充分表明了分支定界算法的優越性。

為了驗證ADA啟發式的漸近最優性，本文將測試的問題規模設定為500, 1000, 1500, 2000個工件，每種問題規模下進行10次獨立實驗，記錄每次實驗求得的目標值間隙OGP=(目標函數值-下界值)/下界值×100%，并將平均值記錄在表2中。

通過表2中的數據，可以看出隨著工件數增加，OGP值越來越接近零，即啟發式算法的目標值與問題下界之間的間隙越來越小。由此，能夠斷定ADA啟發式具有漸近最優性。

表2 ADA啟發式漸近最優性實驗結果(%)

6 結論

本文研究了用分支定界算法求解帶有釋放時間的單機雙代理調度問題。針對大規模問題，提出了ADA啟發式算法進行近似求解，并證明了漸近最優性。針對小規模問題，設計了分支定界算法進行最優求解，其中基于釋放時間的分支規則和基于加工中斷的下界有效地減少了實際運算量，從而加快了求解速度。

在未來的研究中，針對分支定界算法，將給出更有效的剪支規則進一步縮小搜索空間范圍。此外，嘗試結合有效的改進策略，利用智能優化算法求解中等規模問題，獲得高質量的滿意解。