面向柔性作業(yè)車間調(diào)度的改進(jìn)混合蛙跳算法*

王玉芳，繆 昇，葛嘉榮

(南京信息工程大學(xué) a.江蘇省大氣環(huán)境與裝備技術(shù)協(xié)同創(chuàng)新中心;b.自動(dòng)化學(xué)院;c.江蘇省大數(shù)據(jù)分析技術(shù)重點(diǎn)實(shí)驗(yàn)室,南京 210044)

0 引言

柔性作業(yè)車間調(diào)度問(wèn)題(flexible job-shop scheduling problem,FJSP)作為作業(yè)車間調(diào)度問(wèn)題(job-shop scheduling problem,JSP)的一個(gè)分支,它打破了機(jī)器唯一的限制,即待加工工件可以在可選機(jī)器集中選擇一臺(tái)或者多臺(tái)機(jī)器進(jìn)行加工，這無(wú)疑更加符合當(dāng)前復(fù)雜的生產(chǎn)制造環(huán)境，因此FJSP受到了越來(lái)越多的關(guān)注,并取得重大進(jìn)展[1-4]。

作為一個(gè)典型的NP-Hard難題,在過(guò)去的30年中,隨著科學(xué)技術(shù)的發(fā)展,許多的算法被用于解決這類問(wèn)題,諸如遺傳算法[5]、粒子群算法[6]、模擬退火算法[7]、禁忌搜索算法[8]等,這些算法在求解FJSP上都取得了良好的效果。基于這類智能算法的啟發(fā),近年來(lái),也是有越來(lái)越多的仿生智能算法被提出,并且在解決FJSP上展現(xiàn)了優(yōu)越的效果,連裕翔等[9]提出了一種改進(jìn)的Jaya算法,融合M.G和N7兩種鄰域結(jié)構(gòu)的禁忌搜索算法,使混合算法在分散搜索與集成搜索之間達(dá)到平衡,在解決FJSP上顯示出了良好的性能。趙詩(shī)奎[10]提出一種融合改進(jìn)鄰域結(jié)構(gòu)的混合算法,結(jié)合關(guān)鍵工序設(shè)計(jì)了相應(yīng)的移動(dòng)操作,對(duì)已有鄰域結(jié)構(gòu)進(jìn)行了優(yōu)化與擴(kuò)展,提高了鄰域結(jié)構(gòu)的精準(zhǔn)有效性。

蛙跳算法(shuffled frog leaping algorithm,SFLA)作為一種新型的仿生物學(xué)智能優(yōu)化算法，具有概念簡(jiǎn)單，調(diào)整的參數(shù)少,計(jì)算速度快,全局搜索尋優(yōu)能力強(qiáng),易于實(shí)現(xiàn)的特點(diǎn)[11-12]。張曉星等[13]構(gòu)建了以最大完工時(shí)間和總加工能耗最小為優(yōu)化目標(biāo)調(diào)度模型混合蛙跳算法,設(shè)計(jì)了多種局部搜索操作以及鄰域操作來(lái)防止算法陷入局部最優(yōu),但在種群初始化時(shí)并未考慮啟發(fā)式規(guī)則,這就大大削弱了算法的性能，延長(zhǎng)了算法尋找到最優(yōu)解的時(shí)間。艾子義等[14]提出了一種基于新型蛙跳算法的柔性作業(yè)車間調(diào)度模型,加入全局和局部結(jié)合的協(xié)調(diào)優(yōu)化搜索策略,并且取消了種群重組,大大簡(jiǎn)化了算法結(jié)構(gòu),但在解碼過(guò)程中并未考慮啟發(fā)式解碼規(guī)則,而傳統(tǒng)的解碼規(guī)則會(huì)使得算法陷入局部最優(yōu),降低收斂速度。

