張先超，周 泓

1.東南大學(xué) 信息科學(xué)與工程學(xué)院，南京 210096

2.北京航空航天大學(xué) 經(jīng)濟(jì)管理學(xué)院，北京 100191

生產(chǎn)調(diào)度是將有限的資源，如設(shè)備、場(chǎng)地、人員等，按時(shí)間分配給任務(wù)，使得一個(gè)或幾個(gè)目標(biāo)值達(dá)到最優(yōu)。由此可見(jiàn)，生產(chǎn)調(diào)度涉及到任務(wù)、資源和任務(wù)在資源上的處理時(shí)間等眾多因素。然而，實(shí)際生產(chǎn)過(guò)程中的很多因素是不確定的，經(jīng)常導(dǎo)致無(wú)法按照既定的初始調(diào)度方案實(shí)施生產(chǎn)，在生產(chǎn)過(guò)程中需要對(duì)初始調(diào)度方案進(jìn)行一定的調(diào)整，這對(duì)生產(chǎn)過(guò)程和生產(chǎn)結(jié)果都會(huì)產(chǎn)生一定的影響。在這種情況下，為了順利完成生產(chǎn)，確保生產(chǎn)結(jié)果，要求初始調(diào)度方案在一定限度的不確定因素?cái)_動(dòng)下，小幅調(diào)整即可實(shí)施，并能實(shí)現(xiàn)滿(mǎn)意的結(jié)果。將初始調(diào)度具有的這樣的性質(zhì)稱(chēng)為魯棒性，具有魯棒性的初始調(diào)度方案稱(chēng)為魯棒性初始調(diào)度方案?？梢允褂迷诓淮_定因素?cái)_動(dòng)下，實(shí)際調(diào)度目標(biāo)與能夠達(dá)到的最優(yōu)調(diào)度目標(biāo)的差距作為調(diào)度魯棒性的指標(biāo)，用以度量初始調(diào)度方案的魯棒性[1]。

在離散制造業(yè)中，流水車(chē)間（flow shop）是一種典型的作業(yè)模式，在生產(chǎn)制造的整個(gè)過(guò)程或關(guān)鍵部分環(huán)節(jié)被廣泛運(yùn)用。兩臺(tái)機(jī)器串行構(gòu)成的兩階段流水線(xiàn)是最為簡(jiǎn)單的流水車(chē)間結(jié)構(gòu)，其調(diào)度問(wèn)題的研究，在理論上是其他更為復(fù)雜的流水車(chē)間調(diào)度問(wèn)題研究的基礎(chǔ)，在實(shí)際生產(chǎn)中也有著廣泛的應(yīng)用，例如，汽車(chē)的某些沖壓件需要依次經(jīng)過(guò)整形和沖孔兩道工序。

加工時(shí)間不確定是制造過(guò)程中一種常見(jiàn)的影響調(diào)度方案實(shí)施的不確定因素，以往很多學(xué)者將不確定的加工時(shí)間作為隨機(jī)變量，求解期望調(diào)度目標(biāo)最優(yōu)的調(diào)度方案，稱(chēng)這樣的調(diào)度問(wèn)題為隨機(jī)調(diào)度，可以使用隨機(jī)優(yōu)化等多種方法予以解決[2-3]。然而，在很多情況下，加工時(shí)間未必服從某一確切的概率分布函數(shù)，即便如此，也難以獲得準(zhǔn)確的概率分布，此外，非常滿(mǎn)意的隨機(jī)調(diào)度方案在一次具體的生產(chǎn)過(guò)程中也可能導(dǎo)致較差的生產(chǎn)結(jié)果。因此，在加工時(shí)間不確定的環(huán)境下，隨機(jī)調(diào)度具有很大的局限性。相比隨機(jī)調(diào)度，魯棒調(diào)度不要求加工時(shí)間的準(zhǔn)確的分布函數(shù)，而且，求取的調(diào)度方案在任何可能的加工時(shí)間情景下都能獲得比較滿(mǎn)意的生產(chǎn)效果。

