改進(jìn)ICA求解柔性作業(yè)車間插單重調(diào)度問題

唐 亮，程 峰，吉衛(wèi)喜，金志斌

江南大學(xué) 機(jī)械工程學(xué)院，江蘇 無錫 214122

柔性作業(yè)車間調(diào)度問題[1]（flexible job shop scheduling problem，F(xiàn)JSP）是經(jīng)典車間調(diào)度問題的延伸，擴(kuò)展了每道工序的機(jī)器柔性，相對(duì)經(jīng)典車間調(diào)度問題來說更加復(fù)雜。然而在車間實(shí)際生產(chǎn)過程中，會(huì)面臨各種各樣的擾動(dòng)因素，如機(jī)器故障、緊急插單、訂單延期等一系列不確定因素，要充分考慮到當(dāng)前的工作環(huán)境及系統(tǒng)狀態(tài)，及時(shí)對(duì)生產(chǎn)中產(chǎn)生的擾動(dòng)因素做出響應(yīng)，制定出合理的重調(diào)度方案，因此就出現(xiàn)了柔性作業(yè)車間動(dòng)態(tài)重調(diào)度問題。

目前，針對(duì)柔性作業(yè)車間動(dòng)態(tài)重調(diào)度的研究，廣大學(xué)者進(jìn)行了大量的嘗試。何小妹等[2]針對(duì)多目標(biāo)多階段混合流水車間的緊急訂單插單重調(diào)度問題，分別采用NSGA-II 和NSGA-III 求解該問題，驗(yàn)證了NSGA-III 在求解三目標(biāo)優(yōu)化問題上的有效性。張守京等[3]針對(duì)車間調(diào)度調(diào)整提出了基于免疫度的規(guī)則導(dǎo)向策略，以確保實(shí)際生產(chǎn)計(jì)劃的健康執(zhí)行。衛(wèi)少鵬等[4]在求解綠色柔性作業(yè)車間動(dòng)態(tài)調(diào)度問題上，采用改進(jìn)的頭腦風(fēng)暴算法進(jìn)行求解，即在編碼環(huán)節(jié)引進(jìn)轉(zhuǎn)換機(jī)制和多層編碼策略，優(yōu)化了機(jī)器選擇和工序排序問題。張潔等[5]提出一種基于滾動(dòng)窗口的改進(jìn)蟻群算法來求解混合流水車間動(dòng)態(tài)調(diào)度問題，即通過壓縮螞蟻可選路徑，來縮短螞蟻搜索周期和刺激螞蟻嘗試具有較弱信息素路徑來提高所得解的全局性。李聰波等[6]提出一種基于多目標(biāo)引力搜索算法的重調(diào)度節(jié)能優(yōu)化求解方法，來解決機(jī)械加工過程中出現(xiàn)緊急任務(wù)插單和機(jī)床故障等動(dòng)態(tài)事件導(dǎo)致原調(diào)度能耗增高、完工時(shí)間延長(zhǎng)等問題。Akkan[7]為兼顧重調(diào)度的穩(wěn)定性和魯棒性，提出分支定與局部搜索結(jié)合混合算法。一些學(xué)者[8-10]針對(duì)重調(diào)度易導(dǎo)致生產(chǎn)系統(tǒng)的振蕩，以事件驅(qū)動(dòng)策略為研究對(duì)象進(jìn)行一系列改進(jìn)研究。張祥等[11]利用動(dòng)態(tài)交互層機(jī)制，結(jié)合PSGA算法，提高了動(dòng)態(tài)調(diào)度處理緊急訂單的能力。陳超等[12]利用結(jié)合遺傳算法和模擬退火算法的混合算法，求解以平均流經(jīng)時(shí)間和能耗為目標(biāo)的DFJSP優(yōu)化模型。

