王彥杰,向鳳紅

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院,云南 昆明 650000)

0 引 言

生產(chǎn)調(diào)度的出現(xiàn),讓人們脫離了原始的生產(chǎn)模式,解放了勞動(dòng)力。但隨著社會(huì)的發(fā)展,單一的生產(chǎn)調(diào)度模式,已經(jīng)不符合人們?nèi)找嬖鲩L(zhǎng)的需求,需尋求更加有效的生產(chǎn)制造方式[1]。

柔性作業(yè)車間調(diào)度問(wèn)題(FJSP)是傳統(tǒng)的作業(yè)車間調(diào)度問(wèn)題(job shop scheduling problem, JSP)的擴(kuò)展[2]。柔性作業(yè)車間調(diào)度的不確定性和復(fù)雜性,適合現(xiàn)代多變、復(fù)雜的生產(chǎn)環(huán)境,同時(shí)也使得對(duì)該類問(wèn)題的研究變得困難,促使越來(lái)越多的學(xué)者加入到調(diào)度生產(chǎn)模式研究中來(lái)。

目前,對(duì)于柔性作業(yè)車間調(diào)度問(wèn)題的研究方法主要是利用智能算法模擬實(shí)際生產(chǎn),尋求最好的調(diào)度方案。智能算法的出現(xiàn)為解決該問(wèn)題提供了工具,極大程度上解決了復(fù)雜性強(qiáng)、問(wèn)題規(guī)模大的FJSP問(wèn)題。

SINGH M R等人[3]在傳統(tǒng)粒子群算法中加入了量子行為策略,提出了一種混合量子行為粒子群算法,以此來(lái)求解柔性作業(yè)車間調(diào)度問(wèn)題,但該算法對(duì)于初始種群的優(yōu)化存在明顯不足。喬兵等人[4]在遺傳算法中設(shè)計(jì)了新的基因編碼方式,對(duì)不合法基因進(jìn)行了修復(fù),求解了以最大最小完工時(shí)間為優(yōu)化目標(biāo)的柔性作業(yè)車間調(diào)度問(wèn)題;但該算法優(yōu)化后增加了完成加工的時(shí)間,且只針對(duì)不合法基因進(jìn)行優(yōu)化,有一定的局限性。賀仁杰等人[5]利用不同種群之間的進(jìn)化方式以及調(diào)整參數(shù)設(shè)置,以此來(lái)推演優(yōu)秀種群的演進(jìn)過(guò)程,并且根據(jù)種群之間不同方式的演進(jìn)過(guò)程和資源競(jìng)爭(zhēng),使種群之間的信息得以共享,從而推動(dòng)了算法整體的進(jìn)化,同時(shí)提出了通過(guò)知識(shí)型協(xié)同進(jìn)化算法來(lái)求解柔性作業(yè)車間調(diào)度問(wèn)題的方法;但該算法無(wú)法在大規(guī)模實(shí)例中進(jìn)行準(zhǔn)確優(yōu)化,并且存在需要調(diào)整的參數(shù)多等問(wèn)題。MASTROLOLLI M等人[6]利用禁忌搜索算法與新領(lǐng)域結(jié)構(gòu)相結(jié)合的方式,增加了求解FJSP問(wèn)題時(shí)算法搜索的效率與范圍,避免了算法過(guò)早陷入局部最優(yōu);但該算法存在著運(yùn)行時(shí)間過(guò)長(zhǎng)、計(jì)算復(fù)雜度較高等不足。

上述文獻(xiàn)說(shuō)明,目前智能算法雖然已經(jīng)得到了廣泛的應(yīng)用,但蟻獅算法求解FJSP問(wèn)題的可行性國(guó)內(nèi)外還無(wú)人能證明。同時(shí)針對(duì)傳統(tǒng)蟻獅算法存在的不足之處,急需有一種計(jì)算復(fù)雜度低、求解進(jìn)度高、調(diào)參少、能夠解決實(shí)際大規(guī)模問(wèn)題的改進(jìn)蟻獅算法,以此來(lái)求解FJSP問(wèn)題。