近年來(lái)，對(duì)于加工時(shí)間不確定的魯棒調(diào)度問(wèn)題，已經(jīng)有了一定的研究。文獻(xiàn)[4]給出了流水車(chē)間調(diào)度算法的魯棒性。文獻(xiàn)[5]研究了加工時(shí)間是離散情景，分布式流水生產(chǎn)魯棒調(diào)度問(wèn)題的局部搜索算法。文獻(xiàn)[6]研究了加工時(shí)間不確定的job-shop魯棒調(diào)度問(wèn)題，也是將加工時(shí)間描述為離散情景，運(yùn)用鄰域搜索，結(jié)合模擬退火和鄰域搜索求解。加工時(shí)間為離散情景在實(shí)際生產(chǎn)中并不常見(jiàn)，用區(qū)間數(shù)來(lái)表征實(shí)際生產(chǎn)中的加工時(shí)間更具有適用性。Liao等[7]研究了加工時(shí)間為區(qū)間數(shù)的置換流水車(chē)間Min-Max準(zhǔn)則魯棒調(diào)度問(wèn)題，并運(yùn)用遺傳算法求解該問(wèn)題。Levorato 等[8]研究了加工時(shí)間是區(qū)間分布，以工期為調(diào)度目標(biāo)的魯棒調(diào)度問(wèn)題，建立混合整數(shù)規(guī)劃模型，使用列和約束生成算法求解。Wu等[9]也是針對(duì)以工期為目標(biāo)的兩階段流水車(chē)間，研究了加工時(shí)間依賴(lài)具體情境的Min-Max魯棒調(diào)度問(wèn)題。相比工期，總完工時(shí)間在實(shí)際生產(chǎn)中有著更廣泛的意義，例如，總完工時(shí)間與庫(kù)存密切相關(guān)，減小總完工時(shí)間可以降低庫(kù)存，提高資金周轉(zhuǎn)率。進(jìn)一步來(lái)看，使用總完工時(shí)間作為調(diào)度目標(biāo)，對(duì)于生產(chǎn)以外的其他領(lǐng)域也同樣具有很好的適用價(jià)值。文獻(xiàn)[10]研究了針對(duì)云資源，以總完工時(shí)間為目標(biāo)的調(diào)度問(wèn)題。Sun等[11]研究了以總完工時(shí)間及其偏差的和為目標(biāo)的流水車(chē)間魯棒調(diào)度問(wèn)題，但其加工時(shí)間表征為離散情景。

流水車(chē)間魯棒調(diào)度問(wèn)題的求解往往具有很高的復(fù)雜性，降低計(jì)算復(fù)雜性也是研究的重點(diǎn)。Cwik等[12]針對(duì)加工時(shí)間為區(qū)間數(shù)的，以工期為調(diào)度目標(biāo)的流水車(chē)間魯棒調(diào)度問(wèn)題，通過(guò)兩次松弛來(lái)降低計(jì)算復(fù)雜度。利用調(diào)度解的占優(yōu)特點(diǎn)（dominance）是降低復(fù)雜性的常用手段。在不確定加工時(shí)間的環(huán)境下，很少存在對(duì)于任何加工時(shí)間情景都是最優(yōu)的調(diào)度解，但可能會(huì)存在任意加工時(shí)間情景下，某些調(diào)度解都會(huì)優(yōu)于另外的一些調(diào)度解，稱(chēng)這樣的調(diào)度解是占優(yōu)的。Allahverdi和Sotskov[13]證明了加工時(shí)間是隨機(jī)數(shù)或區(qū)間數(shù)的兩臺(tái)機(jī)器流水車(chē)間魯棒調(diào)度占優(yōu)解的充分條件。Matsveichuk和Sotskov等[14]求解了該魯棒調(diào)度問(wèn)題的占優(yōu)解集，對(duì)于某一特定的加工時(shí)間情景，占優(yōu)解集至少包含這種加工時(shí)間情景下的一個(gè)最優(yōu)調(diào)度解。Wu等[15]針對(duì)以總完工時(shí)間為目標(biāo)的兩階段流水車(chē)間調(diào)度問(wèn)題，給出了利用占優(yōu)條件的分支定界算法，以及CA、GSA 等啟發(fā)式算法。然而，占優(yōu)解集在實(shí)際應(yīng)用中有著很大的局限性，需要根據(jù)當(dāng)前的生產(chǎn)情況實(shí)時(shí)選擇調(diào)度方案，需要高效率的算法支持，且對(duì)實(shí)現(xiàn)的調(diào)度目標(biāo)沒(méi)有準(zhǔn)確的預(yù)期。