帝國(guó)競(jìng)爭(zhēng)算法是一種受社會(huì)政治行為啟發(fā)而提出的智能優(yōu)化算法，它既是有效的全局搜索算法，又具有很強(qiáng)的局部搜索能力，能有效地實(shí)現(xiàn)全局搜索和局部搜索的協(xié)調(diào)，適用于不同種類的優(yōu)化問題，同時(shí)具有靈活性、魯棒性、可擴(kuò)展性等顯著特征[13]。但是ICA 算法在產(chǎn)生初始解在空間上分布不均會(huì)使最終解易于偏向局部最優(yōu)解。針對(duì)此類問題，李明等[14]提出一種新型帝國(guó)競(jìng)爭(zhēng)算法來解決高維多目標(biāo)柔性作業(yè)車間調(diào)度問題，采用新方法構(gòu)建初始帝國(guó)，引入殖民國(guó)家同化，應(yīng)用新的革命策略和帝國(guó)競(jìng)爭(zhēng)方法來獲得高質(zhì)量解。操三強(qiáng)等[15]設(shè)計(jì)一種多目標(biāo)帝國(guó)競(jìng)爭(zhēng)算法，采用簡(jiǎn)化的初始帝國(guó)構(gòu)建過程，在同化過程中引入向外部檔案學(xué)習(xí)機(jī)制，并基于新的帝國(guó)競(jìng)爭(zhēng)方法獲得高質(zhì)量的解。呂聰?shù)萚16]提出一種協(xié)作混合帝國(guó)算法，設(shè)計(jì)一種自適應(yīng)參數(shù)的改進(jìn)，來提高算法的收斂速度，引入帝國(guó)殖民地雙改革變異，提高算法的局部搜索效率，最后創(chuàng)建大陸間國(guó)家交流機(jī)制，提高算法的全局搜索能力。而韓忠華等[17]在標(biāo)準(zhǔn)帝國(guó)競(jìng)爭(zhēng)算法的基礎(chǔ)上，引入漢明距離的概念判斷個(gè)體之間的相似度，同時(shí)將各帝國(guó)集團(tuán)內(nèi)最弱殖民地用一個(gè)隨機(jī)解代替并保留所有失去所有殖民地的個(gè)體，提高了算法的局部搜索能力。張清勇等[18]設(shè)計(jì)一種新型ICA，采用最大處理時(shí)間解碼和基于加工速度的概率分配方法構(gòu)建初始種群，運(yùn)用基于工件-工速積的新型插入算子改善解的質(zhì)量。

針對(duì)柔性車間動(dòng)態(tài)重調(diào)度問題，廣大學(xué)者進(jìn)行了大量研究，但對(duì)于插單重調(diào)度，同時(shí)考慮設(shè)備待機(jī)能耗和加工能耗的研究較少。然而在實(shí)際生產(chǎn)過程中，緊急插單是十分普遍的擾動(dòng)事件，如何制定合適的重調(diào)度方案對(duì)車間生產(chǎn)是十分重要的。本文提出一種改進(jìn)的帝國(guó)競(jìng)爭(zhēng)算法解決此類調(diào)度問題，即在帝國(guó)同化階段采用離散帝國(guó)競(jìng)爭(zhēng)算法的交叉變異實(shí)現(xiàn)，增加帝國(guó)革命機(jī)制，帝國(guó)消除機(jī)制，以及外部帝國(guó)入侵機(jī)制，并采用基于事件驅(qū)動(dòng)的重調(diào)度策略來解決此類調(diào)度問題，驗(yàn)證了算法的有效性。

1 問題描述

柔性作業(yè)車間調(diào)度問題[19]可簡(jiǎn)單描述為：初始時(shí)刻，有若干工件Ji(i=1,2,…,n)到達(dá)，要將這n個(gè)工件安排在設(shè)備Mj(j=1,2,…,m)上進(jìn)行加工；每個(gè)工件有多道加工工序，每個(gè)工件的每道工序都可以選擇不同的設(shè)備進(jìn)行加工，所選設(shè)備不同其對(duì)應(yīng)的加工時(shí)長(zhǎng)也不相同。但在實(shí)際生產(chǎn)過程中，車間會(huì)面臨許多突發(fā)的擾動(dòng)因素，這些擾動(dòng)因素會(huì)對(duì)實(shí)際的調(diào)度計(jì)劃產(chǎn)生較大影響，針對(duì)車間加工過程中可能出現(xiàn)的各種擾動(dòng)因素，本文針對(duì)訂單插入這一類動(dòng)態(tài)事件。柔性作業(yè)車間動(dòng)態(tài)重調(diào)度研究存在以下幾個(gè)假設(shè)條件：

（1）初始時(shí)刻，所有設(shè)備均處于待機(jī)狀態(tài)。

（2）相同工件不同工序有嚴(yán)格的加工順序，即相同工件前道工序加工完成后，后道工序才能進(jìn)行加工。

（3）每道工序可在可選設(shè)備集中任選一臺(tái)設(shè)備加工，但同一時(shí)刻只能選擇一臺(tái)設(shè)備加工。

（4）一臺(tái)設(shè)備同一時(shí)刻只能加工一個(gè)工件，同一工件同一時(shí)刻只能在一臺(tái)設(shè)備上加工。

（5）每道工序的加工時(shí)間包括工序的準(zhǔn)備時(shí)間和設(shè)備變更時(shí)間。

（6）原調(diào)度已加工和正在加工的工序保持不變，重調(diào)度時(shí)只需考慮未加工的工序。