筆者嘗試使用蟻獅優(yōu)化[7](ALO)算法求解以最小最大完工時(shí)間為目標(biāo)的FJSP問(wèn)題。首先,提出基于混沌映射與競(jìng)標(biāo)賽選擇的混合策略,生成初始種群;其次,引入傳統(tǒng)遺傳算法中的最簡(jiǎn)單交叉變異策略,設(shè)計(jì)工序和機(jī)器加工選擇的交叉變異策略;最后,利用Brandimarte基準(zhǔn)算例進(jìn)行實(shí)驗(yàn)對(duì)比分析,對(duì)該算法求解FJSP問(wèn)題的有效性以及算法的性能進(jìn)行驗(yàn)證。

1 柔性作業(yè)車間調(diào)度問(wèn)題

1.1 問(wèn)題描述

FJSP包括兩個(gè)子問(wèn)題:(1)對(duì)加工工序進(jìn)行合理地機(jī)器分配;(2)對(duì)所選加工機(jī)器上進(jìn)行不同加工工件的加工工序進(jìn)行緊前緊后安排。

具體描述如下:柔性作業(yè)車間調(diào)度問(wèn)題是n個(gè)工件(j1,j2,j3,…jn)可以在m臺(tái)機(jī)器(m1,m2,m3,…mn)上加工,工件i(i=1,2,3,…,n)有qi道工序,每道工序所用的加工時(shí)間為t,允許工序可以在多個(gè)機(jī)器上進(jìn)行加工操作,根據(jù)所選擇的加工機(jī)器的不同,加工時(shí)間也不同。

調(diào)度問(wèn)題研究的實(shí)質(zhì)就是解決工件工序是否可以在某幾臺(tái)機(jī)器上加工,根據(jù)選擇加工機(jī)器的不同,所產(chǎn)生的加工時(shí)間也不同;為實(shí)現(xiàn)最理想化的生產(chǎn),對(duì)工件的工序進(jìn)行安排以及選擇合適的加工機(jī)器,是整個(gè)調(diào)度方案的重點(diǎn)。

在建立問(wèn)題模型之前,需要對(duì)加工過(guò)程中進(jìn)行一點(diǎn)條件約束,具體如下:

(1)機(jī)器在某時(shí)刻有且只有一個(gè)工件進(jìn)行加工;

(2)工件工序在加工過(guò)程中,僅能選擇一臺(tái)機(jī)器進(jìn)行加工操作;

(3)工件工序加工開始就不會(huì)停止,直到工件工序完成加工;

(4)待加工的工件,在選擇加工時(shí)無(wú)主次之分,僅根據(jù)調(diào)度方案安排工件的加工;

(5)相同工件的不同工序需考慮加工先后順序。

1.2 模型建立

為證明蟻獅算法求解柔性作業(yè)車間調(diào)度問(wèn)題的有效性,筆者以最小最大完工時(shí)間(Cm)為目標(biāo),建立單目標(biāo)柔性作業(yè)車間調(diào)度模型。

在其數(shù)學(xué)模型中,目標(biāo)值為:

(1)

表示每個(gè)工件的每道工序加工開始就不能中斷的為:

(2)

表示確認(rèn)是否可以在機(jī)器上進(jìn)行加工,為0～1決策變量的為:

(3)

表示同一個(gè)工件的不同工序之間加工時(shí)有緊前緊后關(guān)系的為:

Ci(j+1)≥Pij,?i,j;

(4)

表示工件工序加工時(shí)間不得超過(guò)該工件所有工序完成的加工時(shí)間的為:

(5)

表示工件工序的加工時(shí)間不得超過(guò)最大完工時(shí)間的為:

Pj≤Cm

(6)

表示每個(gè)工件的不同工序可以循環(huán)在同一個(gè)機(jī)器上進(jìn)行加工的為:

(7)

2 基于ALO單目標(biāo)柔性作業(yè)車間調(diào)度

2.1 蟻獅優(yōu)化算法