受已有研究啟發(fā)，本文提出一種改進(jìn)的混合蛙跳算法(improved shuffled frog leaping algorithm,ISFLA)，首先，利用啟發(fā)式規(guī)則按比例生成高質(zhì)量的初始種群,加快算法的收斂速度；其次，采用貪婪解碼的方法代替?zhèn)鹘y(tǒng)解碼方式,加強(qiáng)對(duì)解空間的搜索和最優(yōu)解的挖掘；最后，加入了考慮機(jī)器平衡的局部搜索方法,很好的彌補(bǔ)了算法局部搜索能力不足的缺點(diǎn)。

1 問(wèn)題描述

作為一個(gè)典型的NP-Hard難題，F(xiàn)JSP可以描述如下：有臺(tái)機(jī)器m(M1,M2,…,Mm)處理n(J1,J2,…,Jn)個(gè)工件,每個(gè)工件有若干道工序，Oij表示工件i的第j道工序，每道工序可以在不同機(jī)器上進(jìn)行加工，且在不同的機(jī)器上的加工時(shí)間是不相同的。調(diào)度目標(biāo)是通過(guò)為各工序選擇合適的機(jī)器進(jìn)行加工以及調(diào)整各個(gè)機(jī)器上工序加工的先后順序來(lái)使最大完成時(shí)間最小。本文中的時(shí)間均為抽象的單位時(shí)間，此外，在加工過(guò)程中還需要滿足下列的約束條件：

(1)調(diào)度開(kāi)始前所有工件和機(jī)器都處于準(zhǔn)備就緒狀態(tài)且所有工件都可以從零時(shí)刻開(kāi)始被加工；

(2)每臺(tái)機(jī)器在同一時(shí)間只能加工一道工序；

(3)同一個(gè)工件的同一道工序在同一時(shí)間只能被一臺(tái)機(jī)器加工；

(4)同一個(gè)工件的工序有前后加工順序約束，加工完上一道工序才能開(kāi)始下一道工序的加工；

(5)不同的工件之間沒(méi)有加工順序的束。

定義如下數(shù)學(xué)描述：n為工件總數(shù)；m為機(jī)器總數(shù)；i為工件序號(hào),i=1,2,3,…,n；h為機(jī)器序號(hào),h=1,2,3,…,m；ei為第i個(gè)工件的工序數(shù)；j為第i個(gè)工件的工序號(hào),j=1,2,3,…,ei；Oij為第i個(gè)工件的第j道工序；mij為第i個(gè)工件的第j道工序的可選機(jī)器集中機(jī)器的個(gè)數(shù)；Oijh為第i個(gè)工件的第j道工序在機(jī)器Mh上加工；tijh為第i個(gè)工件的第j道工序在機(jī)器Mh上加工的時(shí)間；sij為第i個(gè)工件的第j道工序的開(kāi)始時(shí)間；cij為第i個(gè)工件的第j道工序的完成時(shí)間；K為一個(gè)特別大的正數(shù)；Ci為工件Ji的完成時(shí)間；Wh為第h個(gè)機(jī)器的負(fù)載,h=1,2,3,…,m。

約束條件如下：

s.t.

ci0=0

(1)

sij+xijh×tijh≤cij

(2)

Ci(j-1)≤sij

(3)

cij≤Cmax

(4)

sij+tijh≤skl+K(1-yijhkl)

(5)

Ci(j-1)≤sij+K(1-yijhkj)

(6)

(7)

sij≥0,cij≥0

(8)

式(1)表示虛擬的第零道工序完工時(shí)間為零；式(2)和式(3)表示同一個(gè)工件包含的工序必須按照先后順序處理；式(4)表示任意工序的完成時(shí)間不超過(guò)總的完成時(shí)間，式(5)和式(6)表示在某一時(shí)刻的一臺(tái)機(jī)器上只允許處理一道工序；式(7)表示在某一時(shí)刻同一道工序只能在一臺(tái)機(jī)器上處理；式(8)表示任意工序的開(kāi)始時(shí)間和完成時(shí)間都是非負(fù)的，且任意工件都可以從0時(shí)刻開(kāi)始加工。

2 ISFLA算法

