改進蟻群算法的柔性作業(yè)車間調(diào)度問題研究*

趙小惠，衛(wèi)艷芳，王凱峰，倪奕棋

(西安工程大學(xué)機電工程學(xué)院，西安 710048)

0 引言

智能制造日益成為未來制造業(yè)發(fā)展的重大趨勢和核心內(nèi)容，而柔性作業(yè)車間調(diào)度問題(flexible job-shop scheduling problem，F(xiàn)JSP)作為智能制造業(yè)的核心問題受到了廣泛的關(guān)注。FJSP是傳統(tǒng)車間調(diào)度的擴展，更符合現(xiàn)代的生產(chǎn)模式，更具靈活性，更加貼合現(xiàn)代人的需求，因此受到了越來越多國內(nèi)外學(xué)者的關(guān)注。

在過去的幾十年中，智能算法求解FJSP問題層出不窮，并且通過驗證均取得了良好的效果。張國輝等[1]提出了改進遺傳算法，設(shè)計了不同策略生成初始解和人工配對方式進行交叉操作，又提出了對不同個體設(shè)計自適應(yīng)變異率及其變異范圍，最終使解的質(zhì)量得到提高。黎陽等[2]以最大化完工時間為目標(biāo)，提出了一種改進模擬退火算法，引入了并行搜索、記憶功能的概念，從而使大規(guī)模FJSP問題所求解的質(zhì)量得到提高。張靜等[3]提出了一種混合粒子群算法來求解多目標(biāo)FJSP問題。魯宏浩等[4]提出了分布估計—蟻群算法求解FJSP，兩種算法融合既保留了分布估計算法快速的全局搜索能力也保留了蟻群算法所具有的正反饋優(yōu)點，使得FJSP的求解具有良好的優(yōu)化效果。DING等[5]提出了一種混合人類學(xué)習(xí)優(yōu)化算法—粒子群算法(HLO-PSO算法)，可以有效解決大多數(shù)單目標(biāo)FJSP。WU等[6]將鴿子啟發(fā)優(yōu)化算法(PIO)算法應(yīng)用于FJSP問題，有效地解決了FJSP問題。SHI等[7]建立了具有模糊交貨期的FJSP的動態(tài)調(diào)度模型。并對免疫遺傳算法(IGA)進行了改進，為FJSP在現(xiàn)實世界中的應(yīng)用提供了新的思路。HUANG等[8]將混合遺傳算法與模擬退火相結(jié)合并將運輸時間考慮在內(nèi)，對多目標(biāo)柔性作業(yè)車間調(diào)度問題進行了求解。

綜上所述，智能算法求解FJSP問題具有可行性，但由于FJSP是復(fù)雜的NP-hard問題，在算法運行的過程中存在收斂速度慢、求解效率低等缺點。針對上述問題，提出了一種改進的蟻群算法，將螞蟻均勻分布在每一工件的首個工序，多種方法結(jié)合進行機器選擇和工序的排序，結(jié)合兩種信息素更新方式對信息素進行更新，最后利用FJSP算例對其進行仿真和與其他算法的對比，驗證了改進蟻群算法的優(yōu)越性。

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

1.1 問題描述

柔性作業(yè)車間調(diào)度問題是指有n個待加工工件在m臺設(shè)備上加工，其中待加工工件集合記為J={J1,J2,…,Jn}，機器集合記為M={M1,M2,…,Mm}，每個工件Ji不止包含一道工序，每道工序可以在不同的設(shè)備上完成加工，不同設(shè)備上加工同一個工序所需的時間可能不同。柔性作業(yè)車間調(diào)度問題主要包含工序排序和機器選擇兩個子問題，需要針對不同工件的工序合理安排加工機器，同時為每臺機器安排最合適的工序加工順序，從而使優(yōu)化目標(biāo)達(dá)到最優(yōu)。

工件的加工需滿足以下假設(shè)：

①某一時刻一個工件最多只能在一臺設(shè)備上進行加工；

②同一機器在同一時刻最多只能存在一個工件被加工；

③任一工序一旦開始加工，不可被中斷；

④只有同工件的工序加工具有先后約束；

⑤不同工件之間加工的優(yōu)先級相同；

⑥在零時刻任一機器都可以用于加工、任一工件都可以被加工。

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

本文以最小化最大完工時間為優(yōu)化目標(biāo)，將優(yōu)化目標(biāo)轉(zhuǎn)換成目標(biāo)函數(shù)，其函數(shù)表達(dá)式為：

minf=min[maxCi]

(1)

式中,Ci為工件Ji的完工時間。

約束條件如下：

①機器約束：

(2)

式中,k為機器號，k=1，2，…，m；若工件Ji的第j道工序在機器k上加工，xijk=1，否則xijk=0，式(2)表示同一臺設(shè)備在某一時刻最多只能加工一個工件。

②同一工件加工順序約束：

Sijk+tijk≤Si(j+1)k

(3)

式中,Sijk表示工件Ji的第j道工序在機器k上的加工開始時間;tijk表示在機器k上加工工件Ji的第j道工序所需的時間;Si(j+1)k表示開始在機器k上加工工件Ji的第j+1道工序的時間，式(3)表示同工件的工序加工順序有先后制約。