蟻獅優(yōu)化(ALO)算法通過(guò)模擬自然界中一種生物—蟻獅狩獵螞蟻的行為,對(duì)目標(biāo)函數(shù)優(yōu)化求解,借助于蟻獅周邊螞蟻的隨機(jī)游走,以保證該算法的全局搜索能力。與粒子群等算法不同,該算法中有兩個(gè)種群:蟻獅和螞蟻,通過(guò)蟻獅對(duì)螞蟻的捕獲,實(shí)現(xiàn)種群的進(jìn)化。ALO算法具有求解進(jìn)度高、調(diào)參少等優(yōu)點(diǎn),得到了廣泛的應(yīng)用[8-12],但無(wú)人證明其求解柔性作業(yè)車間調(diào)度問(wèn)題的有效性。

筆者嘗試使用改進(jìn)后的蟻獅算法求解柔性作業(yè)車間調(diào)度問(wèn)題,證明其有效性。

2.2 蟻獅算法的數(shù)學(xué)模型

2.2.1 螞蟻的隨機(jī)游走及歸一化處理

為保證螞蟻隨機(jī)游走在可行域的范圍內(nèi)完成搜索,筆者將進(jìn)行歸一化處理,使其運(yùn)動(dòng)范圍在可行域內(nèi),如下式所示:

X(t)=[0,cumsum(2r(t1)-1),
cumsum(2r(t2)-1),…,cum(2r(tn)-1)]

(8)

(9)

(10)

2.2.2 陷阱對(duì)螞蟻隨機(jī)游走的影響

筆者設(shè)計(jì)陷入陷阱邊緣的螞蟻運(yùn)動(dòng)過(guò)程受陷阱的影響,保證陷入陷阱的螞蟻能夠被蟻獅所捕獲,如下式所示:

(11)

2.2.3 輪盤賭策略捕獲方式

利用式(1)去計(jì)算適應(yīng)度,根據(jù)蟻獅適應(yīng)度大小利用輪盤賭策略來(lái)選擇蟻獅,適應(yīng)度越高的蟻獅有更高的捕捉螞蟻的機(jī)會(huì)。

為提高算法的收斂速度,筆者將螞蟻隨機(jī)游走的范圍隨迭代次數(shù)的增加而縮小,其數(shù)學(xué)模型如下:

(12)

(13)

(14)

式中:t—當(dāng)前迭代次數(shù);w—隨迭代次數(shù)而動(dòng)態(tài)調(diào)整的參數(shù);T—最大迭代次數(shù)。

2.2.4 捕獲螞蟻后重筑陷阱

當(dāng)蟻獅捕獲螞蟻后,需重筑陷阱去捕獲螞蟻。若某只螞蟻的適應(yīng)度高于蟻獅的適應(yīng)度時(shí),則認(rèn)為被蟻獅捕獲,更新蟻獅位置,即:

(15)

2.2.5 精英更新

筆者利用輪盤賭選擇的蟻獅和精英蟻獅的雙重?fù)駜?yōu)措施,對(duì)當(dāng)前螞蟻隨機(jī)運(yùn)動(dòng)產(chǎn)生影響,將適應(yīng)度最優(yōu)的蟻獅作為當(dāng)前最優(yōu)的精英個(gè)體進(jìn)行確定,并儲(chǔ)存其信息,即:

(16)

2.3 蟻獅算法流程框圖

不同于其他群智能算法,蟻獅算法在算法初始種群中引入了2個(gè)種群,即蟻獅種群和螞蟻種群。筆者將能夠抓住螞蟻的蟻獅,即適應(yīng)度最高、靠近最優(yōu)解的蟻獅定義為精英蟻獅,運(yùn)用輪盤賭策略選擇一個(gè)適應(yīng)度較好的蟻獅,讓選擇好的蟻獅和精英蟻獅同時(shí)進(jìn)行捕獵,循環(huán)該過(guò)程,直到從中找到最好的解。

蟻獅算法流程框圖如圖1所示。

圖1 蟻獅算法流程框圖

2.4 編碼解碼