在傳統(tǒng)的SFLA中，每一個(gè)青蛙的位置代表一個(gè)解，若干個(gè)青蛙組成的種群代表一個(gè)解的集合，種群被劃分為不同的組，即模因組，對(duì)每個(gè)模因組執(zhí)行搜索過(guò)程，當(dāng)達(dá)到終止條件后，重新將模因組合并成新的種群，這個(gè)過(guò)程稱作種群重組。搜索和重組過(guò)程持續(xù)進(jìn)行直到滿足終止條件。

在FJSP中，每一個(gè)青蛙代表一個(gè)個(gè)體，即一個(gè)可行解，每一個(gè)可行解都有一個(gè)評(píng)價(jià)其優(yōu)劣的指標(biāo)，即目標(biāo)值?？紤]到傳統(tǒng)SFLA依靠位置更新公式來(lái)產(chǎn)生新解，這種方式難以應(yīng)用于FJSP這種離散問(wèn)題中，所以需要對(duì)SFLA離散化，構(gòu)建合理的編碼解碼以及搜索重組方式。

2.1 編碼

FJSP包含兩個(gè)基本問(wèn)題，即工序調(diào)度問(wèn)題和機(jī)器分配問(wèn)題[15]，因此，該問(wèn)題的解決方案通常由兩部分組成[16-18]，工序串和機(jī)器串，工序串表示所有工件的加工順序，機(jī)器串表示工件對(duì)應(yīng)所選擇的加工機(jī)器號(hào)。一個(gè)3×3的FJSP實(shí)例如表1所示。其中“2”表示第一個(gè)工件的第一道工序在1號(hào)機(jī)器上加工的時(shí)間為2，“-”表示該工件的該道工序不能在該機(jī)器上加工，以此類推。一個(gè)完整的解決方案可以表示為{[1 3 2 1 2 3][3 3 2 1 1 2]}，第一部分{[1 3 2 1 2 3]}表示工序加工順序，數(shù)字代表工件號(hào)，數(shù)字出現(xiàn)的次數(shù)則代表對(duì)應(yīng)工件的第幾道工序。第二部分{[3 3 2 1 1 2]}表示對(duì)應(yīng)工件所選擇的加工機(jī)器。

表1 3×3FJSP實(shí)例

2.2 解碼

解碼是為了將工序串和機(jī)器串轉(zhuǎn)換所求的目標(biāo)值，在此基礎(chǔ)上合理地安排各個(gè)工件在機(jī)器上加工，從而使得目標(biāo)值最優(yōu)。本文為了實(shí)現(xiàn)染色體解碼對(duì)解空間的高效搜索，設(shè)計(jì)了一種進(jìn)化貪婪插入法(evolutionary greedy insertion,EGI)，其解碼過(guò)程如圖1所示。

圖1 EGI解碼過(guò)程示意圖

工序Oij即將在機(jī)器Mb上加工，根據(jù)當(dāng)前加工情況，有三段空閑可供選擇，Idle1、Idle2和Idle3三段空閑時(shí)間均大于等于Oij的加工時(shí)間。Idle1的開(kāi)始時(shí)間小于Oi(j-1)結(jié)束時(shí)間，故不滿足約束條件。Idle2和Idle3都滿足約束條件，而Idle2更接近Oij的加工時(shí)間，所以選擇Idle2插入。相對(duì)于一般的解碼方法，EGI提供了更多可供選擇的空閑時(shí)間段，更利于找到最優(yōu)解。

2.3 種群初始化

初始種群質(zhì)量的優(yōu)劣對(duì)于算法而言至關(guān)重要，一個(gè)高質(zhì)量的種群能夠?yàn)樗惴ǖ倪M(jìn)化提供一個(gè)優(yōu)越的起點(diǎn)，使算法減少?gòu)牟罱獾絻?yōu)解的搜尋時(shí)間。本算法采用了ZHANG等[19]提出的GLS初始化方法，即全局選擇(global selection,GS)、局部選擇(local selection,LS)和隨機(jī)選擇(random selection,RS)，除此以外，再加入一種全局最小化(global minimization,GM)方法，選擇可選機(jī)器集中加工時(shí)間最短的那一臺(tái)機(jī)器進(jìn)行加工。在上述多種啟發(fā)式規(guī)則啟發(fā)下生成的初始種群能夠?yàn)樗惴ǖ倪M(jìn)化提供一個(gè)較好的起點(diǎn)，加快算法的整體收斂速度。