本文研究以總完工時(shí)間作為調(diào)度目標(biāo)，加工時(shí)間為區(qū)間數(shù)的兩階段流水生產(chǎn)魯棒調(diào)度問(wèn)題，使得在所有可能的加工時(shí)間情景下，調(diào)度目標(biāo)相對(duì)相應(yīng)的最優(yōu)調(diào)度目標(biāo)的最大偏差最小，即求解Min-Max準(zhǔn)則的魯棒調(diào)度解。

1 問(wèn)題描述與模型

1.1 魯棒調(diào)度的三元組形式

1.2 魯棒調(diào)度的三元組形式

由此，調(diào)度在所有加工時(shí)間情景下調(diào)度目標(biāo)相對(duì)最優(yōu)調(diào)度目標(biāo)的最大偏差為：

設(shè)調(diào)度σR滿(mǎn)足：

則調(diào)度σR為調(diào)度目標(biāo)最大偏差最小的調(diào)度方案，即Min-Max準(zhǔn)則的魯棒調(diào)度方案。

1.3 數(shù)學(xué)模型

為建立問(wèn)題的數(shù)學(xué)規(guī)劃模型，引入變量xjk和，規(guī)定如下：

式（4）給出了xjk(j,k=1,2,…,n)與調(diào)度σ的一一對(duì)應(yīng)關(guān)系。那么，在加工時(shí)間情景λ下，調(diào)度σ的第j個(gè)位置的工件σ(j)在兩臺(tái)機(jī)器上的加工時(shí)間為：

同理，根據(jù)式（5），得到：

根據(jù)式（7）和（8），在加工時(shí)間情景λ下，調(diào)度σ和最優(yōu)調(diào)度σλ中第j個(gè)位置的工件σ(j)和σλ(j)的完工時(shí)間分別為：

那么，調(diào)度σ和σλ的總完工時(shí)間為：

根據(jù)式（11）和（12），得到：

由此，式（3）轉(zhuǎn)換為以下的整數(shù)規(guī)劃模型：

在模型（14）中，約束（a）使得每個(gè)工件在調(diào)度σ中位于且僅位于一個(gè)位置，約束（b）是調(diào)度σ中每個(gè)位置有且僅有一個(gè)工件，約束（c）是式（6）對(duì)的求解，約束（d）表明xtk是0-1變量。

進(jìn)一步，式（14）改寫(xiě)為：

模型（15）中約束（b）到（e）同模型中約束（a）到（d），求解的τ即為最小最大調(diào)度目標(biāo)偏差。根據(jù)模型（15）的解{xtk|t,k=1,2,…,n} 形成的調(diào)度方案即為Min-Max準(zhǔn)則的魯棒調(diào)度σR。由于區(qū)間數(shù)加工時(shí)間的情景集合Λ是無(wú)窮集合，那么，模型（15）具有無(wú)窮約束，是半無(wú)限規(guī)劃模型。

2 簡(jiǎn)化性質(zhì)與占優(yōu)性質(zhì)

根據(jù)式（18），對(duì)式（13）進(jìn)行變換，得到：

根據(jù)式（19），式（2）給出的區(qū)間數(shù)加工時(shí)間環(huán)境下，調(diào)度σ的總完工時(shí)間最大偏差的求解如式（20）所示：

定理1（簡(jiǎn)化性質(zhì)）對(duì)于給定的調(diào)度σ，使得總完工時(shí)間偏差最大的情景一定是工件加工時(shí)間取其所在時(shí)間區(qū)間的極端值。

定理1 將區(qū)間數(shù)工件時(shí)間轉(zhuǎn)化為可列可數(shù)加工時(shí)間情景，使得模型（20）的約束個(gè)數(shù)有限化，模型得以簡(jiǎn)化，便于問(wèn)題的求解。

設(shè)b是B中的任意一個(gè)工件，b∈B，那么

設(shè)c是C中的任意一個(gè)工件，c∈C，容易得到：

根據(jù)式（22）、（24）、（26）和（27），得到：

定理2成立。

定理3（占優(yōu)性質(zhì)）對(duì)于已經(jīng)給出調(diào)度方案的工件集合σs，以及尚未調(diào)度的工件i和j，如果滿(mǎn)足以下條件：

則存在工件j不是工件集合σs的緊后工件的魯棒調(diào)度方案。