2.4.1 編碼

由于傳統(tǒng)的JSP問(wèn)題只考慮工件工序的加工順序,一般只是對(duì)工件工序進(jìn)行設(shè)計(jì)編碼,但是FJSP調(diào)度問(wèn)題不僅要設(shè)計(jì)工序的加工方案,使其合理安排加工,不會(huì)出現(xiàn)因加工順序安排出錯(cuò),而導(dǎo)致加工沖突的事件發(fā)生,還要根據(jù)約束以及調(diào)度方案為每道工序設(shè)計(jì)合理的可加工機(jī)器,避免機(jī)器利用率不高,以及加工工序在機(jī)器上加工時(shí)出現(xiàn)沖突的情況發(fā)生,僅對(duì)工序的編碼設(shè)計(jì)無(wú)法達(dá)到合理安排以及解決該問(wèn)題。

因此,筆者使用基于工序和機(jī)器雙層實(shí)數(shù)編碼規(guī)則,該編碼具體是針對(duì)工序以及加工機(jī)器兩部分進(jìn)行編碼設(shè)計(jì),達(dá)到合理解決加工工序間和機(jī)器間的沖突以及利用率不夠問(wèn)題的目的,且最終得到了正確可行的調(diào)度解。

為便于讀者理解,筆者提出一個(gè)3×5的MOFJSP例子?，F(xiàn)有工序集為O1={O11,O12,O13},O2={O21,O22},O3={O31,O32,O33};機(jī)器為M={M1,M2,M3,M4,M5}。

擴(kuò)展的基于工序和機(jī)器的雙層編碼方式如圖2所示。

圖2 擴(kuò)展的基于工序和機(jī)器雙層編碼方式

圖2中:表示工件2的第1道工序可以在機(jī)器4上加工,工件1的第1道工序可以在機(jī)器3上加工,其表示的序列為:(O21,M4),(O11,M3),(O31,M1),(O12,M1),(O32,M2),(O13,M5),(O22,M2),(O33,M5)。

其中:基于工序編碼的基因串是確定各個(gè)工件工序的加工順序;基于機(jī)器編碼的基因串為每個(gè)工件加工工序所對(duì)應(yīng)的加工機(jī)器,機(jī)器的基因長(zhǎng)度與工序的總數(shù)相等。

2.4.2 解碼

解碼是為了對(duì)設(shè)計(jì)的編碼信息以及編碼規(guī)則所形成的調(diào)度方案,利用甘特圖的形式清晰地看出其是否合理安排了加工過(guò)程,根據(jù)甘特圖所表示出來(lái)的問(wèn)題進(jìn)行進(jìn)一步修改,直到找尋到最佳的調(diào)度方案,且不同解碼設(shè)計(jì)方案也會(huì)產(chǎn)生不同的調(diào)度解,影響著最終調(diào)度結(jié)果的優(yōu)越性。

因此,筆者利用插入式貪婪算法,根據(jù)編碼信息以及編碼規(guī)則進(jìn)行解碼操作。其具體過(guò)程為:找尋到加工機(jī)器的空閑時(shí)間,判斷在該機(jī)器加工空閑時(shí)間里是否可以安排加工其他工件的工序。

基于插入式貪婪算法解碼得到的甘特圖如圖3所示。

圖3 基于插入式貪婪算法解碼得到的甘特圖

圖3中:利用插入式貪婪算法對(duì)圖2編碼方式進(jìn)行解碼,得到可行解的甘特圖,其中,圖2編碼方式的加工時(shí)間為[4,3,7,2,6,8,3,5];

機(jī)器5上共可以加工兩道工序,即O13與O33,判斷工序O13后是否有空閑時(shí)間,可將工序O33前插進(jìn)行加工操作;機(jī)器2可加工兩道工序O32與O22,判斷O32之后有無(wú)大面積的空閑時(shí)間,將工序O32后插進(jìn)行加工操作,這種操作可以使機(jī)器之間利用均衡,達(dá)到理想的加工效果。

2.5 混合策略的種群初始化

