基于改進(jìn)帝國(guó)競(jìng)爭(zhēng)算法的柔性作業(yè)車(chē)間機(jī)器故障重調(diào)度

張國(guó)輝，陸熙熙，胡一凡，孫靖賀

（鄭州航空工業(yè)管理學(xué)院管理工程學(xué)院，鄭州 450015）

0 引言

作業(yè)車(chē)間調(diào)度問(wèn)題一直是制造業(yè)中的重點(diǎn)關(guān)注對(duì)象，車(chē)間調(diào)度的主要目的是節(jié)省產(chǎn)品的生產(chǎn)時(shí)間，讓生產(chǎn)資源的利用率發(fā)揮最大作用，最后通過(guò)對(duì)資源的恰當(dāng)分配讓柔性作業(yè)車(chē)間的生產(chǎn)效率更高。柔性作業(yè)車(chē)間調(diào)度問(wèn)題（Flexible Jobshop Scheduling Problem，F(xiàn)JSP）是經(jīng)典車(chē)間調(diào)度的延伸，擴(kuò)展了每道工序的機(jī)器柔性，相對(duì)經(jīng)典車(chē)間調(diào)度來(lái)說(shuō)較為繁雜。在實(shí)際的生產(chǎn)制造過(guò)程中，車(chē)間環(huán)境是動(dòng)態(tài)變化的，會(huì)出現(xiàn)各種各樣的問(wèn)題，比如緊急插單、機(jī)器故障等不確定性因素，要充分考慮到當(dāng)前工作環(huán)境及系統(tǒng)的狀態(tài)，及時(shí)作出正確合理的調(diào)度方案，因此就出現(xiàn)了柔性作業(yè)車(chē)間動(dòng)態(tài)重調(diào)度問(wèn)題。在1977年，Nelson等［1］對(duì)于動(dòng)態(tài)調(diào)度問(wèn)題，提出了將動(dòng)態(tài)問(wèn)題轉(zhuǎn)化為多個(gè)連續(xù)的靜態(tài)區(qū)間，對(duì)每個(gè)區(qū)間進(jìn)行優(yōu)化，以達(dá)到總體最優(yōu)。柴永生等［2］根據(jù)動(dòng)態(tài)調(diào)度問(wèn)題提出了免疫遺傳算法，即對(duì)進(jìn)化種群進(jìn)行免疫操作，有效地解決了搜索效率低的問(wèn)題。孟冠軍等［3］在求解多目標(biāo)柔性作業(yè)車(chē)間調(diào)度問(wèn)題上設(shè)計(jì)了改進(jìn)混合人工蜂群算法，即在不同的階段采用不同的搜索機(jī)制，并且為了提高得到最優(yōu)解的概率，將禁忌搜索與改進(jìn)的混合人工蜂群算法結(jié)合。Shahrabi等［4］針對(duì)考慮隨機(jī)作業(yè)到達(dá)和機(jī)器故障的動(dòng)態(tài)作業(yè)車(chē)間調(diào)度問(wèn)題，提出了一種基于變量鄰域搜索的調(diào)度方法，結(jié)合事件驅(qū)動(dòng)策略，為了在任意重調(diào)度點(diǎn)獲得合適的參數(shù)，采用了基于Q因子算法的強(qiáng)化學(xué)習(xí)算法，并通過(guò)模擬作業(yè)車(chē)間實(shí)驗(yàn)結(jié)果表明該方法的性能明顯優(yōu)于常用調(diào)度規(guī)則和一般可變鄰域搜索。He等［5］在研究機(jī)器故障狀態(tài)下的動(dòng)態(tài)調(diào)度問(wèn)題時(shí)，為了提高調(diào)度的魯棒性和穩(wěn)定性，首先提出了一種新的空閑時(shí)間插入策略，其次提出了加工路線(xiàn)變更策略和右移策略相結(jié)合的策略，在這兩種策略的基礎(chǔ)上，提出了一種多策略調(diào)度算法。鄒攀等［6］提出一種基于分層蟻群遺傳算法的車(chē)間資源驅(qū)動(dòng)的多目標(biāo)調(diào)度方法，適用于車(chē)間資源變化、任務(wù)執(zhí)行情況變化、緊急任務(wù)插入等不確定情況下的動(dòng)態(tài)調(diào)度。吳正佳等［7］在研究機(jī)器發(fā)生故障的柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度問(wèn)題時(shí)，提出了兩種重調(diào)度策略即插入重調(diào)度和完全重調(diào)度，并結(jié)合改進(jìn)遺傳算法（Genetic Algorithm，GA）進(jìn)行求解，將機(jī)器故障產(chǎn)生的影響降到最低。孫麗珍等［8］采用改進(jìn)遺傳算法結(jié)合啟發(fā)式規(guī)則求解柔性作業(yè)車(chē)間問(wèn)題；針對(duì)工件加入和機(jī)器故障的動(dòng)態(tài)調(diào)度，提出了加入多約束的貪婪插入空隙法的解碼方式的改進(jìn)遺傳算法。Nouiri等［9］以最小最大完工時(shí)間和魯棒性為目標(biāo)，在求解機(jī)器故障下柔性作業(yè)車(chē)間調(diào)度問(wèn)題上，提出了一種兩階段粒子群優(yōu)化算法，實(shí)驗(yàn)部分與Al-hinai等［10］提出的混合遺傳算法進(jìn)行比較，結(jié)果表明該優(yōu)化算法具有更好的魯棒性和穩(wěn)定性。近年來(lái)，隨著可持續(xù)發(fā)展戰(zhàn)略的提出，越來(lái)越多的生產(chǎn)企業(yè)開(kāi)始轉(zhuǎn)向綠色制造，降低能源消耗已經(jīng)成了焦點(diǎn)問(wèn)題。Nouiri等［11］在解決機(jī)器故障下的動(dòng)態(tài)柔性作業(yè)車(chē)間調(diào)度問(wèn)題時(shí)，以最大完工時(shí)間最小、全局能耗最小為目標(biāo)，提出了一種基于粒子群優(yōu)化方法的綠色重調(diào)度方法，可以最大限度地減少時(shí)間和降低能耗。包哲人等［12］面向考慮能耗的柔性作業(yè)車(chē)間調(diào)度問(wèn)題提出了改進(jìn)離散蝙蝠算法，為避免算法早熟收斂設(shè)計(jì)了一種具有記憶能力的粒子變異操作，同時(shí)為了算法的搜索能力加入慣性權(quán)重策略，通過(guò)生產(chǎn)實(shí)例驗(yàn)證了算法的有效性。陳超等［13］以平均流經(jīng)時(shí)間和能耗為目標(biāo)建立柔性作業(yè)車(chē)間模型，針對(duì)此模型提出了遺傳算法與模擬退火混合算法（Genetic and Simulated Annealing Algorithm，GASA），采用滾動(dòng)窗口技術(shù)結(jié)合GASA來(lái)求解機(jī)器故障的動(dòng)態(tài)調(diào)度問(wèn)題并驗(yàn)證了算法的有效性。曹慶奎等［14］針對(duì)在機(jī)器故障情況下，同時(shí)考慮能耗和交貨期的柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度問(wèn)題，采用GASA進(jìn)行求解，以最大完工時(shí)間最小、能耗最小、客戶(hù)滿(mǎn)意度最大為目標(biāo)驗(yàn)證了其算法的有效性。李明等［15］針對(duì)考慮準(zhǔn)備時(shí)間的低碳FJSP，提出了新型帝國(guó)競(jìng)爭(zhēng)算法（Imperialist Competitive Algorithm，ICA），采用一種全新的同化方法和歸一化總成本新定義，在優(yōu)化關(guān)鍵目標(biāo)的同時(shí)持續(xù)改進(jìn)非關(guān)鍵目標(biāo)總能耗。呂聰?shù)龋?6］提出協(xié)作混合帝國(guó)算法，改進(jìn)了自適應(yīng)參數(shù)，提高了算法的收斂速度，并對(duì)不同階段采用多變異改革策略以提高算法的局部搜索效率，以及協(xié)作交流機(jī)制來(lái)提高算法的全局搜索能力，表明了協(xié)作混合帝國(guó)算法在求解柔性車(chē)間調(diào)度問(wèn)題上的穩(wěn)定性和優(yōu)越性。以上針對(duì)動(dòng)態(tài)調(diào)度問(wèn)題的研究，在國(guó)內(nèi)外學(xué)者的努力下研究成果豐富，但是針對(duì)機(jī)器故障重調(diào)度，并同時(shí)考慮能耗的研究相對(duì)較少。機(jī)器故障在實(shí)際車(chē)間生產(chǎn)過(guò)程中是很常見(jiàn)的動(dòng)態(tài)事件，在發(fā)生故障后找到合適的重調(diào)度方案是非常重要的。本文主要研究機(jī)器故障的柔性作業(yè)車(chē)間重調(diào)度問(wèn)題，對(duì)帝國(guó)競(jìng)爭(zhēng)算法進(jìn)行改進(jìn)，在同化和革命操作之后加入一個(gè)輪盤(pán)賭的選擇機(jī)制，對(duì)同化和革命后的個(gè)體重新進(jìn)行選擇，并結(jié)合事件驅(qū)動(dòng)策略對(duì)此類(lèi)重調(diào)度問(wèn)題進(jìn)行求解，驗(yàn)證算法的有效性。

