王全武，徐震浩，顧幸生

（華東理工大學(xué)能源化工過程智能制造教育部重點(diǎn)實(shí)驗(yàn)室，上海 200237）

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

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

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

到目前為止，已有許多學(xué)者對(duì)多處理機(jī)組合調(diào)度問題進(jìn)行了研究，但是針對(duì)作業(yè)車間環(huán)境下多處理機(jī)任務(wù)組合的批量調(diào)度問題的研究成果較少。因此，本文針對(duì)作業(yè)車間環(huán)境下考慮機(jī)器的準(zhǔn)備時(shí)間的問題，提出了基于機(jī)器負(fù)荷的可變分批方式，建立了作業(yè)車間的可變分批調(diào)度模型，并提出了改進(jìn)的頭腦風(fēng)暴優(yōu)化算法。

1 問題描述和數(shù)學(xué)模型

1.1 問題描述

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

（1）不考慮機(jī)器故障，機(jī)器在零時(shí)刻準(zhǔn)備就緒；

（2）同一臺(tái)機(jī)器的某一時(shí)刻只能加工一種類型的工件；

（3）同一批次內(nèi)只能包含一種類型的工件；

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

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

（6）不考慮工件在不同機(jī)器上加工的運(yùn)輸時(shí)間。

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

1.2.1 下標(biāo)定義

1.2.2 參數(shù)定義

1.2.3 決策變量

1.2.4 調(diào)度目標(biāo)與約束條件

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

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

工序j第p個(gè)子批中的最后一個(gè)工件所對(duì)應(yīng)的上一道工序的批次號(hào)s受限于上一道工序已經(jīng)加工的工件數(shù)量和：

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

（1）當(dāng)j> 1,時(shí)p=，1 工件 第ij道工序第一個(gè)子批的開始加工時(shí)間取決于機(jī)器集中的各臺(tái)機(jī)器的釋放時(shí)間和第j? 1道 工序上第s個(gè)子批完工時(shí)間的最大值。

2 具有貪婪思想的頭腦風(fēng)暴優(yōu)化算法

2.1 BSO 算法

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

2.2 BSO 算法的改進(jìn)

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

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

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

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

2.2.2 環(huán) 變 異 操 作 環(huán) 變 異 操 作（Ring Mutation Operation,RMO）是將個(gè)體圍成一個(gè)環(huán)，保證每個(gè)基因作為變異起點(diǎn)的概率相等。該操作清除了傳統(tǒng)的變異方式所產(chǎn)生的變異盲區(qū)，加強(qiáng)了個(gè)體中首尾基因的聯(lián)系，增加產(chǎn)生優(yōu)質(zhì)個(gè)體的概率。環(huán)變異操作示意圖如圖3 所示。操作步驟如下：

圖3 環(huán)變異操作Fig.3 Ringmutationoperation

（1）將待變異的染色體的首尾相接連成一個(gè)環(huán)；

（3）將劣環(huán)進(jìn)行逆序操作，并且將其首尾相接連成一個(gè)環(huán)，即逆序劣環(huán)；

（4）在優(yōu)環(huán)中，隨機(jī)選擇一個(gè)點(diǎn)作為變異基因的插入點(diǎn)，并且隨機(jī)在逆序劣環(huán)上選擇一個(gè)點(diǎn)將其拆開；

（5）將拆開的逆序劣環(huán)插入到優(yōu)環(huán)中去，形成一個(gè)新的個(gè)體。

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

2.2.5 組間討論 組間討論的次數(shù)隨著進(jìn)化代數(shù)的增加而減小，如式（13）所示：

其中：Ntex為當(dāng)前組間討論次數(shù)；Nmi為算法的最多迭代次數(shù)；Nci為當(dāng)前算法迭代次數(shù)。

組間討論有3 種個(gè)體更新的方式：

（1）組長(zhǎng)革命（LeaderRevolution，LR）。隨機(jī)生成一條染色體，將其與每個(gè)小組的組長(zhǎng)進(jìn)行比較，如果新生成的染色體比組長(zhǎng)好，則用來替換組長(zhǎng)。

（2） 組 長(zhǎng) 交 流（ Team Leader Communication,TLC）。隨機(jī)選取兩個(gè)組，將兩個(gè)組長(zhǎng)進(jìn)行RPOX 操作，如果子代個(gè)體質(zhì)量?jī)?yōu)于父代，則替換之。

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

2.2.6 組內(nèi)討論（In-groupDiscussion,IND） 組內(nèi)討論的次數(shù)隨著算法迭代次數(shù)的增加而增加，即動(dòng)態(tài)改變，如式(14)所示：

其中：Nt_in為當(dāng)前組內(nèi)討論次數(shù)；Nm_t為組內(nèi)討論次數(shù)的上限；Nc_i為當(dāng)前迭代次數(shù)；Nm_i為總的迭代次數(shù)。這樣可以在搜索后期著重細(xì)致搜索，找到更加優(yōu)質(zhì)的解。

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

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