設(shè)調(diào)度σ={σsiAjB}，對(duì)于滿(mǎn)足給定條件的任意加工時(shí)間情景，都有：

又根據(jù)式（30）的給定條件，得到：

根據(jù)式（31），易得：

根據(jù)式（32）和（33），得到：

顯然

那么，根據(jù)式（29），得到：

又因?yàn)?/p>

根據(jù)式（35）、（36）和（37），得到：

根據(jù)式（32）、（34）、（36）和（38），得到：

定理3成立。

定理2 和定理3 給出了所求調(diào)度的占優(yōu)條件，用以縮小解空間，可以減小分支定界方法搜索的節(jié)點(diǎn)數(shù)目，從而降低求解難度。

3 分支定界-遺傳算法

在加工時(shí)間為區(qū)間數(shù)的環(huán)境下，Min-Max準(zhǔn)則魯棒調(diào)度解的搜索涉及到調(diào)度解和加工時(shí)間兩個(gè)空間。先對(duì)于給定的調(diào)度解，搜索總完工時(shí)間偏差最大的加工時(shí)間情景，再?gòu)恼{(diào)度解空間中搜索最大偏差最小的調(diào)度解，即魯棒調(diào)度解。遺傳算法具有很好的全局搜索性，具有廣泛的適用性[17-18]。本文將分支定界方法與遺傳算法結(jié)合起來(lái)，設(shè)計(jì)分支定界-遺傳混合算法（branch and bound-genetic algorithm，BB-GA），運(yùn)用遺傳算法搜索給定調(diào)度解的總完工時(shí)間偏差最大的加工時(shí)間情景，再運(yùn)用分支定界方法從解空間中獲得min-max 準(zhǔn)則的魯棒調(diào)度解，如圖1所示。

圖1 BB-GA算法框架Fig.1 Framework of BB-GA

根據(jù)定理1，求解給定調(diào)度解的總完工時(shí)間最大偏差的加工時(shí)間向量，只需要搜索各加工時(shí)間區(qū)間的端點(diǎn)值即可。因此，遺傳算法可采用0-1編碼，染色體長(zhǎng)度等于工件數(shù)量與機(jī)器臺(tái)數(shù)的乘積。采用這樣的方式解碼，染色體的各基因位依次對(duì)應(yīng)給定調(diào)度解的各加工時(shí)間，如果基因位是“0”，則相應(yīng)的工件加工時(shí)間取其區(qū)間下限，反之，基因位是“1”，則相應(yīng)的工件加工時(shí)間取其區(qū)間的上限，從而，染色體與加工時(shí)間向量一一對(duì)應(yīng)，實(shí)現(xiàn)了遺傳算法的編碼與解碼。

對(duì)于給定的調(diào)度解，遺傳算法的一條染色體對(duì)應(yīng)一種加工時(shí)間情景，那么，可以依據(jù)式求取該染色體對(duì)應(yīng)的總完工時(shí)間偏差，以此作為適應(yīng)度函數(shù)，進(jìn)行遺傳算法的種群選擇。從而，求取給定調(diào)度解的總完工時(shí)間最大偏差。

分支定界算法采用深度優(yōu)先策略，按照字典序依次搜索。對(duì)于搜索到的新的分支，如果部分序的下界小于已有的上界，或者不滿(mǎn)足定理2或定理3，則搜索下一個(gè)分支，否則，延長(zhǎng)部分序的長(zhǎng)度，計(jì)算其下界，并判斷對(duì)于定理2和定理3的滿(mǎn)足性。如果沿著一條路徑搜索到了最底層，也就是形成了完整的調(diào)度解，所有工件都已安排，驗(yàn)證其總完工時(shí)間最大偏差是否小于已有的上界，如果小于已有的上界，則替代形成新的上界，并記錄該調(diào)度解，否則，按照深度優(yōu)先策略搜索下一路徑。依此，直至搜索完全部路徑。

用MD表示總完工時(shí)間最大偏差的最小值，σ表示字典序的當(dāng)前序列，σ′表示字典序的下一個(gè)序列，σl表示σ中l(wèi)個(gè)工件的部分序，σ(l)是σ中第l個(gè)工件，表示σl的總完工時(shí)間最大偏差下界，σR是所求解的魯棒調(diào)度。

算法步驟如下：

輸入：n個(gè)工件在兩臺(tái)機(jī)器上的加工時(shí)間區(qū)間。

輸出：總完工時(shí)間最大偏差最小值MD，及魯棒調(diào)度σR。

步驟1設(shè)定σ={1,2,…},n,l=1,MD為足夠大的初始值。

步驟2根據(jù)遺傳算法（GA）求解,如果≤MD，σl滿(mǎn)足定理2 和定理3，且l ＜n，則l=l+1，返回步驟2；否則，如果＞MD，或σl不滿(mǎn)足定理2或定理3，轉(zhuǎn)到步驟3。

步驟3如果l=n，轉(zhuǎn)到步驟4；否則，如果σ(l)＜n，則σ=σ′,返回步驟2，如果σ(l)=n,則σ=σ′,l=l-1,返回步驟2。

步驟4如果＜MD,則=MD,σR=σl；如果σ(1)=n,σ(n)=1,算法結(jié)束，輸出最大偏差的最小值MD和魯棒調(diào)度σR,否則，σ=σ′,返回步驟2。

在圖1中，算法的效果由運(yùn)用遺傳算法求解給定調(diào)度解的完工時(shí)間最大偏差，以及運(yùn)用分支定界求解完工時(shí)間最大偏差最小的調(diào)度解兩部分決定，由于分支定界算法是確定性算法，能夠得到最優(yōu)解，因此，算法效果主要取決于前者。

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)設(shè)計(jì)