③加工過程不可中斷：

Sijk+tijk=Eijk

(4)

式中，Eijk表示在機器k上加工工件Ji的第j道工序的結(jié)束時間，式(4)表示任一工序一旦開始加工，就不可被中斷。

④加工時間約束：

Sijk≥0

(5)

該式表示在零時刻，任一工件均可開始加工。

2 改進蟻群算法求解FJSP問題

蟻群算法是模擬螞蟻覓食過程而形成的一類智能優(yōu)化算法，被廣泛應(yīng)用于求解旅行商問題(TSP)、路徑規(guī)劃等問題中。本文將柔性作業(yè)車間調(diào)度問題描述為一種特殊的旅行商問題，即螞蟻需遍歷完所有工件的所有工序并找到遍歷完成的最短時間。與TSP問題相比，F(xiàn)JSP問題更為復(fù)雜、約束條件更多，因此傳統(tǒng)的蟻群算法不能滿足對FJSP問題的求解，故本文提出了一種改進的蟻群算法，并通過算例對改進ACO算法的有效性進行了驗證。

2.1 初始化設(shè)計

選擇恰當(dāng)?shù)某跏蓟N群的方式可以提升求解速度，本文采用劉志虎[9]所提初始化種群的方式，讓所有螞蟻均勻分布在每一工件的第一道工序所組成的工序集合上，其優(yōu)點體現(xiàn)在避免螞蟻在初始時刻毫無目的的分布在其余工序上并開始后續(xù)的遍歷，從而浪費機會構(gòu)成無效遍歷，并致使算法搜索速度變慢。

其具體的實現(xiàn)過程為：建立一個禁忌表，禁忌表的大小和所有工件第一道工序所組成的工序集合大小相同，禁忌表中初始元素均為0，當(dāng)首只螞蟻隨機選擇工序集合中的一個工序后，將禁忌表中該元素所在位置的值變?yōu)?，并剔除工序集合中被選擇的這一工序。第二只螞蟻在剩下的工序集合中隨機選擇一個，并將禁忌表中對應(yīng)元素值變?yōu)?，并剔除工序集合中被選擇的這一工序。以此類推，直至禁忌表中所有元素的值均變?yōu)?(工序集合變?yōu)榭占?。若此時還有螞蟻沒有進行初始位置的選擇，需將之前的禁忌表清空，以此循環(huán)往復(fù)從而使所有螞蟻完成初始化。

在進行機器選擇時，為保證初始解的質(zhì)量和搜索空間的多樣性，做出以下改進：以70%的概率選擇加工工件i第j道工序最短的機器，20%的概率選擇可以最早開始加工完工件i的第j道工序的機器，10%的概率隨機選擇。通過三種機器選擇的方式，可以增加機器選擇的空間。

2.2 狀態(tài)轉(zhuǎn)移規(guī)則

螞蟻需要根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則來確定下一步要走的工序，從工序i到工序j運動過程中，按照式(6)的狀態(tài)轉(zhuǎn)移概率公式進行選擇。但若所有螞蟻都選擇轉(zhuǎn)移概率較大的工序作為下一步遍歷的工序，則易使算法收斂過早從而陷入局部最優(yōu)，故本文再求得各個候選工序的狀態(tài)轉(zhuǎn)移概率后，將其中70%的螞蟻采用輪盤賭來進行下一工序的選擇，30%的螞蟻以隨機選擇方式選擇下一工序。不僅能選擇狀態(tài)轉(zhuǎn)移概率較大的工序，也能夠有機會選擇到狀態(tài)轉(zhuǎn)移概率較小的工序，進一步擴大搜索空間，增加解的多樣性。

(6)

(7)

式中，τij(t)表示t時刻路徑(i,j)上的信息素濃度；ηij(t)為啟發(fā)函數(shù)；α為信息啟發(fā)式因子；β為期望啟發(fā)式因子；Tij表示等待選擇的待加工工序的加工時間；allowedk表示下一步可達(dá)工序節(jié)點的集合。

2.3 信息素更新規(guī)則

本文采用帶精英策略的蟻群算法(ASelite)的信息素更新方式來對螞蟻遍歷過程中分泌的信息素進行更新。該改進的模型是借鑒遺傳算法(GA)中的精英保留策略，其目的是使遍歷過程中歷史最優(yōu)的螞蟻所經(jīng)過的路徑對后續(xù)螞蟻有更強的吸引，每完成一次循環(huán)就給予精英螞蟻所搜索的路徑以額外的信息素增量，加速最優(yōu)路徑上的信息素增加，從而引導(dǎo)后續(xù)螞蟻能夠迅速的找到全局最優(yōu)路徑及全局最優(yōu)解。

帶精英策略的蟻群算法信息素的更新方式如式(8)所示：

τij(t+1)=(1-ρ)τij(t)+Δτij(t)+Δτ*(t)

(8)

(9)

(10)

(11)