1 問(wèn)題描述

柔性作業(yè)車(chē)間調(diào)度問(wèn)題可以描述為：將1到n個(gè)工件合理安排到m臺(tái)機(jī)器上進(jìn)行加工，每個(gè)工件有多道工序，其中每道工序都可以選擇不同的機(jī)器進(jìn)行加工，各工序所選機(jī)器不同，所需加工時(shí)長(zhǎng)也不相同。在實(shí)際生產(chǎn)過(guò)程中存在一些不確定性因素，導(dǎo)致會(huì)出現(xiàn)各種動(dòng)態(tài)事件，本文考慮的是機(jī)器故障的動(dòng)態(tài)事件。柔性作業(yè)車(chē)間動(dòng)態(tài)重調(diào)度研究存在以下幾個(gè)假設(shè)條件：

1）同一個(gè)工件在同一時(shí)刻只能由一臺(tái)機(jī)器進(jìn)行加工，一臺(tái)機(jī)器在同一時(shí)刻只允許有一個(gè)工件在該機(jī)器上加工。

2）每一道工序可以選擇由可加工機(jī)器集中的機(jī)器進(jìn)行加工，但是同一時(shí)刻只允許在一臺(tái)機(jī)器上加工。

3）每一個(gè)工件對(duì)于每道工序的加工有先后順序要求，只有某工件的前道工序加工完成后才能對(duì)該道工序進(jìn)行加工。