在車間實(shí)際生產(chǎn)過程中，當(dāng)有新的訂單到來時(shí)，預(yù)調(diào)度方案不再適用，為保證車間的生產(chǎn)效率和訂單的按時(shí)完成，此時(shí)應(yīng)及時(shí)調(diào)整預(yù)調(diào)度方案，并結(jié)合重調(diào)度策略生成新的調(diào)度方案。

1.1 約束條件

車間實(shí)際生產(chǎn)過程中需考慮工件自身的約束和設(shè)備的加工約束：

式中，i、j、k分別表示工件號(hào)，工序號(hào)和設(shè)備號(hào)，Mij為工序Oij的可選設(shè)備集，θijk為決策變量0/1，若工序Oij在設(shè)備Mk上加工，決策變量為1，反之為0，CTij、STij和PTij分別表示工序Oij的加工結(jié)束時(shí)間、開始時(shí)間和加工時(shí)間，CTijk和STijk分別表示工序Oij在設(shè)備Mk上的加工結(jié)束時(shí)間和開始時(shí)間。

式（1）表示工序自身的加工約束，即每道工序每次只能選擇一臺(tái)設(shè)備進(jìn)行加工；

式（2）表示工序自身的時(shí)間約束，即工序的完工時(shí)間為工序開始時(shí)間和加工時(shí)間之和；

式（3）表示工件各工序間的時(shí)間約束，即同一工件只有上一道工序加工完成后，下一道工序才能開始加工；

式（4）表示加工設(shè)備上各工序的時(shí)間約束，即同一設(shè)備同一時(shí)刻只能加工一道工序。

1.2 目標(biāo)函數(shù)

本文的目標(biāo)函數(shù)為最小最大完工時(shí)間、最小加工能耗、最小總延遲時(shí)間和最小設(shè)備變更次數(shù)，具體公式如下：

（1）最小化最大完工時(shí)間

式中，CTi表示第i個(gè)工件的最后一道工序的完工時(shí)間，CTmax為所有工件中的最大完工時(shí)間。

（2）最小化總能耗

本文采用文獻(xiàn)[14]的加工能耗E的表示方法，初始時(shí)刻所有設(shè)備均處于待機(jī)狀態(tài)，設(shè)備的總能耗為設(shè)備的待機(jī)能耗和加工能耗之和，總能耗的數(shù)學(xué)模型可表示為公式（6）：

式中，E0ijk和Pijk分別表示工序Oij在設(shè)備Mk上的單位時(shí)間加工能耗和加工時(shí)間，θijk為決策變量0/1，若工序Oij在設(shè)備Mk上加工，決策變量為1，反之為0，E1K和FTK分別表示設(shè)備Mk單位時(shí)間的待機(jī)能耗和待機(jī)時(shí)間，TE表示所有工件加工完成時(shí)的總能耗。

（3）最小總延遲時(shí)間

訂單插入前后的最大完工時(shí)間的差值稱為總延遲時(shí)間，總延遲時(shí)間的數(shù)學(xué)模型可表示為公式（7）：

式中，CT1max和CT0max分別表示重調(diào)度后所有工件的最大完工時(shí)間和預(yù)調(diào)度所有工件的最大完工時(shí)間，DT表示重調(diào)度前后完工時(shí)間差。

（4）最小化設(shè)備變更次數(shù)

本文最小設(shè)備變更次數(shù)是指訂單插入前后，工件工序加工設(shè)備變更的累計(jì)。工件工序操作設(shè)備的變更，會(huì)增加人力勞動(dòng)及調(diào)運(yùn)成本，以此重調(diào)度需充分考慮工序加工設(shè)備的變更次數(shù)[20]。

工序Oij的變更，可描述為：

設(shè)備總變更次數(shù)可表示為：

式中，EC表示重調(diào)度前后，工序Oij操作設(shè)備的變更次數(shù)，TEC表示重調(diào)度完成后所有工序設(shè)備變更次數(shù)的總和。由于目標(biāo)函數(shù)的量綱不統(tǒng)一，需要分別對(duì)其進(jìn)行歸一化處理，計(jì)算過程如式（10）所示：

其中，λ*、λ、λmax和λmin分別表示歸一化的目標(biāo)函數(shù)值、當(dāng)前目標(biāo)值、全局目標(biāo)最大值和最小值。

本文采用線性加權(quán)和法，首先對(duì)本文的目標(biāo)函數(shù)進(jìn)行歸一化處理，將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，如式（11）所示：

其中，CT*max、TE*、DT*、TEC*分別表示歸一化后的最大完工時(shí)間、加工能耗、總延遲時(shí)間和總設(shè)備變更次數(shù)的數(shù)值，ω1、ω2、ω3、ω4分別為最大完工時(shí)間、總能耗、總延遲時(shí)間和總設(shè)備變更次數(shù)的權(quán)重系數(shù)，且滿足：