初始化種群的質(zhì)量往往影響著最終求解結(jié)果。在蟻獅算法中,存在兩個(gè)種群,即蟻獅種群和螞蟻種群,且這兩個(gè)種群都是隨機(jī)生成的,這樣隨機(jī)生成的種群質(zhì)量無(wú)法保證,進(jìn)而影響算法的有效性。

在單目標(biāo)柔性作業(yè)車間調(diào)度研究中,為解決蟻獅算法種群質(zhì)量不佳的問(wèn)題,筆者采用混沌映射策略以及錦標(biāo)賽選擇方式相結(jié)合的混合策略,生成初始種群改進(jìn)蟻獅算法。

混沌映射是用于生成混沌序列,在確定的系統(tǒng)中生成隨機(jī)序列,增強(qiáng)初始種群的混亂程度,即使初始始種群分布均勻。筆者使用混沌映射策略中的Logistic,即蟲口映射方式,其遞推方程如下:

zk+1=μzk(1-zk)

(17)

式中:zk—一數(shù)列。

其中:μ∈[0,4]。

筆者設(shè)定種群大小為100,其中,種群包括蟻獅種群和螞蟻種群。利用混沌映射策略隨機(jī)初始化生成蟻獅種群與螞蟻種群,其大小分別為50,將隨機(jī)生成的蟻獅種群和螞蟻種群分別進(jìn)行排序,取排序后的蟻獅種群中前1/5,即10個(gè)最優(yōu)種群個(gè)體,作為下一代蟻獅種群。

為保證蟻獅種群不變,筆者在排序和選取后剩下的90個(gè)種群個(gè)體中,利用錦標(biāo)賽選擇方式,根據(jù)目標(biāo)函數(shù)公式計(jì)算其適應(yīng)度,挑選適應(yīng)度最好的種群個(gè)體,以此來(lái)彌補(bǔ)下一代蟻獅種群中空缺的40個(gè)種群個(gè)體。這樣可保證種群的多樣性和種群質(zhì)量,從而進(jìn)一步減小了種群質(zhì)量的好壞對(duì)算法的影響。

2.6 交叉變異操作引入

在單目標(biāo)柔性作業(yè)車間調(diào)度過(guò)程中,為解決蟻獅算法收斂速度較慢、逃避局部最優(yōu)能力弱以及對(duì)加工工序順序的安排、加工機(jī)器的選擇和利用率不高的問(wèn)題,筆者將遺傳算法的交叉變異操作引入蟻獅算法中。其具體過(guò)程如下:

2.6.1 交叉操作

在FJSP加工過(guò)程中,不僅需要確定工件i的所有工序j的加工順序,還要對(duì)加工工序進(jìn)行加工機(jī)器分配,針對(duì)該特點(diǎn),筆者使用了兩種交叉操作:

(1)單點(diǎn)交叉操作。用于對(duì)染色體中工序加工順序的交叉,可更好地繼承父代染色體中的優(yōu)良基因;

(2)兩點(diǎn)交叉操作。用于染色體中對(duì)工序加工機(jī)器的分配的交叉。

以下對(duì)兩種交叉操作進(jìn)行說(shuō)明。

單點(diǎn)交叉又被稱為簡(jiǎn)單交叉,它是指在父代染色體中的工序加工順序基因段中隨機(jī)選取一個(gè)隨機(jī)點(diǎn),交換兩個(gè)父代在隨機(jī)點(diǎn)前后的基因段,產(chǎn)生子代。

單點(diǎn)交叉如圖4所示。

圖4 單點(diǎn)交叉

圖4中:在父代P1與P2工序加工順序染色體中,隨機(jī)選取一個(gè)隨機(jī)點(diǎn),交換父代P1與P2隨機(jī)點(diǎn)前后的基因,產(chǎn)生子代C1和C2。

兩點(diǎn)交叉操作是對(duì)父代染色體工序所分配的機(jī)器進(jìn)行交叉,工序的加工順序保留到子代。

基于機(jī)器編碼的兩點(diǎn)交叉操作如圖5所示。