仿真實(shí)驗(yàn)硬件設(shè)備為配備Intel?CoreTMi9-11900K @3.5 GHz處理器的臺(tái)式計(jì)算機(jī)。

開(kāi)展兩類(lèi)實(shí)驗(yàn)，一是針對(duì)給定調(diào)度方案，驗(yàn)證遺傳算法求解其總完工時(shí)間最大偏差的優(yōu)越性；二是驗(yàn)證求解的初始魯棒性調(diào)度方案的魯棒性。

4.2 總完工時(shí)間最大偏差的實(shí)驗(yàn)分析

從每個(gè)問(wèn)題中隨機(jī)產(chǎn)生10個(gè)實(shí)例，在每個(gè)實(shí)例中，對(duì)工件按照生成的先后次序進(jìn)行排序，以按照生成次序排序的調(diào)度方案作為給定調(diào)度方案。針對(duì)每個(gè)問(wèn)題，對(duì)各實(shí)例分別運(yùn)用遺傳算法、模擬退火算法、禁忌搜索算法求解總完工時(shí)間最大偏差，以及隨機(jī)選取另外一個(gè)調(diào)度方案，求解其總完工時(shí)間偏差，然后求解10個(gè)實(shí)例總完工時(shí)間最大偏差的平均值。這幾類(lèi)算法在智能優(yōu)化中具有典型性。結(jié)果如圖2所示。

圖2 總完工時(shí)間偏差最大值仿真結(jié)果Fig.2 Maximum deviation of total completion time

從圖2 可以看出，對(duì)于給定調(diào)度方案，遺傳算法求解的總完工時(shí)間偏差最大值大于其他各類(lèi)算法，當(dāng)問(wèn)題規(guī)模增大時(shí)，優(yōu)勢(shì)更為明顯。

4.3 初始調(diào)度方案魯棒性的實(shí)驗(yàn)分析

（1）驗(yàn)證指標(biāo)

從每個(gè)問(wèn)題中隨機(jī)產(chǎn)生10 個(gè)實(shí)例，分別記錄和計(jì)算每個(gè)問(wèn)題的10 個(gè)實(shí)例中最優(yōu)期望調(diào)度（以期望加工時(shí)間作為調(diào)度目標(biāo)求解的調(diào)度方案）σE的總完工時(shí)間最大偏差與魯棒調(diào)度σR的總完工時(shí)間最大偏差的最大比值MaxDev(E/R)、平均比值MeanDev(E/R)和最小比值MinDev(E/R)，魯棒調(diào)度σR的期望總完工時(shí)間與最優(yōu)期望調(diào)度σE的期望總完工時(shí)間的最大比值MaxTc(R/E)、平均比值MeanTc(R/E)和最小比值MinTc(R/E)。各指標(biāo)如表2所示。

（2）實(shí)驗(yàn)結(jié)果

仿真實(shí)驗(yàn)結(jié)果如表3所示。