2 FJSP動(dòng)態(tài)重調(diào)度策略

柔性作業(yè)車間動(dòng)態(tài)重調(diào)度策略，指系統(tǒng)在生產(chǎn)過程突發(fā)情況下將采取何種應(yīng)對(duì)措施來解決發(fā)生的突發(fā)事件。事件驅(qū)動(dòng)、周期驅(qū)動(dòng)和周期與事件的混合驅(qū)動(dòng)是廣大學(xué)者普遍采用解決柔性車間動(dòng)態(tài)重調(diào)度的方法，針對(duì)訂單插入重調(diào)度，本文采用事件驅(qū)動(dòng)策略。

在實(shí)際生產(chǎn)過程中，當(dāng)出現(xiàn)訂單插入時(shí)，確定訂單插入點(diǎn)，插入點(diǎn)前已加工工序和正在加工的工序保持不變，找出插入點(diǎn)后未加工工序和新插入的訂單用改進(jìn)帝國(guó)競(jìng)爭(zhēng)算法進(jìn)行重調(diào)度，訂單插入重調(diào)度的具體流程如圖1所示。

圖1 訂單插入重調(diào)度流程Fig.1 Order insertion reschedule process

3 算法設(shè)計(jì)

3.1 基于I-ICA的柔性作業(yè)車間調(diào)度

本節(jié)采用I-ICA 求解柔性車間的插單重調(diào)度問題。ICA[21]是一種受社會(huì)啟發(fā)的隨機(jī)優(yōu)化搜索算法，使其在解決大規(guī)模組合優(yōu)化問題上具有一定的優(yōu)越性，但是由于ICA 算法在產(chǎn)生初始解在空間上分布不均會(huì)使最終解易于偏向局部最優(yōu)解。針對(duì)此類問題，本文相對(duì)于傳統(tǒng)帝國(guó)競(jìng)爭(zhēng)算法，做出了以下改進(jìn)：

（1）I-ICA與標(biāo)準(zhǔn)ICA不同的是，在帝國(guó)內(nèi)同化環(huán)節(jié)采用交叉變異方式來實(shí)現(xiàn)殖民地向殖民國(guó)家的移動(dòng)。

（2）為提高算法的搜索廣度，在帝國(guó)內(nèi)同化環(huán)節(jié)之后，增加帝國(guó)革命機(jī)制，有利于實(shí)現(xiàn)算法的全局搜索。

（3）為提高算法的收斂速度，在帝國(guó)間競(jìng)爭(zhēng)環(huán)節(jié)，增加帝國(guó)消除機(jī)制，同時(shí)保留較優(yōu)解，即沒有殖民地的帝國(guó)，將其歸屬于殖民地交由其他帝國(guó)去競(jìng)爭(zhēng)。

（4）為進(jìn)一步提高解的搜索廣度，提高算法的收斂速度，本文在帝國(guó)競(jìng)爭(zhēng)結(jié)束之后，引入外部帝國(guó)入侵機(jī)制。即產(chǎn)生新的帝國(guó)集團(tuán)，以二元錦標(biāo)賽的形式從新帝國(guó)集團(tuán)和原帝國(guó)集團(tuán)挑選戰(zhàn)勝國(guó)集團(tuán)，戰(zhàn)勝國(guó)攜帶優(yōu)質(zhì)殖民地進(jìn)入原帝國(guó)集團(tuán)，戰(zhàn)敗國(guó)刪除。

為更好理解算法的運(yùn)行流程，圖2 給出了I-ICA 求解的具體流程。

圖2 I-ICA流程圖Fig.2 I-ICA flowchart

3.2 編碼與解碼

為了同時(shí)描述工件的加工順序信息與加工設(shè)備信息，本文采取基于工件編碼和設(shè)備編碼的雙層結(jié)構(gòu)，編碼的第一層為工件碼，其中工件出現(xiàn)的次數(shù)代表工件的第幾道工序；第二層為設(shè)備碼，每一個(gè)設(shè)備碼表示該道工序可選設(shè)備集的索引號(hào)。每一個(gè)雙層編碼結(jié)構(gòu)對(duì)應(yīng)一個(gè)調(diào)度方案，表示為各工件各道工序所選擇的加工機(jī)器。如圖3所示，若某個(gè)國(guó)家編碼為[2，2，1，3，3，2，1，1，3，1，1，3，2，2，1，2，3，3]，則工件碼為[2，2，1，3，3，2，1，1，3]，設(shè)備碼為[1，1，3，2，2，1，2，3，3]，工件對(duì)應(yīng)的工序碼為{O21,O22,O11,O31,O32,O23,O12,O13,O33}，根據(jù)各工序?qū)?yīng)的可選設(shè)備集，可確定該設(shè)備碼對(duì)應(yīng)的設(shè)備編號(hào)依次為{1，1，6，3，4，3，5，6，7}。