圖5 基于機(jī)器編碼的兩點(diǎn)交叉操作

圖5中:設(shè)父代P1和P2交叉產(chǎn)生子代C1和C2。兩點(diǎn)交叉操作的過(guò)程為:隨機(jī)在P1和P2中選擇并設(shè)置兩個(gè)交叉點(diǎn),交換兩個(gè)父代中所選定的兩個(gè)交叉點(diǎn)之間的部分染色體,產(chǎn)生子代C1和C2,P1和P2中其他所分配的機(jī)器保留到子代。

2.6.2 變異操作

采用兩種變異操作:(1)在工序編碼染色體中使用插入變異操作方式;(2)利用單點(diǎn)變異操作進(jìn)行工件加工工序機(jī)器的替換,從兩方面進(jìn)行變異操作。

筆者使用插入變異操作對(duì)工序進(jìn)行變異操作,其工序的插入變異如圖6所示。

圖6 插入變異

圖6中:在工序編碼的父代染色體中隨機(jī)選擇一個(gè)基因,將其隨機(jī)插入某個(gè)基因前面或者后面,保持其他基因不變,產(chǎn)生子代。該變異操作對(duì)工序的安排進(jìn)行一個(gè)隨機(jī)化處理,讓工序加工有更多的可能性,可更好地選擇出一個(gè)合適的調(diào)度方案。

筆者采用單點(diǎn)變異操作進(jìn)行工件加工工序機(jī)器的替換?；跈C(jī)器編碼的單點(diǎn)變異如圖7所示。

圖7 基于機(jī)器編碼的單點(diǎn)變異

圖7中:筆者在機(jī)器編碼的染色體中選擇一個(gè)基因段,從該機(jī)器所加工的工序可選機(jī)器集中選擇一個(gè)進(jìn)行替換,可選擇機(jī)器號(hào)小的機(jī)器來(lái)替換執(zhí)行變異操作的基因段。

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

3.1 改進(jìn)前后ALO算法的實(shí)驗(yàn)對(duì)比

為了驗(yàn)證改進(jìn)的蟻獅算法在柔性作業(yè)車間調(diào)度上的有效性,筆者利用Brandimarte基準(zhǔn)算例加工環(huán)境數(shù)據(jù)集(MK01—MK10)作為模型進(jìn)行仿真測(cè)試。

MK01算例加工環(huán)境模型如圖8所示。

工件機(jī)器工序1工序2工序3工序4工序5工序6J1[1,3][5,3,2][3,6][6,2,1]3[6,3,4]J2231[2,4][6,2,1]—J32[3,6][6,2,1][3,2,6][1,5]—J4[6,2,1]23[5,3,2][3,6]—J5[5,3,2][6,2,1]2[1,3][2,4][3,2,6]J6[3,6]1[3,2,6]2[6,2,1][1,4]J76[1,4][3,2,6][2,5,1]3—J8[3,6][3,2,6][6,2,1]2[2,4]—J96[1,5][6,3,4]1[3,2,6][2,4]J10[3,6][3,2,6][5,3,2]6[2,4][1,4]

算法使用MATLAB2014b進(jìn)行編程。運(yùn)行環(huán)境為Windows10,Intel(R) Core(TM) i5-6200U CPU 2.40 GHz,內(nèi)存4 GB,64位操作系統(tǒng)的個(gè)人筆記本電腦。

測(cè)試目標(biāo)函數(shù)為1.2節(jié)中的式(1),算法參數(shù)設(shè)置為:種群大為100,迭代次數(shù)為200次,交叉范圍(0.3,0.9),變異范圍(0.1,0.25)。

筆者使用Brandimarte算例中的MK01基準(zhǔn)算例,以最小化最大完工時(shí)間為優(yōu)化目標(biāo),運(yùn)行20次ALO算法;然后進(jìn)行改進(jìn)前后ALO算法對(duì)比,從迭代收斂圖和甘特圖可以明顯地看出優(yōu)缺點(diǎn)。