但由于在賦予精英螞蟻以額外的信息素增量時，容易致使該路徑上信息素過量堆積而陷入局部最優(yōu)解從而導(dǎo)致搜索停滯，為克服算法陷入“早熟”，結(jié)合采用最大最小螞蟻系統(tǒng)(MMAS)對路徑上的信息素量進行約束，將螞蟻搜索路徑上的信息素設(shè)定一個最大值和一個最小值，即將信息素含量限定在[τmin,τmax]范圍之間。當(dāng)τij(t)<τmin(t)時，令τij(t)=τmin(t)；當(dāng)τij(t)>τmax(t)時，令τij(t)=τmax(t)。

2.4 改進蟻群算法執(zhí)行流程

所采用的改進的蟻群算法是在蟻群算法的基礎(chǔ)上，將所有螞蟻均勻分布在每一工件的第一道工序所組成的工序集合上，避免后續(xù)螞蟻的無效遍歷，并采用改進的機器選擇策略進行機器的選擇，并在求得各個候選工序的狀態(tài)轉(zhuǎn)移概率后以70%的螞蟻根據(jù)輪盤賭來選擇下一道工序，30%的螞蟻隨機選擇下一工序，從而避免算法過早收斂而導(dǎo)致陷入局部最優(yōu)，同時采用ASelite的信息素更新方式來對螞蟻遍歷過程中所分泌的信息素進行更新，結(jié)合采用最大最小螞蟻系統(tǒng)來避免路徑上的信息素過多積累從而遠(yuǎn)離最優(yōu)解，故改進了蟻群算法。改進蟻群算法求解FJSP流程圖如圖1所示。

圖1 改進蟻群算法求解FJSP流程圖

3 算例分析

為驗證改進算法的性能，采用該算法對不同規(guī)模的FJSP算例進行分析，算法程序是在MATLAB2018b的基礎(chǔ)上實現(xiàn)，處理器為Intel(R) Core(TM) i7-9750H CPU、RAM為8 GB、運行環(huán)境為Windows10(64位)的計算機上進行仿真。實驗參數(shù)設(shè)置如表1所示。

表1 實驗參數(shù)

首先選擇文獻(xiàn)[13]中規(guī)模大小為4×6的部分柔性作業(yè)車間調(diào)度算例進行分析，計算20次，得到圖2和圖3的運行結(jié)果。

圖2 4×6算例調(diào)度結(jié)果甘特圖 圖3 4×6算例收斂曲線圖

由圖2和圖3可知，文中改進蟻群算法的最優(yōu)完工時間為13 s，平均收斂代數(shù)為6.7，與文獻(xiàn)[10-13]相比，改進蟻群算法的最優(yōu)完工時間最短、收斂速度更快、搜索能力較優(yōu)，在20次的仿真實驗中，有19次取得最優(yōu)解，求解穩(wěn)定性較好，對比結(jié)果如表2所示。

表2 4×6不同算法仿真結(jié)果對比

為進一步證明改進蟻群算法的有效性和可行性，再對Kacem算例中分別代表部分柔性和完全柔性的8×8和10×10兩種規(guī)模算例進行仿真分析，分別計算20次得到最優(yōu)調(diào)度方案和收斂曲線圖如圖4～圖7所示。

圖4 8×8算例調(diào)度結(jié)果甘特圖 圖5 8×8算例收斂曲線圖

圖6 10×10算例調(diào)度結(jié)果甘特圖 圖7 10×10算例收斂曲線圖

由圖4～圖7可知，在8×8算例中，最大完工時間為14，在第15代趨于收斂，在10×10算例中，最大完工時間為7，在第13代趨于收斂，將本文改進蟻群算法與文獻(xiàn)[4]和文獻(xiàn)[14]中算法結(jié)果相比較，如表3所示。

表3 8×8、10×10不同算法仿真結(jié)果對比

由表3可見，改進的蟻群算法獲得了和其它文獻(xiàn)一樣的最優(yōu)解，求解質(zhì)量得到了保證，甚至在8×8算例中獲得比MOGA算法更短的完工時間，因此，證明了改進蟻群算法的有效性。與此同時，改進蟻群算法的平均運行時間為2.71 s，相比其他算法所求得最優(yōu)解花費更短的運行時間、求解效率更高。

4 總結(jié)

針對傳統(tǒng)的蟻群算法收斂速度慢、求解效率低，無法滿足FJSP優(yōu)化問題，本文在蟻群算法的基礎(chǔ)上對其機器選擇、工序選擇方法進行改進，避免了后續(xù)一些無效的遍歷，從而減少了搜索時間。并將ASelite的信息素更新方式和MMAS相結(jié)合，將信息素量限定在一定的范圍之內(nèi)，防止某條路徑上信息素過多堆積，使算法陷入“早熟”。最后通過仿真實驗和與其它實驗的對比分析，可以看出不管對于部分柔性和完全柔性作業(yè)車間調(diào)度，改進的蟻群算法均可快速求得最優(yōu)解。證明改進蟻群算法在求解柔性作業(yè)車間調(diào)度不同規(guī)模算例中的優(yōu)越性。