2.4 族群劃分

混合蛙跳算法區(qū)別于其他算法最大的特點(diǎn)就是對(duì)種群進(jìn)行分組，而傳統(tǒng)的隨機(jī)劃分方式由于不能平衡各個(gè)組內(nèi)青蛙的優(yōu)劣程度，會(huì)大大增加算法求解的隨機(jī)性，使得算法的收斂速度變慢。本文算法采用LEI等[20]提出的二元錦標(biāo)賽選擇方式將種群劃分成w個(gè)族群V(V1,V2,…,Vw)，先從種群中選擇最好的w個(gè)個(gè)體依次作為每個(gè)族群中的第一個(gè)個(gè)體，再?gòu)挠嘞碌膫€(gè)體中利用錦標(biāo)賽選擇法補(bǔ)充每個(gè)族群的剩余個(gè)體，即從剩下的種群中隨機(jī)選擇兩個(gè)個(gè)體Q1和Q2，優(yōu)秀的那一個(gè)個(gè)體進(jìn)入V1，作為V1中的第二個(gè)個(gè)體，較差的那個(gè)返回種群；再?gòu)姆N群中隨機(jī)選擇兩個(gè)個(gè)體，較好的那一個(gè)進(jìn)入V2，作為V2中的第二個(gè)個(gè)體，以此類推，直至所有的族群被填滿。

2.5 族群內(nèi)進(jìn)化策略

對(duì)于每一個(gè)族群內(nèi)的個(gè)體來(lái)說(shuō)，如果都采用相同的進(jìn)化策略，則難以對(duì)不同質(zhì)量的個(gè)體進(jìn)行有針對(duì)性的進(jìn)化，所以為了避免盲目進(jìn)化，通常在各自族群內(nèi)部會(huì)區(qū)分出優(yōu)劣個(gè)體，然后對(duì)其采用不同的更新策略進(jìn)行優(yōu)化。對(duì)族群中優(yōu)秀的個(gè)體采用鄰域搜索，加強(qiáng)對(duì)更優(yōu)解的挖掘。對(duì)族群中的劣勢(shì)解，則采用全局加局部結(jié)合的協(xié)調(diào)優(yōu)化策略，平衡整個(gè)族群中個(gè)體的優(yōu)劣程度，加快算法的收斂速度。

2.6 更新策略

2.6.1 交叉操作

交叉的目的是為了獲得新的個(gè)體，在盡量保證優(yōu)良基因不被破壞的情況下，對(duì)解空間進(jìn)行高效搜索，因而交叉操作應(yīng)該滿足可行性、繼承性和非冗余性。針對(duì)FJSP的特性，ZHANG等[21]提出的POX交叉法，因其具有低約束性，并且可以避免沖突檢測(cè)，所以被普遍用來(lái)完成對(duì)工序編碼層的交叉操作。本文對(duì)POX交叉法進(jìn)行局部改進(jìn)，提出一種改進(jìn)的交叉法(improved intersection method,IIM)，具體步驟如下：

步驟1：選出兩條染色體P1、P2作為父代，P1=[1 3 2 4 3 1 2 4 3],P2=[3 1 1 2 4 4 2 3 3]；

步驟2：將工件集J={1,2,3,4}分為兩個(gè)非空子集，J1={1,2},J2={3,4}；

步驟3：復(fù)制P1中包含在J1中的基因按原順序插入子代染色體C1中，復(fù)制P2中包含在J1中的基因按原順序插入子代染色體C2中；

步驟4：復(fù)制P2中包含在J2中的基因按原順序插入C1中，復(fù)制P1中包含在J2中的基因按原順序插入C2中，得到C1=[1 3 2 4 4 1 2 3 3],C2=[3 1 1 2 4 3 2 4 3]；

步驟5：對(duì)C1、C2進(jìn)行倒序操作得到C3、C4，C3=[3 3 2 1 4 4 2 3 1],C4=[3 4 2 3 4 2 1 1 3]，對(duì)C1、C2、C3、C4進(jìn)行解碼操作，選取最優(yōu)的兩個(gè)解代替C1、C2。