改進(jìn)前后ALO算法迭代收斂對(duì)比圖如圖9所示。

圖9 改進(jìn)前后ALO算法迭代收斂對(duì)比圖

圖9中可以看出:第一次迭代時(shí),改進(jìn)前的時(shí)間是65,改進(jìn)后的時(shí)間是49,驗(yàn)證了改進(jìn)ALO算法利用混沌映射和競(jìng)標(biāo)賽選擇的混合初始化種群策略對(duì)初始化種群的質(zhì)量有了極大的改善,保證了初始種群的多樣性和質(zhì)量;

ALO算法迭代160左右才找到最優(yōu)解,而改進(jìn)后的ALO算法迭代100次時(shí)就找到了最優(yōu)解,且找到的最優(yōu)解比改進(jìn)前找到的解要小,說(shuō)明改進(jìn)ALO算法較ALO算法收斂速度快,能夠快速地求解柔性作業(yè)車間問(wèn)題;

其次,ALO算法在40代到135代之間陷入了局部最優(yōu),逃離局部最優(yōu)的能力較弱,而改進(jìn)的ALO算法僅在40代到100代之間陷入局部最優(yōu),逃離局部最優(yōu)的能力有顯著增強(qiáng),加快了算法的收斂速度;

從加工時(shí)長(zhǎng)來(lái)看,ALO算法最小最大完工時(shí)間最優(yōu)為53,而改進(jìn)ALO算法最小最大完工時(shí)間最優(yōu)為40,明顯提高了生產(chǎn)加工的速率。

為探究改進(jìn)前后ALO算法優(yōu)化FJSP問(wèn)題的加工調(diào)度方案的優(yōu)、缺點(diǎn),可根據(jù)甘特圖進(jìn)行對(duì)比觀察。

改進(jìn)前后甘特圖對(duì)比如圖10所示。

在圖10中可以看出:對(duì)機(jī)器5的利用率不高,只有兩道工序在機(jī)器5上進(jìn)行加工,且機(jī)器4的空閑時(shí)間較多,而引入了遺傳算法的交叉變異操作,在機(jī)器5上加工工序變?yōu)榱?道工序,明顯提高了對(duì)加工機(jī)器的利用率,同時(shí)也使機(jī)器4的空閑時(shí)間減少,充分利用了固有資源,降低了生產(chǎn)成本,減少了完成加工的時(shí)間。綜上所述,改進(jìn)后的蟻獅算法更加適用于解決單目標(biāo)柔性作業(yè)車間問(wèn)題。

3.2 與其他智能算法的實(shí)驗(yàn)對(duì)比

為進(jìn)一步驗(yàn)證改進(jìn)蟻獅算法求解單目標(biāo)柔性作業(yè)車間調(diào)度問(wèn)題的有效性,筆者使用Brandimarte基準(zhǔn)算例中的MK01-MK10基準(zhǔn)算例,以最小化最大完工時(shí)間為單目標(biāo),運(yùn)行20次算法,與姜天華等人[13]提出的混合灰狼優(yōu)化算法(hybrid grey wolf optimization,HGWO)、PRASERT S等人[14]提出的改進(jìn)微分進(jìn)化算法(improved differential evolution,IDE)、CALDEIRA R H[15]提出的改進(jìn)Jaya算法(improver Jaya algorithm, IJaya)、ALO算法,以及改進(jìn)ALO算法的仿真結(jié)果進(jìn)行對(duì)比。

Brandimarte算例對(duì)比結(jié)果如表1所示。

表1 Brandimarte算例對(duì)比

從表1中可以發(fā)現(xiàn):改進(jìn)ALO算法比ALO算法效果更加明顯;與其他3種算法相比,改進(jìn)后的ALO算法比HGWO除了MK03算例略差,MK01、MK03、MK07以及MK08這4個(gè)算例效果持平,剩下的5種算例均優(yōu)于HGWO算法;

與IDE算法相比較可知,除了MK07和MK09以外,改進(jìn)后的ALO算法均優(yōu)于IED算法。與IJaya算法相比,改進(jìn)ALO算法效果與其持平,沒有體現(xiàn)出明顯優(yōu)于IJaya算法的趨勢(shì)。

