梁建恒, 薛含鈺, 白丹宇, 苗蘊(yùn)慧

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

0 引言

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

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

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

1 文獻(xiàn)綜述

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

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

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

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

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

約束條件：

(1)

(2)

(3)

(4)

(5)

(6)

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

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

ADA啟發(fā)式：

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

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

定理1對(duì)于帶有釋放時(shí)間的單機(jī)雙代理極小化最大完工時(shí)間和問(wèn)題的實(shí)例，有

ZADA-ZPADA

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

(7)

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

ZADA-ZOPT≤ZADA-ZPADA

(8)

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

(9)

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

4 分支定界算法

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

4.1 分支策略

顯然，如果人為延遲可用工件的開(kāi)始加工時(shí)間，則會(huì)引起可行解的目標(biāo)函數(shù)值惡化?；诖怂枷耄梢缘玫揭韵滦再|(zhì)。

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

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

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

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

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

4.2 有效下界

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

(10)

4.3 算法框架

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

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

5 計(jì)算結(jié)果

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

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

表1 分支定界實(shí)驗(yàn)結(jié)果

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

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

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

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

6 結(jié)論

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

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