基于頭腦風暴算法的多處理機組合生產批量調度問題

王全武，徐震浩，顧幸生

（華東理工大學能源化工過程智能制造教育部重點實驗室，上海 200237）

批量調度問題是指將大批量的工件分成若干個子批進行生產，以獲得較短的生產時間。這類優化問題由Reiter 等[1-2]提出并廣泛應用，以提高生產效率。Huang 等[3]構建了多目標等子批作業車間調度問題的模型，并提出了一種混合蟻群優化算法進行求解。Andrzej 等[4]針對二階段柔性作業車間問題，建立了二階段柔性作業車間分批調度模型。Juan[5]針對柔性作業車間環境下的批量分割和批量調度問題，提出了一種新穎的約束編程方法，可以兼顧批次分割和工件調度，適用于多種生產系統。

多處理機組合生產問題是指工件在每個生產階段需要多臺機器同時協同加工。Drozdowski 等[6]對多處理機任務的調度問題進行了闡述，并進行了分類分析和研究。Jiang 等[7]對多目標分布式混合流水車間組合生產批量調度問題進行了研究。Chen 等[8]對該類問題進行了擴展，針對每道工序，引入了柔性加工機器集，得到最優的機器組合和生產順序。呂媛媛等[9]提出了一種改進的多目標粒子群算法，引入了外部種群尋優機制，解決了多處理機任務的車間調度問題。Liu 等[10]以求解最小化完工時間為目標，研究了帶有子模塊懲罰的多處理機調度問題，并提出了基于Lovasz 擴展的近似算法。Moghaddam 等[11]提出了一種新型免疫遺傳算法以及一種新型的編碼機制。

頭 腦 風 暴 優 化 算 法（Brain Storm Optimization Algorithm，BSO）是由Shi[12]提出的一種新穎的啟發式算法。曹國剛等[13]將頭腦風暴算法與單純性搜索法相結合提出了一種新的配準方法，有效地提高了醫學配準精度，同時縮短了配準時間。李怡敏等[14]將密集聚類算法與頭腦風暴優化算法相結合，在綜合考慮航跡長度和威脅環境的條件下，實現低空范圍內的航線規劃。李捷等[15]引入隨機分組策略和群縱橫交叉機制，加強了算法的收斂性，同時避免過早陷入局部最優。

到目前為止，已有許多學者對多處理機組合調度問題進行了研究，但是針對作業車間環境下多處理機任務組合的批量調度問題的研究成果較少。因此，本文針對作業車間環境下考慮機器的準備時間的問題，提出了基于機器負荷的可變分批方式，建立了作業車間的可變分批調度模型，并提出了改進的頭腦風暴優化算法。

1 問題描述和數學模型

1.1 問題描述

多處理機組合生產的作業車間批量調度問題(Multiprocessor Combined Batch Scheduling Problem,MCBSP)是經典的作業車間批量調度問題的拓展。n種類型的工件，每種類型的工件有w個，每個階段的加工過程需要同時占用多臺處理機，一臺處理機在某一時刻只能進行具有同批次任務的加工，且該批次的任務一旦開始，就不允許中斷。只有整個子批都完成加工，才可以進行下一道工序的加工。針對以上問題，建立作業車間組合生產的非混排批量調度模型，使系統的最大流程時間最小。該問題需要滿足如下假設：

（1）不考慮機器故障，機器在零時刻準備就緒；

（2）同一臺機器的某一時刻只能加工一種類型的工件；

（3）同一批次內只能包含一種類型的工件；

（4）同一批次的工件一旦開始不得中斷，且工序間不允許搶占加工；

（5）每種類型的工件的工藝路線固定；

（6）不考慮工件在不同機器上加工的運輸時間。

1.2 數學模型

1.2.1 下標定義

1.2.2 參數定義

1.2.3 決策變量

1.2.4 調度目標與約束條件

任意一種工件的總數量都等于它任意一道工序所分的每一個子批所包含的工件數量之和，即