MK02算例下Makespe=28調(diào)度方案甘特圖如圖11所示。

圖11 MK02算例下Makespe=28甘特圖調(diào)度方案

綜上所述,與改進(jìn)前算法相比,改進(jìn)蟻獅算法具有更強(qiáng)的收斂速度和不易陷入局部最優(yōu)的特點(diǎn);且在工序加工安排和加工機(jī)器的選擇上,該算法可以極大程度地避免機(jī)器空閑和加工機(jī)器利用率不高的現(xiàn)象發(fā)生。

與目前單目標(biāo)柔性作業(yè)車間調(diào)度問(wèn)題的求解算法相比,該算法都具有優(yōu)勢(shì)。該結(jié)果表明,采用改進(jìn)蟻獅算法求解單目標(biāo)柔性作業(yè)車間調(diào)度問(wèn)題是有效的。

4 結(jié)束語(yǔ)

筆者建立了以最小最大完工時(shí)間為優(yōu)化目標(biāo)的柔性作業(yè)車間調(diào)度模型,使用蟻獅算法求解柔性作業(yè)車間調(diào)度問(wèn)題,通過(guò)實(shí)驗(yàn)證明,蟻獅算法可以求解柔性作業(yè)車間調(diào)度問(wèn)題,但是也存在一定的缺陷,為此,筆者對(duì)算法進(jìn)行了改進(jìn),提出了基于混沌映射與競(jìng)標(biāo)賽選擇的混合策略生成初始種群;引入了傳統(tǒng)遺傳算法中的交叉變異策略;通過(guò)Brandimarte基準(zhǔn)算例的仿真結(jié)果與其他算法進(jìn)行實(shí)驗(yàn)對(duì)比,驗(yàn)證了改進(jìn)ALO算法求解柔性作業(yè)車間調(diào)度問(wèn)題的有效性。

研究結(jié)論如下:

(1)蟻獅算法可以用于求解柔性作業(yè)車間調(diào)度問(wèn)題,但會(huì)出現(xiàn)隨機(jī)生成的初始種群質(zhì)量不優(yōu)、算法的收斂速度較慢、逃避局部最優(yōu)能力較弱、最小最大完工時(shí)間較長(zhǎng)、加工機(jī)器利用率低以及加工空閑時(shí)間較多等問(wèn)題;

(2)蟻獅算法可以得到改進(jìn)。首先,提出了基于混沌映射與競(jìng)標(biāo)賽選擇的混合策略生成初始種群,可以保證初始種群的質(zhì)量和多樣性;其次,引入了傳統(tǒng)遺傳算法中交叉變異策略,可以使該算法在迭代過(guò)程中,收斂速度加快,逃避局部最優(yōu)的能力增強(qiáng)以及加工機(jī)器的利用率更高;

(3)通過(guò)利用Brandimarte基準(zhǔn)算例,進(jìn)行改進(jìn)前后蟻獅算法實(shí)驗(yàn)對(duì)比,證明了改進(jìn)ALO算法在解決該問(wèn)題時(shí),其收斂速度、逃避陷入局部最優(yōu)的能力有明顯的提升。

為進(jìn)一步驗(yàn)證該算法的有效性,筆者將其與解決柔性作業(yè)車間調(diào)度問(wèn)題的其他智能算法進(jìn)行了實(shí)驗(yàn)對(duì)比,結(jié)果證明了該算法有較好的尋優(yōu)能力和收斂速度,驗(yàn)證了該算法解決該問(wèn)題的有效性。

在后續(xù)的研究中,筆者將根據(jù)現(xiàn)有的研究?jī)?nèi)容,將該算法運(yùn)用到求解多目標(biāo)柔性作業(yè)車間調(diào)度問(wèn)題中,并對(duì)其進(jìn)行改進(jìn),使該算法更加適用于求解實(shí)際柔性作業(yè)車間調(diào)度問(wèn)題。