4）當(dāng)原調(diào)度已經(jīng)對(duì)工件的前幾道工序加工完成，再調(diào)度時(shí)只需加工該工件的后續(xù)工序。

柔性作業(yè)車(chē)間機(jī)器故障重調(diào)度問(wèn)題是在給出相關(guān)變量和決策變量，滿(mǎn)足約束條件和目標(biāo)函數(shù)的情況下，生成一個(gè)初始調(diào)度，在機(jī)器發(fā)生故障后，初始調(diào)度方案便不可行，此時(shí)應(yīng)重新調(diào)整調(diào)度方案，結(jié)合重調(diào)度策略生成重調(diào)度方案。

1.1 變量定義

本文的相關(guān)變量符號(hào)及定義如表1所示。

表1 變量描述Tab.1 Variables description

本文的決策變量有?ijk和δijhdk，其中，?ijk用于確定工序與機(jī)床的選擇關(guān)系；δijhdk用于確定工序在機(jī)器上的優(yōu)先加工順序。

1.2 約束條件

柔性作業(yè)車(chē)間調(diào)度問(wèn)題要滿(mǎn)足工件約束和機(jī)器約束：

式（1）表示一道工序只能在一臺(tái)機(jī)器上加工；式（2）表示同一工件只能在前一道工序加工完才能加工后一道工序；式（3）表示一臺(tái)機(jī)器在同一時(shí)刻只能加工一道工序。

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

本文主要研究的調(diào)度目標(biāo)為最小化最大完工時(shí)間（makespan）、最小能耗以及最小總延遲時(shí)間，如下所示：1）最小化最大完工時(shí)間。

2）最小能耗。

