大規(guī)模柔性作業(yè)車間調(diào)度問題分解建模和求解方法

劉海濤，鄧停銘，唐健均，尹 慢

（1.航空工業(yè)成都飛機工業(yè)（集團）有限責任公司，四川 成都 610000；2.西南交通大學機械工程學院，四川 成都 610000）

1 引言

作業(yè)車間調(diào)度屬于NP 難題，半個多世紀以來一直是學術(shù)界的焦點。對于機床×工件=20×50 以內(nèi)的中小規(guī)模[1]調(diào)度問題，目前采用啟發(fā)式算法[2]可以獲取較好的結(jié)果；超出此規(guī)模，即當工件＞50，工件×機器＞1000 時[3]，便成為大規(guī)模作業(yè)車間調(diào)度問題，這種問題往往過于復雜，求解的時間會急速惡化[4]。對此進行了實驗，當規(guī)模達到4000 時，在MATLAB 環(huán)境下采用遺傳算法和一臺2.8GHz 處理器、8GB 內(nèi)存的計算機上尋優(yōu)，9h 后才獲得優(yōu)化近似解。

為解決這類問題，眾多學者采用了對問題進行分解的方法，按照一定的策略獲取子問題并分別求解，再根據(jù)各問題之間的關(guān)系重構(gòu)大規(guī)模調(diào)度問題的可行解。文獻[5]將滾動時域混合瓶頸及分解策略，利用時空兩個維度進行大規(guī)模調(diào)度問題的分解。文獻[6]將調(diào)度問題中約束和目標函數(shù)進行疊加處理后，大規(guī)模調(diào)度數(shù)學模型即轉(zhuǎn)變成若干個分解問題。文獻[7]將大鄰域搜索融合自適應隨機方法，并基于一定的規(guī)則策略來分解大規(guī)模柔性作業(yè)車間調(diào)度問題。文獻[8]根據(jù)工藝相似性進行動態(tài)相似度編碼，并改進編碼規(guī)則提高優(yōu)化求解效率。文獻[9]利用模擬退火搜索總拖延期最小的工序集分解方案，并采用粒子群算法求解各調(diào)度子問題，最后重組問題獲取總調(diào)度問題的可行解。文獻[10]提出根據(jù)交付期分解問題，并采用混合移動瓶頸、模擬退火和可變鄰域搜索方法求解大規(guī)模問題，求解精度較高，但是時間較長。

基于上述研究，提出一種簡單可行的按序組合工序集以進行大規(guī)模調(diào)度問題的分解方法，針對分解后的問題進行描述的基礎(chǔ)上建立大規(guī)模調(diào)度分解問題的數(shù)學模型，最后采用初始解生成策略、遺傳算法與蛙跳算法結(jié)合、雙線程等一系列改進算法和策略對問題進行求解，以高效高精度地得到最優(yōu)解。

2 基于工序組合分解大規(guī)模調(diào)度問題

2.1 工序按序隨機組合分解方法

對于某柔性作業(yè)，假設工件數(shù)為3，各工件加工工序數(shù)也為3，但可在不同的機床上完成工序加工，析取圖，如圖1 所示。圖中工件按照既定的順序加工，工序順序采用實線表示，Oi1、Oi2、Oi3是工件i 的第1、2、3 道工序。工序能夠于同一機床上加工用虛線連接起來，例如在機床1 上可以加工O11、O21、O32工序，在機床2 上可以加工O13、O22、O31工序，在機床3 上可以加工O12、O23、O33工序。原調(diào)度問題按照圖1 析取圖工序順序進行組合，如將工序O11、O12、O21、O22、O31組合形成階段1 子問題，同時將工序O13、O23、O32、O33組合形成階段2 子問題。其中先完成的工序所處階段不晚于后完成的工序所處階段，問題則被分解成了2 個子問題。

圖1 析取圖Fig.1 The Disjunctive Graph

2.2 基于雙段整數(shù)編碼遺傳算法的子問題分解

將最大完工時間作為優(yōu)化目標，采用GA 算法對子問題分解進行優(yōu)化，如圖2 所示。子問題分解采用整數(shù)編碼方式，圖1 中將原調(diào)度問題分解為2 個子問題，而圖2 是其編碼方式，2 段基因代表了2 個子調(diào)度問題的工序集，第一段為首個子問題包含的每個工件按序排列的工序數(shù)，第二段表示第2 個子問題包含的每個工件按序排列的工序數(shù)。同基因段中，每個基因位置號表示工件類別號，數(shù)字則代表著該工件在此子問題中按序排列的工序數(shù)。