（2）組員革命（TMR）。在本組中隨機(jī)選擇一個(gè)組員，采用RMO 操作產(chǎn)生新個(gè)體，如果新個(gè)體優(yōu)于該組員以及組長(zhǎng)，則用其替換組員與組長(zhǎng)。

（3）組員交流（TMC）。在本組中隨機(jī)選擇兩個(gè)成員，進(jìn)行RPOX 操作產(chǎn)生兩個(gè)新個(gè)體，取最優(yōu)個(gè)體，分別與父代個(gè)體進(jìn)行比較，將質(zhì)量差的個(gè)體替換掉。若最優(yōu)子代個(gè)體比組長(zhǎng)的質(zhì)量好，則用最優(yōu)子代個(gè)體替代組長(zhǎng)。

頭腦風(fēng)暴優(yōu)化算法具有新穎、參數(shù)少等特點(diǎn)，且應(yīng)用在其他種類優(yōu)化問題中都得到了較好的效果，故本文采用該算法探索其在批量調(diào)度問題中的應(yīng)用。

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

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

表1 工件加工的信息Table1 Informationofjobprocessing

表2 機(jī)器的最大負(fù)荷Table2 Maximumloadsofthemachines

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

圖4 多處理機(jī)組合生產(chǎn)的甘特圖Fig.4 GanttchartofMCBSP

3.1 實(shí)驗(yàn)設(shè)置

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

由于此類批量調(diào)度問題不同于傳統(tǒng)的作業(yè)車間調(diào)度問題，不同種類的工件數(shù)量不盡相同，從而會(huì)導(dǎo)致總的工序數(shù)量極速增大。即使針對(duì)只有6 種類型工件的生產(chǎn)系統(tǒng)（如表3 中 6× 4規(guī)模），需要調(diào)度的總工序數(shù)量也會(huì)達(dá)到360 個(gè)。

表3 不同規(guī)模算例工序總數(shù)統(tǒng)計(jì)表Table3 Statisticaltableofthetotalprocessfordifferentscalecalculationexamples

3.2 參數(shù)分析

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

表4 AVG 的二次多項(xiàng)式模型的方差分析Table4 ANOVAofquadraticpolynomialmodelforAVG

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

圖5 殘差正態(tài)概率分布圖Fig.5 Externallystudentizedresiduals

圖6 模型預(yù)測(cè)值和實(shí)際值比較Fig.6 Comparison between predicted and actual value of the model

根據(jù)回歸模型分析結(jié)果，選取種群規(guī)模population size=100，組長(zhǎng)個(gè)數(shù)Nldr=，6 相對(duì)變異步P長(zhǎng)mut=0 .2。

3.3 初始種群質(zhì)量分析

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

其中：Ii表示第i個(gè)個(gè)體的質(zhì)量；p為種群規(guī)模。表5示出了不同方式下的初始種群的質(zhì)量。

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

表5 初始種群質(zhì)量分析Table5 Qualityanalysisofinitialindividual

3.4 分批方式的影響

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

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

由表6 可以看出，以 6× 4算例為例，一致分批比可變分批的生產(chǎn)周期平均多出11.00%。并且針對(duì)大多數(shù)的算例，可變分批相比于一致分批可以縮短生產(chǎn)周期。這是因?yàn)榭勺兎峙绞娇梢允构ぜ谏a(chǎn)過程中靈活地進(jìn)行分批，減少了待加工工件的等待時(shí)間和機(jī)器的空閑時(shí)間，進(jìn)而縮短了生產(chǎn)周期。因此，本文提出的可變分批相比于一致分批更有優(yōu)勢(shì)。

表6 不同分批方式的對(duì)比Table6 Comparisonofdifferentbatchmodes

3.5 算法性能測(cè)試

取不同規(guī)模的算例進(jìn)行測(cè)試。將BSOGT 與MA[17]、ICA[18]以及BSO[12]進(jìn)行比較，每種算例獨(dú)立運(yùn)行10 次，分別以相對(duì)百分比偏差（RPD）、最優(yōu)相對(duì)誤差（BRE）、最差相對(duì)誤差（WRE）作為性能指標(biāo)，如式（17）～式（19）所示。

式中：MAX、MIN、AVG、Best 分別表示最大值、最小值、平均值和最優(yōu)值。對(duì)比結(jié)果如表7 所示。

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

表7 算法性能對(duì)比表Table7 Performancecomparisonofalgorithms

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

綜上所述，引入貪婪思想來生成初始種群，動(dòng)態(tài)的組內(nèi)、組間討論策略以及改進(jìn)的變異操作使得BSOGT算法無論是初始種群的質(zhì)量，還是收斂速度以及尋優(yōu)質(zhì)量都優(yōu)于其他算法。

4 結(jié) 論

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