而對(duì)于機(jī)器編碼層采用多點(diǎn)交叉方式，可避免產(chǎn)生非法解。具體步驟如下：

步驟1：隨機(jī)選擇兩條機(jī)器染色體L1和L2，L1=[1 2 5 3 4 2 6 1 5],L2=[3 3 5 2 1 4 2 3 3]；

步驟2：生成一個(gè)和機(jī)器染色體維度一樣的0、1數(shù)組X，X=[0 0 1 1 0 0 1 0 0]；

步驟3：找到矩陣中所有1所在的位置；

步驟4：將所有位置1上的L1和L2的基因?qū)Q得到L1′和L2′，L1′=[1 2 5 2 4 2 2 1 5],L2′=[3 3 4 3 4 2 6 3 3]。

2.6.2 局部搜索操作

為了提高算法的搜索能力和開(kāi)發(fā)能力，在保持種群多樣性的同時(shí)又能夠提高算法的收斂能力，本文算法采用了分別針對(duì)于工序編碼層和機(jī)器編碼層的局部搜索策略。

(1)針對(duì)工序編碼層OS，采用如下步驟進(jìn)行局部搜索操作：

步驟1：選擇一條工序染色體P，P=[1 3 2 4 1 1 2 2 3]；

步驟2：隨機(jī)選擇兩個(gè)工序數(shù)相等的工件J1和J2，J1={1},J2={2}，找出它們所有工序在染色體中的位置；

步驟3：交換兩個(gè)工件對(duì)應(yīng)所有工序的位置，并保持原來(lái)的順序，得到新的工染色體P′，P′=[2 3 1 4 2 2 1 1 3]。

(2)針對(duì)機(jī)器編碼層，結(jié)合圖2具體搜索步驟如下：

步驟1：選擇一組染色體，其中工序染色體為P，P=[1 1 2 3 3 1 4 2 4]；機(jī)器染色體為L(zhǎng)，L=[2 1 3 2 3 1 3 2 1]；對(duì)應(yīng)加工時(shí)間矩陣為T，T=[1 2 1 3 1 4 1 2 2 ];

步驟2：計(jì)算出所有機(jī)器上的總負(fù)載Ptotal，Ptotal=[8 6 3]；最大完成時(shí)間Cmax，Cmax=9；計(jì)算得到所有機(jī)器的負(fù)載率，其中每臺(tái)機(jī)器的負(fù)載率P=Ptotal/Cmax，P=[0.89 0.67 0.33]，并排序得到負(fù)載率最高和最低的機(jī)器；

步驟3：在滿足約束條件的情況下，從負(fù)載率最高的機(jī)器上選擇該機(jī)器加工的最后一道工序移動(dòng)到負(fù)載率最低的那一臺(tái)機(jī)器上，從圖2可以看出，在未進(jìn)行該局部搜索時(shí)，最大完成時(shí)間為9，經(jīng)過(guò)該局部搜索，將M1上的O42移動(dòng)到M3上，得到的最大完成時(shí)間為8。

圖2 機(jī)器局部搜索

2.7 ISFLA算法整體框架

根據(jù)上述改進(jìn)策略，結(jié)合FJSP，提出的ISFLA框架流程圖如圖3所示。

圖3 ISFLA流程圖

3 實(shí)驗(yàn)數(shù)據(jù)與分析

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

ISFLA采用MATLAB編程實(shí)現(xiàn)，程序在Windows7系統(tǒng)，主頻為2.9 GHz，內(nèi)存為8 G的個(gè)人電腦上運(yùn)行。由于參數(shù)的選擇對(duì)算法的運(yùn)算結(jié)果也十分重要，所以采用正交試驗(yàn)基于Brandinmrte[22]系列中的MK01算例來(lái)確定最終的參數(shù)，具體參數(shù)包括種群大小popsize，迭代次數(shù)maxgen，族群個(gè)數(shù)w以及每個(gè)族群內(nèi)部搜索的次數(shù)gen。另外，考慮到算例規(guī)模大小對(duì)算法的運(yùn)行效果有較大的影響，所以因子水平的選擇均與算例的工件數(shù)與機(jī)器數(shù)有關(guān)。