圖2 分解整數(shù)編碼示意圖Fig.2 The Decompose Inter Coding Schematic

2.3 大規(guī)模柔性作業(yè)車間調(diào)度分解問題描述

2.4 大規(guī)模柔性作業(yè)車間調(diào)度分解問題數(shù)學模型

這里的數(shù)學模型建立在以下假設基礎(chǔ)上：各子問題中工件工序和機床在零時刻可用；同一時刻同一機床只加工一個工件；工件的某道工序只能在同一臺機床上加工；一旦工序開始加工直到完工才能被終止。

式中：［］—取整數(shù)；

（6）各問題包含的工序個數(shù)總和等于所有各類工件的工序個數(shù)之和：

3 改進遺傳算法

遺傳算法具有好的全局尋優(yōu)能力、魯棒性、操作簡單等特點，特別適應于典型的NP-Hard 諸如車間調(diào)度問題，一直是研究熱點。但是也存在受初始解集影響大、過早收斂陷入局部最優(yōu)解、計算效率低等缺陷，為此，提出一系列改進策略，以提高求解精度和求解效率。

3.1 改進策略

3.1.1 提高初始種群個體質(zhì)量和多樣化的策略

對于遺傳算法，初始解在空間分布越均勻，則越容易找找到最優(yōu)解。為了提高初始種群的質(zhì)量，并保證其多樣性，可利用不同的組合策略，產(chǎn)生一部分初始種群[11-12]，來提高解的搜索精度。按照以下4 種組合策略生成50%初始種群：（1）剩余最大工序數(shù)與工序最短加工時間的策略；（2）剩余最長加工時間與工序最短加工時間的策略；（3）全局最短處理時間與剩余最大工序數(shù)的策略；（4）全局最短時間與工件最長剩余加工時間的策略。種群初始化過程中，另外50%初始種群則隨機生成。

3.1.2 全局搜索能力的改進策略

遺傳交叉在實現(xiàn)的時候，比起蛙跳算法參數(shù)多、結(jié)構(gòu)復雜，但精度高。為了更快的實現(xiàn)交叉和個體更新，結(jié)合兩種算法的優(yōu)點，50%的個體用蛙跳局部搜索策略，以縮短遺傳算法計算時間，50%的個體仍然采用GA 雙點交叉策略。這種個體更新方式，在保證尋優(yōu)的精度的同時，提高了遺傳算法的運算效率。

混沌隨機數(shù)生成策略具有非線性系統(tǒng)的特征，與隨機亂數(shù)不同，是有界隨機數(shù)的一種生成方式，對初始情況存在高敏感性[13]。將混沌策略融入到算法的交叉過程中，使種群在混沌空間與穩(wěn)定空間交替過程中更易于跳出局部最優(yōu)解，有效地避免算法過早收斂，提高全局搜索能力。按照強混沌映射[14]，產(chǎn)生混沌隨機數(shù)，第t代混沌隨機數(shù)變量，如式（10）所示。

式中：K—系統(tǒng)分岔參數(shù)。

遺傳算法的雙點交叉方式，是在選擇的兩個染色體上，隨機選出兩段基因位置，并將交換這兩個基因片段，產(chǎn)生的兩個新個體一般會存在多余的基因以及部分缺失的基因，因此需要使基因合格化；蛙跳算法在局部更新時將50%的種群個體自動分成Y 個子群，每個子群內(nèi)有y 個個體，首先利用各個子群的最優(yōu)個體Pl 更新子群中的最差個體Pw，并形成新個體Pw′，如式（11）所示。

3.1.3 雙線程并行計算子問題

MATLAB 針對循環(huán)次數(shù)過多、數(shù)值陣列數(shù)據(jù)過大和消息傳遞過多等情況提供并行處理結(jié)構(gòu)，該結(jié)構(gòu)能處理數(shù)據(jù)實現(xiàn)并行算法。采用MATLAB 工具箱中Spmd 并行結(jié)構(gòu)進行多線程并行計算，以縮減大規(guī)模調(diào)度問題的求解時間。在計算的過程中，由于使用雙核計算機，可設置2 個線程進行子問題的并行運算。

3.2 改進遺傳算法流程及步驟