每個子批所包含的工件數，由該工序的所有機器的負荷最小值、以及剩余未加工工件數量共同決定：

工序j第p個子批中的最后一個工件所對應的上一道工序的批次號s受限于上一道工序已經加工的工件數量和：

工件i第j道工序的第p個子批的開始加工時間，根據工件與機器的特性，存在以下4 種情況：

（1）當j> 1,時p=，1 工件 第ij道工序第一個子批的開始加工時間取決于機器集中的各臺機器的釋放時間和第j? 1道 工序上第s個子批完工時間的最大值。

2 具有貪婪思想的頭腦風暴優化算法

2.1 BSO 算法

BSO 算法是一種全局優化的啟發式算法，靈感來自于人類的頭腦風暴過程，其中心思想是聚集一群具有不同背景的人進行頭腦風暴，通過思想交流、觀點融合來共同解決問題。每一次迭代過程類似于一次頭腦風暴的過程，個體相當于是問題的解決方案。

2.2 BSO 算法的改進

基本BSO 算法存在著一些弊端，由于新想法的產生都是以原有的想法為線索，所以最優解的質量比較依賴于初始種群。為了提高初始種群的質量，在初始種群的產生過程中引入了貪婪思想。貪婪思想是受迭代貪婪算法的啟發，尋找在插入工件加工序列中，時間增加最小的點作為插入點插入指定工件，直到所有工件的所有工序都考慮到。在分類方面，每次頭腦風暴過程結束后，需要對個體進行評估，保證各組長是種群中最優秀的個體，每個組長按照能力來決定各自小組組員的數量，組員被隨機分配到各小組中。在種群更新方面，為了解決基本BSO算法的弊端，引入動態組內組間討論機制，組間討論可以找到局部最優解，組內討論則整合局部最優解，找出全局最優解。圖1 示出了具有貪婪思想的頭腦風暴優化算法（BrainStormOptimizationAlgorithm withGreedyThought,BSOGT）的流程圖。

圖1 BSOGT 算法流程圖Fig.1 FlowchartofBSOGT

2.2.1 逆序POX 交叉重組操作 交叉操作是指兩個父代個體經過迭代更新后使得染色體基因發生了互換，產生兩個新個體的過程。張超勇等[16]描述了基本POX 交叉重組操作的規則，并基于改進POX 交叉操作的遺傳算法解決了經典的作業車間調度問題。交叉操作可以產生盡可能多的新個體，提高算法的搜索能力。本文在基本POX 交叉操作的基礎上增加了染色體逆序的操作，提出了逆序POX 交叉重組操作（ReversePrecedenceOperationCrossover，RPOX），操作步驟如圖2 所示。圖中數字分別表示工件和工序的編碼，編碼長度與每種工件的工序數量有關，是所有工件所需要的加工工序數量之和。其中，編碼序列中的數字代表每種類型工件的編號，出現的次數代表著該類型工件的工序編號。

圖2 逆序交叉重組操作Fig.2 Reverseprecedenceoperationcrossover

2.2.2 環 變 異 操 作 環 變 異 操 作（Ring Mutation Operation,RMO）是將個體圍成一個環，保證每個基因作為變異起點的概率相等。該操作清除了傳統的變異方式所產生的變異盲區，加強了個體中首尾基因的聯系，增加產生優質個體的概率。環變異操作示意圖如圖3 所示。操作步驟如下：

圖3 環變異操作Fig.3 Ringmutationoperation

（1）將待變異的染色體的首尾相接連成一個環；

（3）將劣環進行逆序操作，并且將其首尾相接連成一個環，即逆序劣環；

（4）在優環中，隨機選擇一個點作為變異基因的插入點，并且隨機在逆序劣環上選擇一個點將其拆開；

（5）將拆開的逆序劣環插入到優環中去，形成一個新的個體。