對(duì)于一些規(guī)模較小的算例，如果參數(shù)選擇過(guò)大可能會(huì)造成冗余計(jì)算，削弱算法的整體運(yùn)行效率，而對(duì)于一些規(guī)模較大的算例，參數(shù)設(shè)置的過(guò)小則會(huì)造成搜索不完全，容易遺漏最優(yōu)解。綜合考慮之后選擇了表2所示的指標(biāo)水平。正交試驗(yàn)規(guī)模為 L9(34)，即試驗(yàn)次數(shù)為9，參數(shù)個(gè)數(shù)為4，因子水平數(shù)為3。

表2 參數(shù)組合

算法在9種參數(shù)組合的基礎(chǔ)上分別運(yùn)行10次，得到的Cmax的平均值Cavg，Cavg越小則表示該種參數(shù)組合越適合ISFLA，正交試驗(yàn)結(jié)果如表3所示。

表3 正交試驗(yàn)結(jié)果

可以看出，參數(shù)組合8所得到的Cavg最小，表示這組參數(shù)最適合ISFLA，所以最終的參數(shù)設(shè)置為popsize=6×m×n,maxgen=m×n,w=m,gen=2×m×n。

3.2 策略有效性分析

為了進(jìn)一步驗(yàn)證改進(jìn)策略對(duì)算法的影響，本文對(duì)這些改進(jìn)策略進(jìn)行了有效性分析，3種改進(jìn)策略分別為改進(jìn)啟發(fā)式規(guī)則初始化Ispt-Initial、改進(jìn)貪婪解碼方法EGI以及考慮機(jī)器負(fù)載平衡的局部搜索策略Local-Balance，然后對(duì)這3種改進(jìn)策略進(jìn)行排列組合得到7種不同的改進(jìn)算法，然后在傳統(tǒng)的SFLA基礎(chǔ)上分別加上這7種改進(jìn)算法，得到的進(jìn)化曲線對(duì)比圖如圖4所示。

圖4 改進(jìn)策略進(jìn)化曲線

可以看出，傳統(tǒng)的SFLA在求解MK01算例時(shí)效果并不理想，而隨著改進(jìn)策略的加入，算法的性能逐漸提升，尤其Ispt-Initial這一改進(jìn)策略得到的效果尤為突出，可見(jiàn)啟發(fā)式規(guī)則對(duì)于算法的進(jìn)化是十分重要的，它為整個(gè)算法提供了一個(gè)優(yōu)秀的起點(diǎn)，加速了算法的收斂，避免了冗余計(jì)算。

而EGI和Local-Balance雖然改進(jìn)效果不大，但相較于傳統(tǒng)的SFLA，效果依舊可觀。接下來(lái)3種改進(jìn)策略的兩兩組合相較于其各自單獨(dú)作用效果更加明顯，其中Ispt-Initial和EGI這兩個(gè)的改進(jìn)策略的組合要明顯優(yōu)于另外兩種，除了啟發(fā)式初始化規(guī)則發(fā)揮的作用外，這種改進(jìn)的貪婪解碼方式為解碼提供了更多可供選擇的可插入空閑時(shí)間段，在滿足約束 條件的前提下選擇最優(yōu)的空閑時(shí)間段插入，大大提高了解碼的時(shí)效性。最后在這一基礎(chǔ)上加入了Local-Balance這一局部搜索策略，最大化的考慮每臺(tái)機(jī)器上的負(fù)載平衡，在減小Cmax的同時(shí)也能夠減小能耗，改進(jìn)效果也是最好的。

3.3 算例對(duì)比