圖3 雙層編碼與解碼Fig.3 Double layer encoding and decoding

3.3 初始化國(guó)家

ICA 初始化產(chǎn)生的個(gè)體成為國(guó)家。初始化產(chǎn)生的個(gè)體采用雙層編碼結(jié)構(gòu)，前n個(gè)表示工件順序，確定工件的加工順序，后面表示各工序?qū)?yīng)的設(shè)備，則一個(gè)國(guó)家個(gè)體表示為式（13）：

將隨機(jī)產(chǎn)生的個(gè)體代入式（14）fitnesss 函數(shù)計(jì)算各個(gè)國(guó)家的歸一化成本，具體如公式（11）所示。每個(gè)國(guó)家勢(shì)力的大小由歸一化后的成本衡量，成本越小國(guó)家勢(shì)力越大。

根據(jù)成本大小進(jìn)行排序，前Nimp成為帝國(guó)，其余淪為殖民地。采用賭輪盤為每個(gè)帝國(guó)分配殖民地，通常勢(shì)力越大的帝國(guó)分配的殖民地越多。

3.4 帝國(guó)內(nèi)同化

帝國(guó)內(nèi)同化環(huán)節(jié)[16]相當(dāng)于群體智能算法中的尋優(yōu)過程，重在增強(qiáng)算法的區(qū)域搜索能力。離散型帝國(guó)競(jìng)爭(zhēng)算法與標(biāo)準(zhǔn)帝國(guó)競(jìng)爭(zhēng)算法最大的不同在于帝國(guó)集團(tuán)內(nèi)殖民地朝殖民國(guó)家的同化過程。本文殖民地向殖民國(guó)家的同化借鑒遺傳算法中的交叉變異方式實(shí)現(xiàn)。由于優(yōu)先操作交叉（precedenceoperation crossover，POX）方式產(chǎn)生的子代都是可行的，不會(huì)違背生產(chǎn)工藝約束，因此本文采用基于POX的交叉規(guī)則對(duì)工件碼和設(shè)備碼進(jìn)行交叉。

圖4 給出了POX 交叉的一個(gè)例子。先對(duì)工件碼進(jìn)行交叉，假定初始工件集為O={1，2，3}，隨機(jī)將工件集分為兩個(gè)子工件集Oi={2}和Oc={1，3}，其中Oi來自帝國(guó)，Oc來自殖民地，則新殖民地由帝國(guó)中的Oi工件集和殖民地中的Oc工件集兩部分組成。完成工件碼交叉后，其對(duì)應(yīng)的加工設(shè)備也進(jìn)行同樣的交叉操作。

圖4 個(gè)體交叉示意圖Fig.4 Individual crossover diagram

3.5 帝國(guó)革命和殖民地革命

柔性作業(yè)車間調(diào)度問題[16]具有高維復(fù)雜性，為了增加算法的全局搜索，防止ICA 過早陷入局部最優(yōu)，基于生物進(jìn)化思想提出殖民地與帝國(guó)雙改革的優(yōu)化。

3.5.1 帝國(guó)革命

針對(duì)柔性作業(yè)車間調(diào)度問題，為滿足工序和設(shè)備加工過程中的約束，采用簡(jiǎn)單交換會(huì)出現(xiàn)沖突，圖5 采用部分映射的方法消除沖突。本文針對(duì)帝國(guó)改革的機(jī)制主要針對(duì)設(shè)備碼的變異，即隨機(jī)產(chǎn)生兩個(gè)變異點(diǎn)，兩個(gè)變異點(diǎn)間的位置基因采用隨機(jī)變異的方式，即在可選設(shè)備集任選一臺(tái)設(shè)備進(jìn)行加工，其他位置的基因保持不變。計(jì)算新帝國(guó)的成本，若新帝國(guó)的成本優(yōu)于原帝國(guó)，則替換原帝國(guó)成為新的宗主國(guó)。

圖5 帝國(guó)革命Fig.5 Imperial revolution

3.5.2 殖民地革命

本文殖民地革命采用的機(jī)制與帝國(guó)革命機(jī)制相同，即都是采用部分映射的方式消除沖突，主要針對(duì)設(shè)備碼的變異。圖6 給出了殖民地革命機(jī)制。計(jì)算新殖民地的成本，若新殖民地的成本優(yōu)于原帝國(guó)的成本，則替換原帝國(guó)成為新的宗主國(guó)，原帝國(guó)成為該宗主國(guó)的殖民地。

圖6 殖民地革命Fig.6 Colonial revolution

3.6 帝國(guó)競(jìng)爭(zhēng)