采用融合了初始解集產(chǎn)生策略、混沌策略、蛙跳算法的改進遺傳算法，其流程圖，如圖3 所示。首先設置初始參數(shù)，包括確定種群規(guī)模、子問題個數(shù)、子問題工序數(shù)、代溝、交叉率、變異率和最大迭代次數(shù)。其次采用兩層整數(shù)編碼方式，首層為工序排序基因?qū)樱竺嬉粚訛楣ば蜻x擇機床基因?qū)樱M行種群初始化。然后計算種群內(nèi)各個個體的適應度值選出全局最優(yōu)個體，判斷是否滿足終止條件，是則結(jié)束，否則采用輪盤賭的方式，從種群中選擇適應度較高的個體；采用雙點交叉和蛙跳算法結(jié)合的策略更新個體，當變異概率大于算法參數(shù)設置的變異算子時，機床基因發(fā)生變異，產(chǎn)生新種群，重新計算適應度并選擇個體。依次循環(huán)直到優(yōu)化過程達到終止條件時，得到最優(yōu)解。

圖3 基于蛙跳算法的改進遺傳算法流程圖Fig.3 The Improved Genetic Algorithm Flow Based on Leapfrog Algorithm

4 實例驗證

4.1 應用實例與實驗

針對某航空企業(yè)生產(chǎn)的不同典型管類零件進行實驗，每類管子加工工藝不同，但是工序數(shù)目都為8，工序加工時間和準備時間也不同。實驗時工件數(shù)×機床數(shù)×工序數(shù)分別為460×18×8、690×18×8、1150×18×8 等3 種大規(guī)模。為了進行對比分析，這里采用傳統(tǒng)調(diào)度方法即不分解問題直接進行優(yōu)化計算的方法、按照批次分解子問題以及提出的基于工序組合分解子問題的方法，分別進行了10 次計算，取其平均值作為對比依據(jù)。實驗后數(shù)據(jù)表，如

4.2 實驗數(shù)據(jù)對比分析

（1）收斂精度與收斂時間對比分析

根據(jù)圖4、圖5 及表1 可見，相對于傳統(tǒng)調(diào)度，提出的基于工序組合后再分解子問題的調(diào)度方法，在搜索到的優(yōu)化目標值最大完工時間方面以及運算時間方面都得到大幅度的降低，搜索精度比傳統(tǒng)算法提高25%以上，而收斂時間上縮短到僅為傳統(tǒng)算法的（3～4）%，大大提高了調(diào)度效率。當調(diào)度規(guī)模不斷增加，搜索時間和精度也不斷改善，說明提出的方法尋優(yōu)能力在超大規(guī)模中優(yōu)勢更加顯著。同時基于工序組合后分解子問題的調(diào)度方法比起一般的組批調(diào)度方法，在收斂精度至少提高11%以上，而在縮減計算時間上僅為組批調(diào)度的28%左右。

表1 基于工序組合分解調(diào)度與傳統(tǒng)調(diào)度方法對比表Tab.1 The Comparison Table Base on Process Combination Decomposition Scheduling and Traditional Scheduling Method

圖4 各種方法收斂精度對比圖Fig.4 The Comparison of Convergence Accuracy of Various Methods

圖5 各種方法收斂時間對比圖Fig.5 The Comparison Graph of Convergence Time of Various Methods

5 結(jié)論

針對大規(guī)模調(diào)度問題進行了研究，提出了一套基于工序再組合的大規(guī)模調(diào)度問題的分解、建模和求解方法。

（1）提出基于工序的再組合，將大規(guī)模問題分解成復雜度低的子問題可便于求解，并采用雙段整數(shù)編碼遺傳算法實現(xiàn)分解。

（2）提出各個子問題的最大完工時間最小為目標函數(shù)，分析各個子問題空間的約束條件，建立大規(guī)模調(diào)度分解問題的數(shù)學模型；

（3）采用蛙跳與遺傳算法相結(jié)合的改進算法，同時提出了組合規(guī)則下的初始種群產(chǎn)生方法、基于混沌數(shù)的更新策略、通過MATLAB 的Spmd 結(jié)構(gòu)實現(xiàn)該算法的雙線并行運算等系列改進策略，形成的改進求解算法。

通過實例顯示，提出的改進算法尋優(yōu)能力比起傳統(tǒng)調(diào)度算法提高了25%，同時在獲取更佳最優(yōu)解的基礎(chǔ)上，收斂速度提高25 倍以上，證明提出方法的可行性和顯著優(yōu)勢。