在表3 中，第（1）列是問(wèn)題編號(hào)，第（2）列是工件數(shù)目，第（3）和（4）列分別是α1和α2的均勻分布區(qū)間，第（5）到（10）列分別是表1給出的指標(biāo)。第（5）到第（10）列的各列中圓括弧標(biāo)出了各列的最小值，方括弧標(biāo)出了各列的最大值。

表1 實(shí)驗(yàn)問(wèn)題Table 1 Experimental questions

表2 計(jì)算實(shí)驗(yàn)比較指標(biāo)Table 2 Indices of computational experiments

表3 計(jì)算實(shí)驗(yàn)結(jié)果Table 3 Result of computational experiments

（3）實(shí)驗(yàn)分析

從表3 可以看出，在各組問(wèn)題中，最優(yōu)期望調(diào)度的總完工時(shí)間最大偏差都明顯大于魯棒調(diào)度，各組最大偏差比值的最大值高達(dá)2.458，最小值有1.484，各組平均偏差比值的最大值達(dá)到1.703，最小值為1.253，各組最小偏差比值的最大值有1.3，最小值也有1.042。從魯棒調(diào)度的期望調(diào)度目標(biāo)與期望調(diào)度的目標(biāo)比值來(lái)看，各組中最大比值的最大值只有1.114，平均比值的最大值僅有1.047，最小值為1.011，而各組最小比值的最大值僅為1.008，最小值則為1，也就是說(shuō)二者有著相同的期望總完工時(shí)間。

圖3 展示了實(shí)驗(yàn)結(jié)果，橫軸是問(wèn)題，縱軸是比值，6條折線(xiàn)分別是表1 中的6 個(gè)指標(biāo)。圖2 中，對(duì)于8 個(gè)問(wèn)題，指標(biāo)1、2和3明顯大于指標(biāo)4、5和6。而且，指標(biāo)4、5和6都接近于1。

圖3 實(shí)驗(yàn)分析Fig.3 Experiment analysis

表3和圖3充分表明：

（1）魯棒調(diào)度能夠有效克服加工時(shí)間的不確定性的擾動(dòng)，避免生成總完工時(shí)間偏差較大的調(diào)度方案；

（2）魯棒調(diào)度相比最優(yōu)期望調(diào)度的性能損失很小。

計(jì)算實(shí)驗(yàn)驗(yàn)證了本文的魯棒調(diào)度方法能夠生成總完工時(shí)間偏差較小，而性能損失較小的初始魯棒調(diào)度方案，能夠有效解決加工時(shí)間是區(qū)間數(shù)，以總完工時(shí)間為調(diào)度目標(biāo)的兩階段流水車(chē)間調(diào)度問(wèn)題。

5 結(jié)語(yǔ)

本文研究了以總完工時(shí)間作為調(diào)度目標(biāo)，加工時(shí)間為區(qū)間數(shù)的兩階段流水車(chē)間魯棒調(diào)度問(wèn)題，求解所有加工時(shí)間情景下，使得能夠獲得最優(yōu)調(diào)度目標(biāo)最大偏差最小的魯棒性初始調(diào)度方案，即Min-Max 準(zhǔn)則的魯棒調(diào)度。以總完工時(shí)間為調(diào)度目標(biāo)的調(diào)度問(wèn)題作為研究對(duì)象，更符合實(shí)際生產(chǎn)需要。建立了該類(lèi)魯棒調(diào)度問(wèn)題的半無(wú)限規(guī)劃模型，證明了問(wèn)題的一個(gè)簡(jiǎn)化定理和兩個(gè)占優(yōu)定理，簡(jiǎn)化定理將半無(wú)限規(guī)劃模型轉(zhuǎn)化為等價(jià)的有限約束的模型，占優(yōu)定理用以縮小解空間。建模與定理證明的理論價(jià)值顯著，對(duì)于類(lèi)似問(wèn)題的研究具有很好的借鑒意義。設(shè)計(jì)了求解的分支定界-遺傳算法，使用遺傳算法獲取給定調(diào)度解的完工時(shí)間最大偏差，分支定界算法搜索調(diào)度解，利用了遺傳算法的全局搜索性和分支定界的全局最優(yōu)性，混合算法效果良好。本文的研究對(duì)于生產(chǎn)以外的其他領(lǐng)域，還可以推廣應(yīng)用于供應(yīng)鏈、信息網(wǎng)絡(luò)等其他領(lǐng)域。