2.2.3 生成初始種群的方法（IEG） 針對初始種群的生成采用半隨機生成、半引入貪婪思想的方式，取前半部分基因作為隨機生成的基因，對后半部分基因引入貪婪思想，一次插入到可能的位置中，取插入該基因后生產周期增加的最小的點作為基因最后的插入點，直到完成所有工件的調度。

2.2.5 組間討論 組間討論的次數隨著進化代數的增加而減小，如式（13）所示：

其中：Ntex為當前組間討論次數；Nmi為算法的最多迭代次數；Nci為當前算法迭代次數。

組間討論有3 種個體更新的方式：

（1）組長革命（LeaderRevolution，LR）。隨機生成一條染色體，將其與每個小組的組長進行比較，如果新生成的染色體比組長好，則用來替換組長。

（2） 組 長 交 流（ Team Leader Communication,TLC）。隨機選取兩個組，將兩個組長進行RPOX 操作，如果子代個體質量優于父代，則替換之。

（3）組 員 交 流（Team Member Communication,TMC）。隨機選擇兩個小組，在其中各隨機選擇一個個體，將這兩個個體進行RPOX 操作，保留質量好的那個子代，再將其與父代染色體進行比較，如果優于父代染色體，則替換之。

2.2.6 組內討論（In-groupDiscussion,IND） 組內討論的次數隨著算法迭代次數的增加而增加，即動態改變，如式(14)所示：

其中：Nt_in為當前組內討論次數；Nm_t為組內討論次數的上限；Nc_i為當前迭代次數；Nm_i為總的迭代次數。這樣可以在搜索后期著重細致搜索，找到更加優質的解。

更新種群的方式有如下3 種：

（1）組長革命（LR）。將組長通過RMO 操作生成新個體，若其質量比原個體好，則替換之。

（2）組員革命（TMR）。在本組中隨機選擇一個組員，采用RMO 操作產生新個體，如果新個體優于該組員以及組長，則用其替換組員與組長。

（3）組員交流（TMC）。在本組中隨機選擇兩個成員，進行RPOX 操作產生兩個新個體，取最優個體，分別與父代個體進行比較，將質量差的個體替換掉。若最優子代個體比組長的質量好，則用最優子代個體替代組長。

頭腦風暴優化算法具有新穎、參數少等特點，且應用在其他種類優化問題中都得到了較好的效果，故本文采用該算法探索其在批量調度問題中的應用。

3 仿真實驗

以一個具體的6 種工件、4 道工序的生產系統為例，表1 和表2 分別示出了工件與機器的信息。其中，BH表示該種類型工件的總數，Jm表示工件的機器集合，PTm與Tm分別表示準備時間與加工時間。Oi表示第道i工序，Pmax表示機器的最大負荷。圖4示出了調度方案的甘特圖，其中淺灰色方塊代表了各臺機器加工不同類型工件的準備時間，其他顏色方塊表示了不同種類工件在各臺機器的加工時間，方塊上面的JP-Q-k表示工件P的第Q個階段的第k個子批。

表1 工件加工的信息Table1 Informationofjobprocessing

表2 機器的最大負荷Table2 Maximumloadsofthemachines

由圖4 可知，該系統有6 個工件、4 個加工階段，按照參與某個工件的所有機器的負荷的最小值與當前未加工工件的剩余數量進行分批操作。Job1 有3 個加工階段，第1 個階段由M4 和M5 組合加工，按照生產計劃，Job1 的第1 個階段從250 時刻開始分成3 個子批進行加工。第1 個子批在M4 和M5 上的加工完成時間分別為370 和394，所以該子批的第1 個階段完工時刻為394。同理，第2 個子批和第3 個子批的完工時間分別為538 和610。第2 個加工階段只有M3 參與，由于M3 的機器負載大于第1 個階段的最小機器負載，所以必須在538 時刻才可以開始第2 個階段的加工。同上，每個階段每個子批的批量以及加工開始時間都要考慮機器約束和工件約束。

圖4 多處理機組合生產的甘特圖Fig.4 GanttchartofMCBSP