采用文獻(xiàn)［13］中的加工能耗E的表示方法，每臺(tái)機(jī)器上的第一個(gè)工件的開(kāi)始加工時(shí)刻就是該臺(tái)機(jī)器的開(kāi)工時(shí)刻，機(jī)器一直保持著耗能狀態(tài)，直到該機(jī)器上所有工件都加工完畢，因此能耗的數(shù)學(xué)模型為式（5）所示：

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

本文總延遲時(shí)間主要是計(jì)算機(jī)器故障前后，兩次調(diào)度的最小化最大完工時(shí)間差，總延遲時(shí)間的數(shù)學(xué)模型如式（6）所示：

由于三個(gè)目標(biāo)的量綱不統(tǒng)一，需要進(jìn)行歸一化處理，將各目標(biāo)數(shù)據(jù)轉(zhuǎn)換到［0，1］內(nèi)，計(jì)算過(guò)程如式（7）所示：

其中：x*表示歸一化之后的目標(biāo)值，x為當(dāng)前目標(biāo)值，xmax為全局目標(biāo)最大值，xmin為全局目標(biāo)最小值。

對(duì)本文的三個(gè)目標(biāo)進(jìn)行歸一化處理后，再采用線(xiàn)性加權(quán)和法，將三個(gè)目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)變成單目標(biāo)優(yōu)化問(wèn)題，如式（8）所示：

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

動(dòng)態(tài)重調(diào)度策略，是指在系統(tǒng)生產(chǎn)過(guò)程突發(fā)情況下將采取應(yīng)對(duì)措施來(lái)解決發(fā)生的異常事件。一般用到的策略方法有三種，分為事件驅(qū)動(dòng)、周期驅(qū)動(dòng)和周期與事件的混合驅(qū)動(dòng)，本文采用事件驅(qū)動(dòng)策略。

當(dāng)機(jī)器出現(xiàn)故障時(shí)，確定機(jī)器修復(fù)時(shí)間T，故障點(diǎn)前已經(jīng)加工過(guò)的工序保持不動(dòng)，找出故障點(diǎn)后未加工的工序，并對(duì)其用帝國(guó)競(jìng)爭(zhēng)算法進(jìn)行重新調(diào)度，故障機(jī)器的開(kāi)工時(shí)間為修復(fù)后的時(shí)間，即故障時(shí)刻加上故障時(shí)長(zhǎng)，其余機(jī)器的開(kāi)工時(shí)間為當(dāng)前正在加工工序的完成時(shí)間。機(jī)器發(fā)生故障后，在該機(jī)器上未進(jìn)行加工的工件將被分配到其他機(jī)器上進(jìn)行加工。機(jī)器故障重調(diào)度的具體流程如圖1所示。

圖1 機(jī)器故障重調(diào)度流程Fig.1 Flow of reschedulingwith machinebreakdown

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

3.1 基本帝國(guó)競(jìng)爭(zhēng)算法

帝國(guó)競(jìng)爭(zhēng)算法是一種受帝國(guó)競(jìng)爭(zhēng)行為啟發(fā)的新的智能優(yōu)化算法，它與粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法、蟻群優(yōu)化（Ant Colony Optimization，ACO）算法等一樣，都屬于基于群體的隨機(jī)優(yōu)化搜索算法。帝國(guó)競(jìng)爭(zhēng)算法比PSO和GA收斂速度快，具有較強(qiáng)的全局收斂性，并且同化和革命步驟又保證了算法的局部搜索能力，因此在求解柔性作業(yè)車(chē)間調(diào)度問(wèn)題上有一定的優(yōu)勢(shì)。帝國(guó)競(jìng)爭(zhēng)算法在解決各種實(shí)際的優(yōu)化問(wèn)題上具有廣泛應(yīng)用，本文將其應(yīng)用在解決機(jī)器故障重調(diào)度問(wèn)題上。

ICA的基本過(guò)程為：產(chǎn)生初始帝國(guó)、同化、革命、帝國(guó)競(jìng)爭(zhēng)和帝國(guó)消亡。ICA的流程如圖2所示，具體步驟為：

圖2 ICA流程Fig.2 Flowchart of ICA

步驟1 將隨機(jī)產(chǎn)生的Npop個(gè)初始解作為初始國(guó)家，并計(jì)算每個(gè)國(guó)家的成本cn。

