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

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

0 引言

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

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

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

1 文獻綜述

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

2 混合整數(shù)規(guī)劃模型

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

Y=充分大的正數(shù)。

單機雙代理調(diào)度問題整數(shù)規(guī)劃模型：

約束條件：

(1)

(2)

(3)

(4)

(5)

(6)

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

3 啟發(fā)式算法漸近分析

ADA啟發(fā)式：

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

證明請參見文獻[12]中關(guān)于算法1最優(yōu)性的證明過程。證畢

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

ZADA-ZPADA

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

(7)

ZOPT表示最優(yōu)目標值。

ZADA-ZOPT≤ZADA-ZPADA

(8)

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

(9)

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

4 分支定界算法

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

4.1 分支策略

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

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

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

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

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

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

4.2 有效下界

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

(10)

4.3 算法框架

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

(7)結(jié)束：算法終止，當前的上界對應(yīng)的序列就是最優(yōu)解。

5 計算結(jié)果

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

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

表1 分支定界實驗結(jié)果

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

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

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

表2 ADA啟發(fā)式漸近最優(yōu)性實驗結(jié)果(%)

6 結(jié)論

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

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