帝國(guó)競(jìng)爭(zhēng)機(jī)制[16]是帝國(guó)競(jìng)爭(zhēng)算法的核心思想，ICA通過競(jìng)爭(zhēng)機(jī)制，不斷迫使勢(shì)力弱的帝國(guó)割舍殖民地給強(qiáng)大的帝國(guó)，不斷削弱勢(shì)力弱的帝國(guó)，最終實(shí)現(xiàn)帝國(guó)統(tǒng)一和少數(shù)帝國(guó)并立的局面。

3.6.1 帝國(guó)間競(jìng)爭(zhēng)

帝國(guó)集團(tuán)勢(shì)力的大小通過總成本值來衡量，總成本越小，帝國(guó)集團(tuán)勢(shì)力越大。因此在進(jìn)行競(jìng)爭(zhēng)前需計(jì)算每個(gè)帝國(guó)集團(tuán)的總成本，總成本由帝國(guó)集團(tuán)下的殖民地成本和宗主國(guó)成本構(gòu)成，其二者對(duì)帝國(guó)勢(shì)力影響程度不同，因此需要重新構(gòu)造帝國(guó)集團(tuán)的總成本目標(biāo)函數(shù)來衡量各個(gè)帝國(guó)集團(tuán)的勢(shì)力，即：

其中，TotalCostn代表第n個(gè)帝國(guó)集團(tuán)的總成本；Costimp為帝國(guó)集團(tuán)中的宗主國(guó)成本；Costcol為殖民地成本，其中ncol表示該帝國(guó)集團(tuán)下殖民地個(gè)數(shù)；ζ表示殖民地成本對(duì)帝國(guó)集團(tuán)總成本的影響程度（本文取ζ=0.1）。帝國(guó)集團(tuán)間的競(jìng)爭(zhēng)是將勢(shì)力最弱的帝國(guó)集團(tuán)的最弱殖民地釋放，交由其他帝國(guó)集團(tuán)競(jìng)爭(zhēng)。若存在某個(gè)帝國(guó)集團(tuán)的殖民地?cái)?shù)量為0，則將其宗主國(guó)歸屬于殖民地交由其他帝國(guó)集團(tuán)去競(jìng)爭(zhēng)，原帝國(guó)集團(tuán)消除，通常勢(shì)力越強(qiáng)的帝國(guó)集團(tuán)獲得該殖民地的概率越高。

3.6.2 外部帝國(guó)入侵

標(biāo)準(zhǔn)帝國(guó)競(jìng)爭(zhēng)算法[21]僅在隨機(jī)產(chǎn)生的初始國(guó)家中迭代，考慮到產(chǎn)生的解若在解的空間上分布不均，則算法易陷入局部最優(yōu)?，F(xiàn)實(shí)社會(huì)中，當(dāng)有外部較強(qiáng)的勢(shì)力入侵時(shí)，會(huì)加劇沖突的演變，根據(jù)物競(jìng)天擇，適者生存的原則，生存下來的各方會(huì)快速變強(qiáng)。本文基于這一現(xiàn)象，提出一種外來帝國(guó)入侵機(jī)制，用來增加解的多樣性，以此來增加解的搜索廣度，提升國(guó)家的質(zhì)量，使最終結(jié)果更加貼近最優(yōu)。外部帝國(guó)入侵機(jī)制步驟如下：

步驟1 隨機(jī)產(chǎn)生國(guó)家群來組建一批外來帝國(guó)入侵集團(tuán)。

步驟2 在原有帝國(guó)集團(tuán)和入侵帝國(guó)集團(tuán)中采用二元錦標(biāo)賽的形式挑選戰(zhàn)勝國(guó)。

步驟3 戰(zhàn)勝國(guó)將挑選與原有帝國(guó)殖民地?cái)?shù)量相同的優(yōu)秀殖民地組建戰(zhàn)勝國(guó)集團(tuán)，并進(jìn)入原有帝國(guó)集團(tuán)進(jìn)行競(jìng)爭(zhēng)。

3.7 帝國(guó)覆滅及算法終止

在算法迭代過程中，勢(shì)力強(qiáng)大的帝國(guó)集團(tuán)會(huì)以一定的概率獲取最弱帝國(guó)集團(tuán)的最弱殖民來增強(qiáng)自身的勢(shì)力，當(dāng)某個(gè)帝國(guó)集團(tuán)國(guó)家數(shù)量為1 時(shí)（即失去所有殖民地），帝國(guó)覆滅，該集團(tuán)的宗主國(guó)淪為殖民地交由其他帝國(guó)競(jìng)爭(zhēng)。理想狀態(tài)下，算法迭代若干次后，弱小帝國(guó)全部覆滅，大陸統(tǒng)一，算法終止。實(shí)際運(yùn)行過程中，帝國(guó)競(jìng)爭(zhēng)過程中會(huì)始終存在幾個(gè)勢(shì)力相近的帝國(guó)，這些帝國(guó)始終存在直到達(dá)到最大迭代次數(shù)。此時(shí)應(yīng)將勢(shì)力最強(qiáng)的帝國(guó)集團(tuán)中的宗主國(guó)作為最優(yōu)解輸出。