步驟2 構(gòu)建初始帝國(guó)。選擇成本較小的Nimp個(gè)國(guó)家作為殖民國(guó)家imp，剩余的作為殖民地Col，殖民地的個(gè)數(shù)NCol與殖民國(guó)家個(gè)數(shù)Nimp之和等于初始解的個(gè)數(shù)Npop。確定殖民國(guó)家所能分到的殖民地?cái)?shù)量，隨機(jī)分配殖民地給各殖民國(guó)家，此時(shí)各殖民國(guó)家與其殖民地組成初始帝國(guó)PEmp。殖民國(guó)家所擁有的殖民地?cái)?shù)量與其勢(shì)力成正比，因此要先計(jì)算每個(gè)殖民國(guó)家的標(biāo)準(zhǔn)化成本Cn，如式（9）所示：

殖民國(guó)家的成本越小，勢(shì)力就越大，每個(gè)殖民國(guó)家的標(biāo)準(zhǔn)化勢(shì)力pn如式（10）所示：

第n個(gè)殖民國(guó)家所擁有的初始殖民地?cái)?shù)量NCn如式（11）所示：

其中round是將小數(shù)四舍五入成整數(shù)的函數(shù)。

步驟3 同化和革命。將殖民地向其所在殖民國(guó)家移動(dòng)，即殖民地都趨向于殖民國(guó)家這個(gè)最優(yōu)解；革命的目的是防止同化后的算法過(guò)早收斂。同化操作分為機(jī)器的選擇和工序排序兩部分，機(jī)器的選擇部分采用多點(diǎn)交叉變異的方法，具體操作為：隨機(jī)選取r個(gè)位置，將殖民國(guó)家的r個(gè)位置的信息替換到殖民地中的對(duì)應(yīng)位置，其余位置信息保持不變；工序排序部分采用工件交換的方式，將殖民地的加工工序部分與殖民國(guó)家的加工工序部分進(jìn)行信息交換，更新殖民地的加工工序部分。革命操作同樣分為機(jī)器的選擇部分和工序排序部分，在機(jī)器選擇部分，隨機(jī)選取某個(gè)加工機(jī)器，然后選擇對(duì)應(yīng)機(jī)器集中的其他任一機(jī)器代替它；在工序排序部分，隨機(jī)選擇兩個(gè)位置上的工序進(jìn)行信息交換。同化和革命后的新帝國(guó)為SEmp。

步驟4 殖民國(guó)家更新。當(dāng)殖民地經(jīng)過(guò)同化和革命后，將殖民國(guó)家和所有殖民地的成本進(jìn)行比較：若有殖民地的成本比殖民國(guó)家要小，則該殖民地替代殖民國(guó)家成為該帝國(guó)內(nèi)新的殖民國(guó)家；否則，殖民國(guó)家不發(fā)生變化，更新后的帝國(guó)為Emp。

步驟5 帝國(guó)競(jìng)爭(zhēng)。計(jì)算所有帝國(guó)的總成本，較弱帝國(guó)需選出一個(gè)最弱殖民地，較強(qiáng)帝國(guó)可以來(lái)爭(zhēng)奪殖民地，帝國(guó)越強(qiáng)獲得該殖民地的概率越大。每個(gè)帝國(guó)的總成本TCn計(jì)算如式（12）所示，將每個(gè)帝國(guó)的總成本進(jìn)行標(biāo)準(zhǔn)化處理，如式（13）所示，每個(gè)帝國(guó)占有弱殖民地的概率Pn計(jì)算如式（14）所示：

其中：f（impn）表示第n個(gè)帝國(guó)的殖民國(guó)家的成本，f（Coli）表示第i個(gè)殖民地的成本，α為殖民地影響因子，0<α<1，NTCn表示第n個(gè)帝國(guó)的標(biāo)準(zhǔn)化成本。

步驟6 帝國(guó)消亡。當(dāng)某個(gè)帝國(guó)沒(méi)有任何殖民地時(shí)，此時(shí)該帝國(guó)消亡。

步驟7 若終止條件成立，則算法結(jié)束；否則回到步驟3。

3.2 編碼和解碼