3.1 實驗設置

由于本文研究的調度問題是隨著生產系統的改變而新出現的，沒有標準的Benchmark 算例庫，故采用隨機生成算例。機器準備時間的范圍為（1，10），單位加工時間為（5，25）。機器數量（m）、準備時間（Setuptime）、工件加工時間(Processtime)、相同種類工件數量( Pi ec)e以及總工序數量(Totalprocess)的選取范圍如表3 所示，其中 Total pr ocess=n×m× Piece，n和stage 分別為工件的類型和階段數量。

由于此類批量調度問題不同于傳統的作業車間調度問題，不同種類的工件數量不盡相同，從而會導致總的工序數量極速增大。即使針對只有6 種類型工件的生產系統（如表3 中 6× 4規模），需要調度的總工序數量也會達到360 個。

表3 不同規模算例工序總數統計表Table3 Statisticaltableofthetotalprocessfordifferentscalecalculationexamples

3.2 參數分析

BSOGT 算法的參數設置對于算法的尋優效果、收斂性以及運算速度有著很大的影響，本文采用響應面分析方法來確定其參數。以3.1 節算例庫中的10×10 算例為例進行實驗，每組實驗獨立運行5 次，取5 次運行Makespan 的平均值(AVG)作為響應值。利用Design-Expert10.0 軟件，以AVG 作為評價指標，其二次多項式模型的方差分析結果如表4 所示。表中VS（VarianceSource）表示方差來源，MS(Main Square)表示均方，FD(FreedomDegree)表示自由度，SS(SumSquare)表示平方和P。＜0 .0 5，說明回歸模型高度顯著；P> 0.05，說明模型失擬性不顯著，回歸模型擬合程度高。

表4 AVG 的二次多項式模型的方差分析Table4 ANOVAofquadraticpolynomialmodelforAVG

由3 種因素的P值可判斷3 個實驗因素對AVG有著顯著的影響；該模型的決定系數與校正決定系數均接近1，說明該擬合回歸模型具有較高的可靠性。擬合的殘差正態概率分布圖、預測與實際的對比圖分別如圖5 和圖6 所示。由擬合結果可知，殘差值較為均勻地分布在直線兩側，實際數據較為均勻地分布在擬合直線上下兩側，說明擬合效果很好。

圖5 殘差正態概率分布圖Fig.5 Externallystudentizedresiduals

圖6 模型預測值和實際值比較Fig.6 Comparison between predicted and actual value of the model

根據回歸模型分析結果，選取種群規模population size=100，組長個數Nldr=，6 相對變異步P長mut=0 .2。

3.3 初始種群質量分析

2.2.3 節中提出了嵌入貪婪機制的IEG。為了說明其性能，將IEG 與隨機的方式(RandomlyGenerate,RG)、基于反向學習機制(OppositionBasedLearning,OBL)的方式進行了比較。采用3.1 節中的數據集，使用BSOGT 算法，取所有初始種群的makespan 的平均值(AVG)作為目標。AVG 值越小，說明初始種群的質量越高。AVG 計算公式如式（15）所示。

其中：Ii表示第i個個體的質量；p為種群規模。表5示出了不同方式下的初始種群的質量。

由表5 可以看出，針對數據集中的算例，IEG 方式得到的AVG 比其他兩種方式的AVG 要小。在IEG 中，個體當中有一半的基因是隨機生成的，有一半的基因是引入貪婪思想后生成的，因此當有新基因插入到當前序列中時，應該選擇所有可能的插入位置中使生產周期增量最小的插入位置。即在一半隨機生成的基因中，每增加一個基因，該基因插入到個體中的位置，對于整個系統的影響都是最小的，所以相對于RG、OBL 方式，IEG 方式可以大大改善初始種群的質量。

表5 初始種群質量分析Table5 Qualityanalysisofinitialindividual

3.4 分批方式的影響