4 仿真結(jié)果及分析

本章通過仿真實(shí)驗(yàn)來驗(yàn)證I-ICA在求解柔性車間插單重調(diào)度問題上的有效性。隨機(jī)假設(shè)三種插單的情景，得出最優(yōu)重調(diào)度方案，驗(yàn)證算法在求解柔性作業(yè)車間插單重調(diào)度問題的有效性。

4.1 參數(shù)設(shè)置

本文的實(shí)例數(shù)據(jù)來自于南通某離散制造企業(yè)，本文的動(dòng)態(tài)調(diào)度案例經(jīng)過簡(jiǎn)化為9×8 的柔性作業(yè)車間調(diào)度問題，具體仿真數(shù)據(jù)如表1所示，可簡(jiǎn)化為9個(gè)工件，8臺(tái)設(shè)備，30道工序的柔性車間調(diào)度問題。表2和表3分別為每臺(tái)設(shè)備的待機(jī)能耗和假設(shè)的三種插單場(chǎng)景，三種插單場(chǎng)景獨(dú)立發(fā)生。

表1 仿真實(shí)例數(shù)據(jù)Table 1 Simulation instance data

表2 設(shè)備待機(jī)能耗Table 2 Equipment standby power consumption

表3 三種插單場(chǎng)景Table 3 Three insertion scenarios

本文使用Matlab 2020a 對(duì)該企業(yè)生產(chǎn)實(shí)例數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，根據(jù)問題的規(guī)模和性質(zhì)，在綜合考慮求解結(jié)果和計(jì)算時(shí)間的前提下，本文I-ICA的參數(shù)設(shè)置參照文獻(xiàn)[21]帝國(guó)競(jìng)爭(zhēng)算法參數(shù)的設(shè)定，并通過多次實(shí)驗(yàn)驗(yàn)證該參數(shù)設(shè)定在求解本文調(diào)度問題上能取得較好的結(jié)果，最后確定本文提出的I-ICA參數(shù)設(shè)置為：最大迭代次數(shù)為200，國(guó)家個(gè)數(shù)為200，帝國(guó)數(shù)量為10，ω1、ω2、ω3和ω4分別設(shè)置為0.2、0.2、0.3 和0.3。同化概率、革命概率和入侵概率分別設(shè)置為0.8、0.4和0.33。

4.2 仿真結(jié)果

本文采用I-ICA 生成預(yù)調(diào)度方案，圖7 為初始最優(yōu)調(diào)度方案對(duì)應(yīng)的甘特圖，其中最大完工時(shí)間為18 min，總能耗為217.2 J。圖7中不同顏色代表不同工件，工件的加工順序由矩形塊左上角的數(shù)字表示：其中“-”前的數(shù)字代表工件號(hào)，“-”后的數(shù)字代表工件的工序號(hào)，例如“5-1”代表工件5的第1道工序。

圖7 初始調(diào)度方案甘特圖Fig.7 Initial scheduling scheme Gantt chart

場(chǎng)景1 是在時(shí)刻t=3 時(shí)插入工件9，重調(diào)度后的最優(yōu)調(diào)度方案對(duì)應(yīng)的甘特圖如圖8所示，其中最大完工時(shí)間為18 min，總能耗為225.5 J，總延遲時(shí)間為0，總設(shè)備變更次數(shù)為0。

圖8 重調(diào)度方案甘特圖(t=3)Fig.8 Rescheduling scheme Gantt chart(t=3)

場(chǎng)景2 是在時(shí)刻t=6 時(shí)插入工件9，重調(diào)度后的最優(yōu)調(diào)度方案對(duì)應(yīng)的甘特圖如圖9所示，其中最大完工時(shí)間為19 min，總能耗為228.7 J，總延遲時(shí)間為1 min，總設(shè)備變更次數(shù)為0。

圖9 重調(diào)度方案甘特圖(t=6)Fig.9 Rescheduling scheme Gantt chart(t=6)

場(chǎng)景3是在時(shí)刻t=10 時(shí)插入工件9，重調(diào)度后的最優(yōu)調(diào)度方案對(duì)應(yīng)的甘特圖如圖10 所示，其中最大完工時(shí)間為18 min，總能耗為234.4 J，總延遲時(shí)間為0，總設(shè)備變更次數(shù)為0。

圖10 重調(diào)度方案甘特圖(t=10)Fig.10 Rescheduling scheme Gantt chart(t=10)