在ICA中，每一個(gè)國(guó)家代表一組柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度問(wèn)題的可行方案，結(jié)合柔性作業(yè)車(chē)間調(diào)度問(wèn)題特點(diǎn)設(shè)計(jì)兩段式實(shí)數(shù)編碼方式對(duì)國(guó)家個(gè)體進(jìn)行編輯。

以圖3為例，每個(gè)個(gè)體為一串整數(shù)，總長(zhǎng)度為2L，L為所有工序的個(gè)數(shù)，Oi表示工件i的工序數(shù)。左半部分為加工機(jī)器的選擇，按照工件1、工件2和工件3的工序順序進(jìn)行排列，每個(gè)整數(shù)表示對(duì)應(yīng)工序可選加工機(jī)器的排列序號(hào)，第一個(gè)整數(shù)3為工序O11可選機(jī)器集｛M2，M3，M4｝的第3個(gè)機(jī)器即M4。右半部分為加工工序的排序，每個(gè)整數(shù)代表工件號(hào)，第1次出現(xiàn)表示該工件的第1道工序，第2次出現(xiàn)表示該工件的第2道工序，以此類(lèi)推，圖3中加工工序所表示的工序順序?yàn)椋∣21，O11，O31，O12，O32，O22）。

圖3 編碼表達(dá)示意圖Fig.3 Schematic diagram of codingexpression

對(duì)國(guó)家個(gè)體進(jìn)行解碼操作時(shí)，首先對(duì)個(gè)體的前半部分即機(jī)器部分從左到右依次進(jìn)行解碼，轉(zhuǎn)成對(duì)應(yīng)的機(jī)器并確定各工序在對(duì)應(yīng)機(jī)器上的加工時(shí)間，然后對(duì)個(gè)體的后半部分即工序部分進(jìn)行解碼，解碼成活動(dòng)調(diào)度。

3.3 改進(jìn)ICA

帝國(guó)競(jìng)爭(zhēng)算法中的同化是通過(guò)殖民地向殖民國(guó)家的移動(dòng)來(lái)實(shí)現(xiàn)，相當(dāng)于是一個(gè)尋優(yōu)過(guò)程增強(qiáng)了算法的局部搜索能力，但是在傳統(tǒng)的帝國(guó)競(jìng)爭(zhēng)算法中并沒(méi)有物競(jìng)天擇的進(jìn)化規(guī)律，在ICA求解調(diào)度時(shí)為了能夠提高求解質(zhì)量、提高算法的尋優(yōu)能力，因此本文參照遺傳算法中的遺傳和變異對(duì)帝國(guó)競(jìng)爭(zhēng)算法進(jìn)行改進(jìn)，在初始帝國(guó)進(jìn)行同化和革命之后增加一個(gè)選擇機(jī)制的步驟，可以使初始帝國(guó)中的優(yōu)秀基因得以保留，更新后的帝國(guó)質(zhì)量更優(yōu)，更加貼近最優(yōu)解。選擇機(jī)制的具體操作如下：

步驟1 首先將初始帝國(guó)PEmp中的第一個(gè)帝國(guó)PEmp（1）的所有個(gè)體與其同化和改革后的SEmp中對(duì)應(yīng)的第一個(gè)帝國(guó)SEmp（1）中的所有個(gè)體放在一起。

步驟2 采用輪盤(pán)賭的方法從合并的帝國(guó)中選出一半數(shù)量的個(gè)體，將其作為一個(gè)新的帝國(guó)Emp（1）。本文采用輪盤(pán)賭的個(gè)體概率值為各個(gè)國(guó)家的成本值的倒數(shù)，成本值越小則被選到的概率越大，否則概率越小。

步驟3 從新帝國(guó)中選出成本值最低的國(guó)家作為殖民國(guó)家，剩余的國(guó)家則淪為該殖民國(guó)家的殖民地。

步驟4 接著轉(zhuǎn)到步驟1進(jìn)行初始帝國(guó)PEmp中的第二個(gè)帝國(guó)PEmp（2）和同化和改革后的SEmp中對(duì)應(yīng)的第二個(gè)帝國(guó)SEmp（2）的合并，以此類(lèi)推，直到所有帝國(guó)全部選擇完成，最終生成新的帝國(guó)Emp，此時(shí)選擇機(jī)制結(jié)束。

改進(jìn)帝國(guó)競(jìng)爭(zhēng)算法選擇機(jī)制的示意圖如圖4所示。