為了更加直觀地驗(yàn)證ISFLA在解決FJSP上的高效性能，本文與文獻(xiàn)[23-25]提出的算法性能進(jìn)行對(duì)比，采用Brandinmrte系列中MK01-MK10算例。對(duì)比算法具體標(biāo)識(shí)如下：ICSO為文獻(xiàn)[23]提出的貓群算法，VNS_MBOA為文獻(xiàn)[24]提出的變鄰域搜索候鳥(niǎo)優(yōu)化算法，IGPSO為文獻(xiàn)[25]提出的改進(jìn)博弈粒子群算法。本文算法ISFLA與上述3種算法對(duì)比如表4所示，其中m×n表示工件數(shù)與機(jī)器數(shù)的乘積，即總工序數(shù)；C*表示已有文獻(xiàn)得到的最優(yōu)解；min表示本文算法得到的最優(yōu)解；avg表示算法運(yùn)行十次得到的平均值。

表4 ISFLA與WSA、VNS_MBOA、IGPSO最優(yōu)解的比較

可以看出，ISFLA在MK01-MK10算例的求解上Cmax和Cavg都優(yōu)于另外兩種算法，并且MK01、MK02、MK03以及MK08算例都得到了與已有最優(yōu)解相同的Cmax。另外可以看到，在處理小規(guī)模問(wèn)題上例如MK01、MK03這類算例都取得了很好的效果，但隨著問(wèn)題規(guī)模的擴(kuò)大，ISFLA性能有所降低，尤其是MK06和MK10這兩個(gè)算例，機(jī)器數(shù)增多，工件可選擇的機(jī)器數(shù)就增加，這無(wú)疑加大了不確定性，也同時(shí)加大了ISFLA求解的難度。另外從表4可以看到，本文算法在求解MK02實(shí)例得到最大完成時(shí)間不僅得到了與已有文獻(xiàn)相同的最優(yōu)解，并且另外三種算法沒(méi)有得到，所以圖5給出了MK02算例的調(diào)度甘特圖，其中每個(gè)矩形中上面的數(shù)字代表工件號(hào)，下面的數(shù)字代表工序號(hào)。

圖5 MK02算例調(diào)度甘特圖

從圖5可以看出，MK02實(shí)例的最大完成時(shí)間為26，與已有文獻(xiàn)得到的最優(yōu)解相同，并且各個(gè)工件之間基本沒(méi)有間隙，說(shuō)明貪婪插入的解碼操作起到了很好的作用，提高了加工的效率，避免了不必要的加工損耗。

4 結(jié)論

本文針對(duì)最小化最大完工時(shí)間這一目標(biāo)，結(jié)合傳統(tǒng)蛙跳算法的優(yōu)點(diǎn)和不足之處，提出了一種改進(jìn)的混合蛙跳算法，從種群初始化、解碼方式以及局部搜索策略這3個(gè)方面進(jìn)行相應(yīng)的改進(jìn)。與隨機(jī)初始化種群相比，利用啟發(fā)式規(guī)則生成的種群質(zhì)量更高，能夠?yàn)榻酉聛?lái)的進(jìn)化過(guò)程提供一個(gè)優(yōu)質(zhì)的起點(diǎn)。而進(jìn)化的貪婪解碼方式則相較于傳統(tǒng)的解碼方式能夠提供更多可供選擇的插入空閑時(shí)間段，在滿足所有約束條件前提下優(yōu)化目標(biāo)函數(shù)。試驗(yàn)結(jié)果表明，改進(jìn)的混合蛙跳算法在尋優(yōu)能力和收斂性上都優(yōu)于傳統(tǒng)的蛙跳算法，并且相較于另外3種智能算法，本算法表現(xiàn)出了更加突出的尋優(yōu)性能。在實(shí)際生產(chǎn)應(yīng)用中，多目標(biāo)的生產(chǎn)調(diào)度問(wèn)題無(wú)疑更加符合當(dāng)下復(fù)雜的生產(chǎn)環(huán)境，所以由單目標(biāo)生產(chǎn)調(diào)度向多目標(biāo)生產(chǎn)調(diào)度的轉(zhuǎn)變是很有必要的。另外為了響應(yīng)當(dāng)前“綠色制造”的號(hào)召，所以下一階段將圍繞多目標(biāo)“綠色”調(diào)度展開(kāi)。