在以往研究中，GA 和PSO 作為常見的單目標(biāo)優(yōu)化算法，被廣大學(xué)者用來解決調(diào)度優(yōu)化問題。ICA在收斂速度和全局最優(yōu)解方面表現(xiàn)出極好的特性，具有較好的優(yōu)化效果，而ICA算法產(chǎn)生初始解在空間上分布不均會(huì)使最終解易于偏向局部最優(yōu)解。因此為驗(yàn)證I-ICA求解的有效性，分別采用標(biāo)準(zhǔn)ICA、GA、PSO 對(duì)以上三種插單場(chǎng)景進(jìn)行求解。各對(duì)比算法均進(jìn)行相應(yīng)的離散化處理，在綜合考慮求解結(jié)果和計(jì)算時(shí)間的前提下，通過多次實(shí)驗(yàn)對(duì)比，確定各算法參數(shù)如表4所示。

表4 算法參數(shù)詳情表Table 4 Algorithm parameter details table

四種算法求解的四種優(yōu)化指標(biāo)數(shù)據(jù)如表5所示，除場(chǎng)景3插單時(shí)間為10 min時(shí)，I-ICA的能耗指標(biāo)較GA的能耗指標(biāo)稍有不足，但其他指標(biāo)均優(yōu)于其他算法指標(biāo)?？梢哉f明I-ICA對(duì)比其他三種算法，實(shí)驗(yàn)結(jié)果更好，說明該算法在求解柔性作業(yè)車間插單重調(diào)度問題上的有效性。

表5 實(shí)驗(yàn)數(shù)據(jù)對(duì)比Table 5 Experimental data comparison

最后，為驗(yàn)證I-ICA求解的穩(wěn)定性，針對(duì)場(chǎng)景2的插單情景，分別采用上述四種算法進(jìn)行求解，四種算法運(yùn)行10次的各項(xiàng)指標(biāo)的平均值和方差如表6所示。從表6中可以看出，I-ICA 與ICA、GA 和PSO 相比各優(yōu)化指標(biāo)的平均值和方差較小，驗(yàn)證了I-ICA求解的穩(wěn)定性。

表6 四種算法的性能對(duì)比Table 6 Performance comparison of four algorithms

針對(duì)上述假設(shè)的插單場(chǎng)景的實(shí)驗(yàn)數(shù)據(jù)分析，通過比較I-ICA 與ICA、GA、PSO 算法的求解結(jié)果，可以說明，插單前后的最大完工時(shí)間、總能耗、總延遲時(shí)間和總設(shè)備變更次數(shù)均能維持在一個(gè)較好的范圍之內(nèi)，滿足車間實(shí)際加工的需求。

5 結(jié)語

本文針對(duì)柔性作業(yè)車間插單重調(diào)度問題，對(duì)傳統(tǒng)帝國(guó)競(jìng)爭(zhēng)算法進(jìn)行了改進(jìn)，相比較于傳統(tǒng)帝國(guó)競(jìng)爭(zhēng)算法，I-ICA加入了帝國(guó)革命機(jī)制，增加帝國(guó)消除機(jī)制，同時(shí)引入外部帝國(guó)入侵機(jī)制，采用基于事件驅(qū)動(dòng)的重調(diào)度策略，以最大完工時(shí)間、總能耗、總延遲時(shí)間以及總設(shè)備變更次數(shù)為優(yōu)化指標(biāo)，對(duì)該類動(dòng)態(tài)事件進(jìn)行求解。對(duì)假設(shè)的三種不同插單場(chǎng)景進(jìn)行實(shí)驗(yàn)仿真分析，得出的結(jié)果較為符合實(shí)際生產(chǎn)需要。針對(duì)三種不同插單場(chǎng)景，將I-ICA同ICA、GA和PSO求解的結(jié)果進(jìn)行對(duì)比，I-ICA求解的各項(xiàng)指標(biāo)均優(yōu)于其他算法，驗(yàn)證了I-ICA求解的有效性。同時(shí)在同一插單場(chǎng)景下，通過比較四種算法運(yùn)行10次各項(xiàng)指標(biāo)的平均值和方差，I-ICA求解四項(xiàng)指標(biāo)的平均值和方差較小，驗(yàn)證了I-ICA求解的穩(wěn)定性。

柔性作業(yè)車間在實(shí)際生產(chǎn)中容易受到各種擾動(dòng)因素的影響，接下來將對(duì)帝國(guó)競(jìng)爭(zhēng)算法進(jìn)行更加深入的研究，將其應(yīng)用到其他擾動(dòng)環(huán)境下的重調(diào)度中，例如設(shè)備故障、工單延誤和交貨期變更等擾動(dòng)事件中。