圖4 選擇機(jī)制示意圖Fig.4 Schematic diagram of selection mechanism

改進(jìn)后的帝國(guó)競(jìng)爭(zhēng)算法的流程如圖5所示。

圖5 改進(jìn)ICA流程Fig.5 Flow of improved ICA

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

采用改進(jìn)ICA對(duì)柔性作業(yè)車(chē)間機(jī)器故障重調(diào)度算例進(jìn)行仿真實(shí)驗(yàn)，并隨機(jī)假設(shè)三種機(jī)器發(fā)生故障的場(chǎng)景，得出最佳調(diào)度方案，驗(yàn)證該算法求解柔性作業(yè)車(chē)間機(jī)器故障重調(diào)度問(wèn)題的有效性。

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

本文的實(shí)驗(yàn)算例來(lái)自洛陽(yáng)某鋼具廠生產(chǎn)車(chē)間，經(jīng)過(guò)簡(jiǎn)化為8×8的柔性作業(yè)調(diào)度問(wèn)題，如表2所示，有8個(gè)工件，8臺(tái)機(jī)器。表3為每臺(tái)機(jī)器的加工能耗，表4為假設(shè)的三種機(jī)器故障場(chǎng)景，這三種場(chǎng)景分別獨(dú)立發(fā)生。

表2 仿真實(shí)例數(shù)據(jù)Tab.2 Dataof simulation examples

表3 機(jī)器能耗Tab.3 Machineenergy consumption

表4 三種機(jī)器故障場(chǎng)景Tab.4 Three scenarios of machinebreakdowns

使用Matlab 2017b對(duì)該算例進(jìn)行仿真實(shí)驗(yàn)，本文提出的算法參數(shù)設(shè)定為：最大迭代次數(shù)為50，國(guó)家個(gè)數(shù)為100，帝國(guó)個(gè)數(shù)為10，a、b、c分別設(shè)為0.3、0.3、0.4。針對(duì)同化系數(shù)、革命概率和競(jìng)爭(zhēng)概率三個(gè)參數(shù)，采用田口方法以及Minitab軟件進(jìn)行多因子正交實(shí)驗(yàn)，正交表如表5所示，每個(gè)參數(shù)有3個(gè)水平，共有9種不同的組合，對(duì)該正交表進(jìn)行田口分析得到的均值主效應(yīng)圖如圖6所示，最后得出同化系數(shù)、革命概率和競(jìng)爭(zhēng)概率的參數(shù)分別為0.7、0.05、1。

表5 正交表Tab.5 Orthogonal table

圖6 參數(shù)均值主效應(yīng)圖Fig.6 Main effect plots of parameter means

4.2 實(shí)驗(yàn)結(jié)果

首先在初始時(shí)刻采用改進(jìn)ICA對(duì)問(wèn)題進(jìn)行調(diào)度，得到初始方案，如圖7所示為迭代最優(yōu)解的甘特圖，最大完工時(shí)間為26 min，能耗為624.3 J。圖7中相同顏色代表同一工件，其中顏色塊上的數(shù)字表示為：第一個(gè)數(shù)字是工件號(hào)，后兩位數(shù)字表示工序號(hào)，如“101”表示工件1的第一道工序，“402”表示工件4的第二道工序。

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

場(chǎng)景1是機(jī)器3在0時(shí)刻發(fā)生故障，故障修復(fù)時(shí)刻為15，進(jìn)行重調(diào)度后的甘特圖如圖8所示，最大完工時(shí)間為27 min，總延遲時(shí)間為1 min，能耗為722.8 J。圖8中數(shù)字表示工件號(hào)，相同顏色代表同一工件，機(jī)器3上，［0，15］時(shí)間段為故障區(qū)間。

圖8 機(jī)器3發(fā)生故障后的重調(diào)度甘特圖Fig.8 Gantt chart of rescheduling after machine 3 breakdown

場(chǎng)景2是機(jī)器6在5時(shí)刻發(fā)生故障，故障修復(fù)時(shí)刻為10，進(jìn)行重調(diào)度后的甘特圖如圖9所示，最大完工時(shí)間為27 min，總延遲時(shí)間為1 min，能耗為757.6 J。圖9中標(biāo)有數(shù)字的白色部分表示機(jī)器發(fā)生故障時(shí)刻之前的工序保持原調(diào)度不變，有顏色的部分表示機(jī)器發(fā)生故障后重新進(jìn)行調(diào)度的工序。