考慮到機器容量的限制，針對一致分批（CM），工件分批時需考慮參與其加工的所有機器的容量。針對不分批和等量分批的方式，由于機器容量的限制，需要對工件進行分批處理；由于某些工件的總數會導致無法對工件進行等量分批，如某種類型工件數量為15 個，而機器負載容量為2 個，實際上無法采用等量分批。該情況下的等量分批實質就是一致分批。因此本文只對可變分批（VM）與一致分批的影響進行分析。獨立進行10 次實驗，取最小值。同時，采用機器空置率的平均值（AverageMachineVacancy Rate,AMVR）來衡量機器的運行效率。AMVR 的計算如式（16）所示：

其中：PTj為機器的j實際生產時間；ET j、S Tj分別為機器j的加工過程結束時間、開始時間。實驗結果如表6 所示，部分算例不同分批方式的甘特圖如圖7 所示。

由表6 可以看出，以 6× 4算例為例，一致分批比可變分批的生產周期平均多出11.00%。并且針對大多數的算例，可變分批相比于一致分批可以縮短生產周期。這是因為可變分批方式可以使工件在生產過程中靈活地進行分批，減少了待加工工件的等待時間和機器的空閑時間，進而縮短了生產周期。因此，本文提出的可變分批相比于一致分批更有優勢。

表6 不同分批方式的對比Table6 Comparisonofdifferentbatchmodes

3.5 算法性能測試

取不同規模的算例進行測試。將BSOGT 與MA[17]、ICA[18]以及BSO[12]進行比較，每種算例獨立運行10 次，分別以相對百分比偏差（RPD）、最優相對誤差（BRE）、最差相對誤差（WRE）作為性能指標，如式（17）～式（19）所示。

式中：MAX、MIN、AVG、Best 分別表示最大值、最小值、平均值和最優值。對比結果如表7 所示。

從表7 可以看出，針對 15× 7 、5 0× 15算例，所有算法的性能指標都接近0，說明當算例規模較小時，所有算法均可以找到最優解，性能差別不大。隨著規模的增大，ICA、MA、BSO3 種算法的RPD、BRE、WRE 指標都在變大。RPD 增大，說明算法的尋優能力減弱，而BRE 和WRE 的增大反映了算法的穩定性變差。BSOGT 算法在大部分算例中的RPD、BRE、WRE 都小于其他3 種算法，且隨著算例規模的增大，BSOGT 算法的優勢更明顯。圖7 示出了兩組不同規模算例的算法收斂曲線。由于BSOGT引入了動態的組內、組間討論機制，故BSOGT 在算法進化的初期有著較快的收斂速度，注重全局搜索，而在算法迭代后期，注重局部搜索，有著較好的尋優能力。

表7 算法性能對比表Table7 Performancecomparisonofalgorithms

圖7 不同算法的收斂曲線Fig.7 Convergencesofdifferentalgorithms

綜上所述，引入貪婪思想來生成初始種群，動態的組內、組間討論策略以及改進的變異操作使得BSOGT算法無論是初始種群的質量，還是收斂速度以及尋優質量都優于其他算法。

4 結 論

本文針對作業車間環境下多處理機組合生產的批量調度問題，考慮了機器的準備時間以及機器的加工負載，提出了可變分批方式，建立了調度模型。針對基本頭腦風暴算法收斂速度慢，容易陷入局部最優的缺陷，提出了改進的頭腦風暴算法，優化建立的數學模型。為了提高初始種群的質量，引入了貪婪思想。將BSOGT 進化過程分為組內討論和組間討論兩個階段。組內討論通過組員與組員、組員與組長的相互交流來更新高質量的個體；組間討論通過組長與組長、不同組的組員之間的交流來更新高質量的個體。每次迭代中組內討論次數隨著迭代次數的增加而增多，組間討論次數隨著迭代次數的增加而減少。使得在搜索開始階段，加強廣泛搜索，充分發現潛在的全局最優；而在搜索后期，著重細致搜索，加速收斂。