圖9 機(jī)器6發(fā)生故障后的重調(diào)度甘特圖Fig.9 Gantt chart of reschedulingafter machine6 breakdown

場(chǎng)景3是機(jī)器7在10時(shí)刻發(fā)生故障，故障修復(fù)時(shí)刻為25，重調(diào)度后的甘特圖如圖10所示，最大完工時(shí)間為27 min，總延遲時(shí)間為1 min，能耗為707.3 J。

為進(jìn)一步驗(yàn)證改進(jìn)ICA的有效性，假設(shè)機(jī)器2、機(jī)器5和機(jī)器6分別在0時(shí)刻發(fā)生故障，并且短時(shí)間內(nèi)無(wú)法修復(fù)，針對(duì)該三種機(jī)器故障情況采用GASA［13］、改進(jìn)GA［8］和改進(jìn)ICA分別進(jìn)行求解并對(duì)比，三種算法求出的三種優(yōu)化目標(biāo)數(shù)據(jù)如表6所示，從表中可以看出該改進(jìn)ICA與其他兩種算法相比實(shí)驗(yàn)結(jié)果更好，驗(yàn)證了該算法的有效性。

表6 實(shí)驗(yàn)數(shù)據(jù)對(duì)比Tab.6 Comparison of experimental data

故障機(jī)器D/min 2 5 6算法GASA改進(jìn)GA改進(jìn)ICA GASA改進(jìn)GA改進(jìn)ICA GASA改進(jìn)GA改進(jìn)ICA C max/min 28 31 27 30 30 27 29 32 29 E/J 786.1 792.5 712.2 807.9 833.9 740.6 780.4 817.9 723.6 251441363

為了驗(yàn)證算法求解的穩(wěn)定性，分別采用三種算法對(duì)上述機(jī)器2發(fā)生故障的情況進(jìn)行求解，表7為三種算法運(yùn)行10次的各優(yōu)化目標(biāo)的平均值和方差，從表7中可以看出，改進(jìn)ICA與GASA、改進(jìn)GA相比各優(yōu)化目標(biāo)的方差最小，表明該改進(jìn)ICA求解的穩(wěn)定性最好。

表7 三種算法的性能對(duì)比Tab.7 Performance comparison of threealgorithms

針對(duì)上述假設(shè)的機(jī)器故障情況的實(shí)驗(yàn)研究以及與遺傳算法進(jìn)行比較，可以得出的結(jié)論是，故障后的重調(diào)度方案的最大完工時(shí)間、總延遲時(shí)間以及能耗都控制在一個(gè)較好的范圍之內(nèi)，符合實(shí)際生產(chǎn)需要。

5 結(jié)語(yǔ)

本文針對(duì)柔性作業(yè)車(chē)間機(jī)器故障的動(dòng)態(tài)事件，對(duì)帝國(guó)競(jìng)爭(zhēng)算法進(jìn)行改進(jìn)，加入選擇機(jī)制操作，結(jié)合事件驅(qū)動(dòng)策略以及最大完工時(shí)間、能耗和總延遲時(shí)間三個(gè)目標(biāo)函數(shù)，對(duì)該類(lèi)動(dòng)態(tài)問(wèn)題進(jìn)行求解。對(duì)提出的三種不同機(jī)器故障的場(chǎng)景進(jìn)行實(shí)驗(yàn)仿真分析，得出的結(jié)果較為符合實(shí)際生產(chǎn)需要，并將改進(jìn)ICA與兩種不同的算法進(jìn)行比較，驗(yàn)證了該算法的有效性和可行性。

柔性作業(yè)車(chē)間生產(chǎn)過(guò)程中容易受到各種復(fù)雜因素的影響，下一步將繼續(xù)對(duì)帝國(guó)競(jìng)爭(zhēng)算法進(jìn)行改進(jìn)，并運(yùn)用到其他類(lèi)型的動(dòng)態(tài)調(diào)度中，如插入緊急訂單、工件延誤等動(dòng)態(tài)事件。