張國(guó)輝 閆少峰 陸熙熙 張海軍

摘 要：柔性作業(yè)車間調(diào)度問(wèn)題是一類重要的組合優(yōu)化問(wèn)題，實(shí)際生產(chǎn)過(guò)程中，產(chǎn)品搬運(yùn)、機(jī)床換模、更換刀具等間接加工活動(dòng)中存在運(yùn)輸時(shí)間和調(diào)整時(shí)間，會(huì)對(duì)生產(chǎn)周期產(chǎn)生影響。研究了同時(shí)考慮運(yùn)輸時(shí)間和調(diào)整時(shí)間的柔性作業(yè)車間調(diào)度問(wèn)題，建立以最小化最大完工時(shí)間、機(jī)器總負(fù)載、機(jī)器關(guān)鍵負(fù)載和工件的交貨期懲罰值為目標(biāo)的數(shù)學(xué)模型，并提出一種改進(jìn)的混合多目標(biāo)蟻群算法。結(jié)合問(wèn)題特征和算法特點(diǎn)設(shè)計(jì)了一種分布式編碼方式，采用改進(jìn)蟻群算法分別搜索各優(yōu)化目標(biāo)的最優(yōu)調(diào)度方案，針對(duì)調(diào)度方案集進(jìn)行非支配排序選擇，為了提高算法的搜索精度，提出了突變和靠攏操作。最后通過(guò)基準(zhǔn)實(shí)例和生產(chǎn)實(shí)例進(jìn)行仿真實(shí)驗(yàn)，并與改進(jìn)遺傳算法、MOGATS算法進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果表明提出的改進(jìn)混合多目標(biāo)蟻群算法是有效和可行的。

關(guān)鍵詞：改進(jìn)蟻群算法； 運(yùn)輸時(shí)間； 調(diào)整時(shí)間； 柔性作業(yè)車間調(diào)度問(wèn)題

中圖分類號(hào)：TH165?? 文獻(xiàn)標(biāo)志碼：A?? 文章編號(hào)：1001-3695（2023）12-026-3690-06

doi：10.19734/j.issn.1001-3695.2022.10.0546

Improved hybrid multiobjective ant colony optimization for flexible JobShop scheduling problem with transportation time and setup time

Abstract：Flexible job shop scheduling is an important combinatorial optimization problem. In the actual production process， there are transportation time and setup time in indirect processing activities such as product handling， and machine tool changing， which will affect the production cycle. This paper studied the flexible job shop scheduling problem considering both transportation time and setup time， established a mathematical model with the objectives of minimizing the maximum completion time， total workload， the workload of the critical machine， and penalties of earliness/tardiness， and proposed an improved hybrid multiobjective ant colony optimization. It designed a distributed coding method by combining the problem characteristics and algorithm features， using an improved ant colony optimization to search for the optimal scheduling solution for each optimization objective separately， performing nondominated sorting selection for the set of scheduling solutions， and proposing mutation and closeness operations in order to improve the search accuracy of the algorithm. Finally， it conducted simulation experiments using benchmark and production instance and compared them with the improved genetic algorithm and MOGATS algorithm， and the experimental results showed that the proposed improved hybrid multiobjective ant colony optimization is effective and feasible.

Key words：improved ant colony optimization; transportation time; setup time; flexible job shop scheduling problem

0 引言

隨著制造、信息和網(wǎng)絡(luò)技術(shù)的不斷提高，生產(chǎn)模式向著多品種、小批量、縮短生產(chǎn)周期、減少在制品庫(kù)存的方向發(fā)展［1］。傳統(tǒng)的制造系統(tǒng)和管控模式已難以適應(yīng)新時(shí)代的發(fā)展和要求。新一輪工業(yè)革命和產(chǎn)業(yè)變革正在進(jìn)行，德國(guó)和中國(guó)相繼提出“工業(yè)4.0”和“中國(guó)制造2025”等概念，新型制造系統(tǒng)需要向柔性化、信息化、數(shù)字化、智能化多方面發(fā)展［2，3］。在這樣的生產(chǎn)制造環(huán)境下，智能制造被視為新一代工業(yè)革命的核心技術(shù)，而車間調(diào)度智能化正是實(shí)現(xiàn)智能生產(chǎn)制造系統(tǒng)高效運(yùn)轉(zhuǎn)的關(guān)鍵之一。1954年Johnson［4］提出了兩臺(tái)機(jī)器的流水作業(yè)車間調(diào)度問(wèn)題，車間調(diào)度問(wèn)題一直是制造業(yè)中的重點(diǎn)關(guān)注對(duì)象，其中作業(yè)車間調(diào)度問(wèn)題（job shop scheduling problem，JSP）是車間調(diào)度問(wèn)題中最基本最典型的優(yōu)化問(wèn)題。柔性作業(yè)車間調(diào)度問(wèn)題（flexible job shop scheduling problem，F(xiàn)JSP）最初是由Brucker等人［5］在1990年提出的，它作為經(jīng)典車間調(diào)度問(wèn)題的延伸，是更加復(fù)雜的NP難問(wèn)題。

隨著多品種、小批量生產(chǎn)模式的興起，當(dāng)一臺(tái)機(jī)器處理不同的作業(yè)時(shí)，作業(yè)之間會(huì)因?yàn)楦鼡Q加工夾具或機(jī)器設(shè)置存在調(diào)整時(shí)間。工件在不同機(jī)器之間進(jìn)行加工需要進(jìn)行搬運(yùn)會(huì)存在運(yùn)輸時(shí)間。如果忽略掉調(diào)整時(shí)間和運(yùn)輸時(shí)間將大大降低調(diào)度方案的可行性［6］。特別在煉鋼車間中，如若不考慮運(yùn)輸時(shí)間和調(diào)整時(shí)間則可能會(huì)造成嚴(yán)重的質(zhì)量問(wèn)題［7］。因此，求解FJSP需同時(shí)考慮運(yùn)輸時(shí)間和調(diào)整時(shí)間。Fattahi等人［8］針對(duì)帶裝配過(guò)程的柔性作業(yè)車間調(diào)度問(wèn)題提出了一種混合并行變鄰域粒子群優(yōu)化算法。陳魁等人［9］在研究考慮運(yùn)輸時(shí)間的FJSP時(shí)，構(gòu)建了以最大完工時(shí)間、機(jī)器負(fù)載和總機(jī)器負(fù)載為目標(biāo)的多目標(biāo)優(yōu)化模型，并提出了一種小生境粒子群優(yōu)化算法和混合離散粒子群算法來(lái)求解。朱偉等人［10］針對(duì)考慮工件移動(dòng)時(shí)間約束的FJSP，提出了改進(jìn)遺傳算法求解，設(shè)計(jì)了自適應(yīng)變異規(guī)則以及混合子代產(chǎn)生模式。張洪亮等人［11］為求解考慮運(yùn)輸時(shí)間的分布式FJSP，提出了一種改進(jìn)的非支配排序遺傳算法（improved nondominated sorting genetic algorithm Ⅱ，INSGAⅡ），并設(shè)計(jì)了考慮運(yùn)輸時(shí)間的貪婪插入解碼方法，嵌入一種變鄰域搜索策略以提升Pareto前沿的質(zhì)量。查靚等人［12］研究了考慮順序相關(guān)調(diào)整時(shí)間的FJSP和設(shè)備維護(hù)計(jì)劃的集成優(yōu)化問(wèn)題，并提出了基于遺傳優(yōu)化的兩階段算法結(jié)合不等周期維護(hù)計(jì)劃來(lái)求解該問(wèn)題。Shen等人［13］針對(duì)帶有調(diào)整時(shí)間的柔性作業(yè)車間調(diào)度問(wèn)題，采用析取圖模型研究問(wèn)題的結(jié)構(gòu)特性，并提出了一種具有特定鄰域函數(shù)和多樣化結(jié)構(gòu)的禁忌搜索算法。雖然大多數(shù)學(xué)者研究FJSP系列問(wèn)題時(shí)一般采用啟發(fā)式算法，但也有一些學(xué)者采用群智能算法求解柔性作業(yè)車間調(diào)度問(wèn)題。李俊青等人［14］針對(duì)綜合考慮運(yùn)輸資源約束、工件間準(zhǔn)備時(shí)間約束的FJSP，提出了一種改進(jìn)的人工蜂群優(yōu)化算法，在局部搜索策略方面，提出了五種不同的調(diào)度鄰域結(jié)構(gòu)，并且為進(jìn)一步提升算法的全局搜索能力，嵌入了模擬退火接受準(zhǔn)則。李瑞等人［15］針對(duì)考慮最大完工時(shí)間和機(jī)器總負(fù)載的雙目標(biāo)FJSP提出了一種改進(jìn)的基于分解的多目標(biāo)進(jìn)化算法，設(shè)計(jì)了結(jié)合五種局部搜索策略的變鄰域搜索，增加了算法的后期收斂能力。張聞強(qiáng)等人［16］針對(duì)多目標(biāo)FJSP提出了一種基于多區(qū)域采樣策略的混合粒子群優(yōu)化算法，將粒子群算法與遺傳算法進(jìn)行結(jié)合，提升了算法搜索過(guò)程的多樣性并且避免算法陷入局部最優(yōu)。然而這些算法在一定程度上還存在搜索精度不高，收斂速度慢等缺點(diǎn)。蟻群算法具有很強(qiáng)的魯棒性，具有正反饋搜索機(jī)制，其搜索過(guò)程采用分布式計(jì)算，多個(gè)個(gè)體同時(shí)進(jìn)行并行計(jì)算，大大提高了算法的搜索范圍和收斂能力。本文要解決的多目標(biāo)問(wèn)題有四個(gè)優(yōu)化目標(biāo)，該問(wèn)題的關(guān)鍵就是盡可能擴(kuò)大解的搜索范圍，搜索到更多優(yōu)良的非支配解。因此結(jié)合算法特點(diǎn)和問(wèn)題特征采用蟻群算法來(lái)求解該問(wèn)題。

綜上所述，帶有運(yùn)輸時(shí)間和調(diào)整時(shí)間的柔性作業(yè)車間調(diào)度問(wèn)題（FJSP with transportation and setup time，F(xiàn)JSP_T/S）更加符合實(shí)際要求，目前有很多學(xué)者研究考慮運(yùn)輸時(shí)間的FJSP或考慮調(diào)整時(shí)間的FJSP，但同時(shí)考慮運(yùn)輸時(shí)間和調(diào)整時(shí)間的研究還是較少。因此，本文針對(duì)FJSP_T/S問(wèn)題，提出了一種改進(jìn)混合多目標(biāo)蟻群算法（hybrid multiobjective ant colony optimization，HMACO），并同時(shí)優(yōu)化最大完工時(shí)間、機(jī)器總負(fù)載、機(jī)器關(guān)鍵負(fù)載和工件的交貨期懲罰值四個(gè)目標(biāo)。

1 帶運(yùn)輸時(shí)間和調(diào)整時(shí)間的FJSP

1.1 問(wèn)題描述

帶運(yùn)輸時(shí)間和調(diào)整時(shí)間的柔性作業(yè)車間調(diào)度問(wèn)題可以描述為：有n個(gè)相互獨(dú)立的待加工的工件，它們構(gòu)成工件集合J={J1，J2，…，Ji，…，Jn}；有m臺(tái)可用于加工的機(jī)器，它們構(gòu)成機(jī)器集合M={M1，M2，…，Mj，…，Mm}。加工Ji須經(jīng)過(guò)hi道給定優(yōu)先順序約束的工序{Oi，1，Oi，2，…，Oi，hi}即同工件工序須按指定的順序進(jìn)行加工，如加工Oi，1須在Oi，2完成后才能開始。各工序有指定的可選機(jī)器集合Moi，jM（顯然1≤|Moi，j|≤m），其加工時(shí)間取決于選擇的加工機(jī)器。在工序加工間隙，存在著運(yùn)輸時(shí)間和調(diào)整時(shí)間。不同之處在于，同一工件的相鄰工序之間可能存在運(yùn)輸時(shí)間，而同一機(jī)器上相鄰工序之間可能存在著調(diào)整時(shí)間。調(diào)整時(shí)間也與加工順序相關(guān)，即當(dāng)同一臺(tái)機(jī)器上的兩道相鄰工序?qū)儆谕粋€(gè)工件時(shí)，它們之間的運(yùn)輸時(shí)間和調(diào)整時(shí)間為0。目的是找到可行調(diào)度方案使目標(biāo)函數(shù)達(dá)到最優(yōu)。該問(wèn)題的調(diào)度包含機(jī)器分配和工序排序兩個(gè)子問(wèn)題。機(jī)器分配是指將每道工序分配到一臺(tái)合適的機(jī)器上，而工序排序指的是確定每個(gè)機(jī)器上工序加工的優(yōu)先順序。

在本文中FJSP_T/S問(wèn)題存在如下假設(shè)：a）所有機(jī)器均在0時(shí)刻可用；b）所有工件均在0時(shí)刻釋放；c）所有工件首工序運(yùn)輸時(shí)間忽略不計(jì)；d）任何時(shí)候都禁止工序搶占作業(yè)，即所有工序一旦開始就不能被打斷；e）同一道工序同一時(shí)刻只能被一臺(tái)機(jī)器加工；f）每臺(tái)機(jī)器同時(shí)只能加工一道工序。

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

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

本文中的決策變量有oij，k和δij，k，其中用于確定oij，k工序與機(jī)床的選擇關(guān)系；δij，k用于確定工序是否存在調(diào)整和運(yùn)輸時(shí)間。

本文針對(duì)帶運(yùn)輸時(shí)間和調(diào)整時(shí)間的FJSP研究，綜合考慮四個(gè)目標(biāo)，建立如下的數(shù)學(xué)模型。該模型的四個(gè)目標(biāo)函數(shù)計(jì)算公式與約束條件如下：

其中：式（3）～（6）是四個(gè)優(yōu)化目標(biāo);f1為最后一道工序的加工結(jié)束時(shí)間； f2為整個(gè)生產(chǎn)過(guò)程所有機(jī)器上花費(fèi)的加工時(shí)間、運(yùn)輸時(shí)間和調(diào)整時(shí)間總和；f3為花費(fèi)時(shí)間最多的機(jī)器上花費(fèi)的加工時(shí)間、運(yùn)輸時(shí)間和調(diào)整時(shí)間總和；f4為工件i完工時(shí)間CJi（CJi=max（Ci））不在規(guī)定交貨期內(nèi)［DSi，DEi］造成的損失;若提前完工則需一定的存儲(chǔ)費(fèi)用，αs為提前每個(gè)單位時(shí)間花費(fèi)的存儲(chǔ)費(fèi)，若拖期完工則需支付違約費(fèi)用，αe為拖期每個(gè)單位時(shí)間花費(fèi)的違約費(fèi)。式（7） 確保每個(gè)工序分配給一臺(tái)且僅分配給一臺(tái)符合條件的機(jī)器。式（8）表示同一作業(yè)的連續(xù)操作之間的優(yōu)先級(jí)關(guān)系 。

2 改進(jìn)混合多目標(biāo)蟻群算法求解FJSP_T/S

本文提出一種改進(jìn)混合多目標(biāo)蟻群算法來(lái)求解FJSP_T/S。在該算法中提出了一種分布式編碼方式，先確定機(jī)器分配，將解空間分解為多個(gè)相互獨(dú)立的區(qū)域，再結(jié)合改進(jìn)蟻群算法搜索該區(qū)域內(nèi)各優(yōu)化目標(biāo)的最優(yōu)調(diào)度方案，從而提高解的搜索范圍。接著在蟻群算法的狀態(tài)轉(zhuǎn)移中加入了輪盤賭選擇法，避免算法陷入局部最優(yōu)，之后在信息素更新中加入了精英螞蟻選擇法，給最優(yōu)螞蟻路徑額外的信息素增加量提高收斂速度。另外提出一種將熵權(quán)法與非支配排序法結(jié)合起來(lái)的方法用于尋找非支配解。最后對(duì)機(jī)器分配部分提出突變和靠攏操作來(lái)提高搜索精度。

2.1 分布式編碼和初始化

改進(jìn)混合多目標(biāo)蟻群算法不同于傳統(tǒng)的兩段式編碼解碼搜索框架，結(jié)合問(wèn)題和算法特點(diǎn)提出一種分布式編碼方式。根據(jù)柔性作業(yè)車間調(diào)度問(wèn)題特點(diǎn)，分布式編碼分為機(jī)器選擇信息和工序排序信息，首先初始化產(chǎn)生機(jī)器選擇部分的初始信息列表，工序排序部分的初始信息列表由改進(jìn)混合多目標(biāo)蟻群算法進(jìn)行生成。機(jī)器選擇的信息表達(dá)方式如圖1所示，每條信息個(gè)體為一串整數(shù)，長(zhǎng)度為L(zhǎng)，L為所有工序的個(gè)數(shù)，Oi表示工件i的工序數(shù)，每個(gè)整數(shù)表示對(duì)應(yīng)工序的可選加工機(jī)器的排列序號(hào)，比如1號(hào)位置的數(shù)1表示實(shí)際加工機(jī)器2。在初始化時(shí)，對(duì)機(jī)器選擇部分采用完全隨機(jī)初始化方法，每個(gè)位置的整數(shù)為對(duì)應(yīng)工序的可選加工機(jī)器集中隨機(jī)選擇的機(jī)器序號(hào)。

2.2 改進(jìn)蟻群算法

蟻群優(yōu)化算法（ant colony optimization，ACO）是一種用來(lái)在圖中尋找優(yōu)化路徑的幾率型算法，是由自然界中螞蟻覓食的行為而啟發(fā)的。在螞蟻覓食過(guò)程中，蟻群總能夠按照尋找到一條從蟻巢和食物源的最優(yōu)路徑。使用蟻群算法求解FJSP時(shí)，螞蟻從0節(jié)點(diǎn)出發(fā)，遍歷每一個(gè)節(jié)點(diǎn)直至10節(jié)點(diǎn)，得到的工序序列即為問(wèn)題的一個(gè)解。

本文采用改進(jìn)的蟻群算法，依次對(duì)機(jī)器選擇種群中的個(gè)體進(jìn)行搜索，找出該機(jī)器選擇方案下，最大完工時(shí)間、機(jī)器總負(fù)載、機(jī)器關(guān)鍵負(fù)載和工件的交貨期懲罰值四個(gè)目標(biāo)上最優(yōu)的工序排序方案，得到四個(gè)不同目標(biāo)上的最優(yōu)調(diào)度方案，遍歷完機(jī)器選擇種群，便會(huì)得到4Npop個(gè)調(diào)度方案（Npop為種群個(gè)數(shù)）。單個(gè)蟻群主要步驟如下：

a）初始化信息素濃度表，濃度全為Cinit。

b）根據(jù)輪盤賭法確定各螞蟻的工序排序。以圖2信息素濃度表示意圖為例，行數(shù)為工件數(shù)、列數(shù)為工序數(shù)，每一格上的數(shù)值表示在加工對(duì)應(yīng)工序時(shí)，選擇工件的信息素。例如第（j，k）格上的數(shù)值為選擇工件j為第k道加工的工件工序。在確定螞蟻第k道加工工序時(shí)，先確定待加工工件集，然后采用式（9）計(jì)算各工件的適應(yīng)度值Pkij，將求得的各工件適應(yīng)度值規(guī)劃為一整個(gè)轉(zhuǎn)盤，各工件按照適應(yīng)度值分布在轉(zhuǎn)盤上，轉(zhuǎn)盤每轉(zhuǎn)一次，箭頭所指之處即為選擇一個(gè)工件。

其中：i為上一個(gè)確定的工件;j為allowedk集合中的工件，τij（k）為k時(shí)由工件i到j(luò)的信息素濃度;ηij（k）為k時(shí)由工件i到j(luò)距離dkij的倒數(shù)，實(shí)際上dkij反映的是k時(shí)加工工件j將產(chǎn)生的機(jī)器空閑間隙的大小，若間隙為0則說(shuō)明此時(shí)安排加工工件j能夠提升局部生產(chǎn)效率。由于0不能做分母，所以dkij最小取0.1。dkij的計(jì)算公式為

dkij=max{［max（SJ+T2，SM+T3）－SM］，0.1}（10）

其中：SM為機(jī)器的允許開始時(shí)間;SJ為工件的允許開始時(shí)間。

c）螞蟻選擇完所有工件時(shí)，根據(jù)式（3）～（6）計(jì)算螞蟻對(duì)應(yīng)方案的四個(gè)目標(biāo)值。各工件工序的時(shí)間信息在選擇過(guò)程同時(shí)已計(jì)算完畢，無(wú)須重復(fù)進(jìn)行編碼解碼操作。

d）記錄蟻群中最優(yōu)個(gè)體對(duì)應(yīng)的調(diào)度方案。

e）更新信息素。首先信息素?fù)]發(fā)，信息素濃度表上所有值乘上（1-Prho），然后所有螞蟻對(duì)應(yīng)的工序排序在信息素濃度表上相應(yīng)位置的值加1，最優(yōu)螞蟻對(duì)應(yīng)的工序排序在信息素濃度表上相應(yīng)位置的值加10。

f）判斷蟻群算法是否終止，依據(jù)參數(shù)中對(duì)算法終止條件的設(shè)定，判斷算法是否終止。若算法終止，則輸出當(dāng)前最優(yōu)解；反之，算法還沒有終止，則回到步驟b）繼續(xù)執(zhí)行。

2.3 非支配排序選擇

由于四個(gè)優(yōu)化目標(biāo)相互之間存在沖突無(wú)法比較，很難找到一個(gè)解使得所有目標(biāo)函數(shù)同時(shí)最優(yōu)，所以對(duì)改進(jìn)蟻群算法求得的規(guī)模為4Npop的調(diào)度方案集進(jìn)行快速非支配排序［17］。通過(guò)熵權(quán)法對(duì)目標(biāo)值進(jìn)行權(quán)重賦值，并計(jì)算該調(diào)度方案的綜合得分，然后對(duì)種群個(gè)體進(jìn)行分層和排序。

熵權(quán)法的基本思路是根據(jù)指標(biāo)變異性的大小來(lái)確定客觀權(quán)重。一般來(lái)說(shuō)，若某個(gè)指標(biāo)的熵值越小，表明指標(biāo)值的變異程度越大，提供的信息量越多，在綜合評(píng)價(jià)中所能起到的作用也越大，其權(quán)重也就越大。熵權(quán)法是一種客觀賦權(quán)法，能深刻反映出指標(biāo)的區(qū)分能力，進(jìn)而確定權(quán)重。熵權(quán)法具體步驟為

a）采用式（11）對(duì)目標(biāo)值進(jìn)行標(biāo)準(zhǔn)化處理：

其中：xij為第i個(gè)對(duì)象的第j個(gè)指標(biāo)數(shù)據(jù)原始值;yij為第i個(gè)對(duì)象的第j個(gè)指標(biāo)值，i=1，2，…，n；n=4×Npop。

b）采用式（12）計(jì)算第j個(gè)指標(biāo)下，第i個(gè)對(duì)象占該指標(biāo)的比重Yij：

c）計(jì)算第j個(gè)指標(biāo)的熵值ej和信息效用值dj，計(jì)算公式為

d）可以求得j項(xiàng)指標(biāo)值的權(quán)重wj，如式（15）所示。

e）計(jì)算綜合得分F，如式（16）所示。

F=∑wjyij（16）

得到各解的綜合得分后，再對(duì)各解進(jìn)行非支配排序，將解集劃分為不同的支配層如F1～F3等。依次選擇不同支配層的解，直到Fn層時(shí)，選擇解的個(gè)數(shù)大于等于Npop，如果選擇的解的個(gè)數(shù)恰好等于Npop，則將F1中的解的機(jī)器選擇信息提取出來(lái)組成種群F1，F(xiàn)2～Fn中的解的機(jī)器選擇信息提取出來(lái)組成種群F2n。否則，前n－1層的解（|F1|+|F2|+…+|F（n－1）|Npop）都被選中，并選擇第n層中綜合得分排名靠前的解，直到選擇的解的個(gè)數(shù)達(dá)到Npop，再將選擇的解的機(jī)器選擇信息分別提取種群F1和F2n中。

2.4 突變和靠攏

突變和靠攏是個(gè)體之間進(jìn)行信息交換的操作，可以將優(yōu)良個(gè)體的信息保留到下一代，提高算法的搜索精度。突變和靠攏操作只針對(duì)個(gè)體的機(jī)器選擇部分。

對(duì)選出的種群F1中的個(gè)體進(jìn)行突變操作，如圖3突變操作示意圖所示，隨機(jī)選擇個(gè)體的突變位置2和6，將其變換為該位置上可選機(jī)器數(shù)中的任一數(shù)字，突變后位置2中的3變換為1，位置6中2變換為3，生成新的信息個(gè)體。

對(duì)選出的種群F2n的個(gè)體執(zhí)行向種群F1的靠攏操作，首先計(jì)算每個(gè)F2n中的個(gè)體與F1中個(gè)體的海明距離d，海明距離為兩個(gè)個(gè)體中對(duì)應(yīng)位置不一樣的個(gè)數(shù)，如圖4所示，個(gè)體1和2的第1、2、4位的信息不一樣，所以個(gè)體1和2的海明距離等于3。然后F2n層中的每個(gè)個(gè)體隨機(jī)向一個(gè)最近的F1中個(gè)體靠攏，針對(duì)機(jī)器部分采用多點(diǎn)交叉變異的方式進(jìn)行靠攏，隨機(jī)生成交叉的多個(gè)位置，將F1層中個(gè)體信息替換到所要靠攏的對(duì)應(yīng)F2n中的個(gè)體上，F(xiàn)1中個(gè)體其余位置上的信息保持不變。

將進(jìn)行突變和靠攏操作后的兩個(gè)信息列表進(jìn)行合并，得到有2Npop個(gè)信息個(gè)體的新一代信息列表，并計(jì)算目標(biāo)函數(shù)值，記錄信息列表中個(gè)體的最優(yōu)解，將列表中的最優(yōu)個(gè)體與當(dāng)前最優(yōu)解進(jìn)行比較，若目標(biāo)函數(shù)值比當(dāng)前最優(yōu)解的小則替換當(dāng)前最優(yōu)解為列表最優(yōu)個(gè)體，反之當(dāng)前最優(yōu)解不變。

2.5 算法流程

改進(jìn)混合多目標(biāo)蟻群算法流程如圖5所示。

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

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

使用MATLAB 2017b 對(duì)該算例進(jìn)行仿真實(shí)驗(yàn)，運(yùn)行環(huán)境為Intel Core i7 CPU 2.2 GHz和8 GB RAM。本文提出的改進(jìn)HMACO算法參數(shù)經(jīng)過(guò)多次實(shí)驗(yàn)得出最佳組合，具體設(shè)置為：群體規(guī)模Npop=50、迭代次數(shù)Niter =50、突變概率Pmutr=0.5、蟻群最大迭代次數(shù)NACOiter =20、螞蟻數(shù)量Nant=10、初始信息素濃度Cinit=1、蒸發(fā)率Prho=0.2，目標(biāo)值f4里的懲罰系數(shù)αs=1、αe=5。

3.2 實(shí)驗(yàn)1

為了測(cè)試改進(jìn)HMACO算法的性能，采用的基準(zhǔn)算例來(lái)自Brandimarte［18］的數(shù)據(jù)集中的10個(gè)算例（MK01～MK10），實(shí)例中的運(yùn)輸時(shí)間與調(diào)整時(shí)間隨機(jī)生成，具體的實(shí)驗(yàn)數(shù)據(jù)來(lái)自于文獻(xiàn)［6］。采用改進(jìn)遺傳算法（IGA）［19］、MOGATS［20］與本文的改進(jìn)HMACO算法進(jìn)行比較。之所以選擇此兩種算法作為對(duì)比算法的原因是兩者都是研究的多目標(biāo)問(wèn)題，與本文內(nèi)容有一定的相似之處，文獻(xiàn)［18］同時(shí)考慮運(yùn)輸時(shí)間和調(diào)整時(shí)間，文獻(xiàn)［19］考慮了調(diào)整時(shí)間，而且這兩種算法都已經(jīng)被驗(yàn)證過(guò)是可行有效的。由于算法的不確定性，所有的實(shí)驗(yàn)都重復(fù)了10次，并計(jì)算10次結(jié)果的平均值作為最終的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比。

表2為三種算法的對(duì)比結(jié)果， f1～f4為對(duì)應(yīng)的四個(gè)目標(biāo)函數(shù)值，四個(gè)值的數(shù)值越小說(shuō)明算法的收斂能力越好。N為算法在該算例上尋找到的非支配解的數(shù)量，N的值越大說(shuō)明算法搜索到的解空間越大，算法的性能也就越好。表2中加粗字體表示對(duì)應(yīng)算法求解的結(jié)果優(yōu)于其他兩種算法，表2的最后一行統(tǒng)計(jì)了不同指標(biāo)在三種算法中的最優(yōu)數(shù)量。從表2中可以看出，在MK01上，三種算法所求的 f1值相同，但是改進(jìn)HMACO算法求得的另外三個(gè)目標(biāo)值都比IGA、MOGATS要好；從最后的統(tǒng)計(jì)結(jié)果來(lái)看，改進(jìn)HMACO算法求得的 f1值優(yōu)于其他兩種算法的實(shí)例有7個(gè)，f2值優(yōu)于其他兩種算法的實(shí)例有7個(gè)，f3值優(yōu)于其他兩種算法的實(shí)例有10個(gè)，f4值優(yōu)于其他兩種算法的實(shí)例有9個(gè)。特別是在MK04、MK05、MK08、MK09、MK10五個(gè)算例上，改進(jìn)HMACO算法求得的全部函數(shù)值均優(yōu)于其他兩種算法，說(shuō)明該算法收斂能力強(qiáng)于其他兩種算法。

圖6為三種算法在10個(gè)算例上尋找到非支配解數(shù)量的箱線圖，其數(shù)據(jù)來(lái)自于表2中的N。在表2中可以看到改進(jìn)HMACO算法除了MK03和MK08兩個(gè)算例，在其他算例中尋找到的非支配解數(shù)量都遠(yuǎn)超其他兩種算法。為了更科學(xué)地分析實(shí)驗(yàn)結(jié)果，在圖2中標(biāo)出了不同算法求得非支配解數(shù)量的中位數(shù)、平均值和異常值?？梢詮膱D2中明顯地看出，改進(jìn)HMACO算法在尋找非支配解數(shù)量上面遠(yuǎn)超于其他兩種算法。因此，表明本文改進(jìn)HMACO算法可行有效。

3.3 實(shí)驗(yàn)2

除了在基準(zhǔn)數(shù)據(jù)集上進(jìn)行算法有效性測(cè)試之外，還用改進(jìn)HMACO算法求解實(shí)際的考慮運(yùn)輸時(shí)間和調(diào)整時(shí)間的柔性作業(yè)車間調(diào)度問(wèn)題。該實(shí)例是來(lái)自鄭州某機(jī)械廠生產(chǎn)車間的10×6的帶運(yùn)輸時(shí)間和調(diào)整時(shí)間的FJSP，實(shí)例的數(shù)據(jù)如表3所示，表4為運(yùn)輸時(shí)間。分別采用IGA、MOGATS與本文改進(jìn)HMACO算法進(jìn)行求解，表5為三種算法求得的解集中各目標(biāo)的最優(yōu)值與尋找到的非支配解的數(shù)量。

在求解帶運(yùn)輸時(shí)間和調(diào)整時(shí)間的10×6柔性作業(yè)車間調(diào)度實(shí)例問(wèn)題上，所求得的四個(gè)目標(biāo)值的最優(yōu)值分別為92、419、77、171，其中三個(gè)目標(biāo)均優(yōu)于其他兩種算法，只有在f4上略差于IGA。在尋找非支配解的能力上，改進(jìn)HMACO算法找到99個(gè)非支配解，非支配解數(shù)量也遠(yuǎn)超其他兩種算法。綜合比較本文改進(jìn)HMACO算法優(yōu)于其他兩種算法。圖7（a）～（c）分別為改進(jìn)HMACO算法、MOGATS、IGA得到的Pareto最優(yōu)前沿圖，從三張圖片的對(duì)比中可以明顯看出，本文改進(jìn)HMACO算法找到的非支配解的數(shù)量更多，而且解空間的分布更加集中，說(shuō)明算法的收斂性更好。圖8為改進(jìn)HMACO算法的運(yùn)算收斂曲線。圖9為改進(jìn)HMACO算法求得的Pareto解集中f1值最優(yōu)解的甘特圖，機(jī)器加工工件前需要工人進(jìn)行模具的更換，存在機(jī)器調(diào)整時(shí)間，該甘特圖中所有淺棕色方框即代表加工該工序的機(jī)器調(diào)整時(shí)間，如在機(jī)器1上加工的101工序的第一個(gè)淺棕色方框，工件在不同機(jī)器上加工中間需要有運(yùn)輸過(guò)程，該圖中所有淺藍(lán)色方框即對(duì)應(yīng)此工序的運(yùn)輸時(shí)間，如101工序的第三個(gè)淺藍(lán)色方框。兩者中間的綠色方框即是101工序的加工時(shí)間。綜合以上兩個(gè)實(shí)驗(yàn)的結(jié)果可以得到，本文改進(jìn)混合多目標(biāo)蟻群算法是有效和可行的。

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

針對(duì)FJSP_T/S問(wèn)題，本文提出一種改進(jìn)混合多目標(biāo)蟻群算法進(jìn)行求解，結(jié)合改進(jìn)的蟻群算法和非支配排序方法，同時(shí)優(yōu)化最大完工時(shí)間、機(jī)器總負(fù)載、機(jī)器關(guān)鍵負(fù)載和工件的交貨期懲罰值四個(gè)目標(biāo)值，對(duì)10個(gè)基準(zhǔn)問(wèn)題以及生產(chǎn)實(shí)例問(wèn)題進(jìn)行實(shí)驗(yàn)分析，并將改進(jìn)HMACO算法與兩種不同的算法進(jìn)行比較，驗(yàn)證了本文算法可以有效解決FJSP_T/S問(wèn)題。

在柔性作業(yè)車間實(shí)際生產(chǎn)過(guò)程中，除了工件運(yùn)輸和機(jī)器調(diào)整，還容易受到各種復(fù)雜因素的影響，例如訂單的緊急插單、機(jī)器故障等。下一步將關(guān)注具有實(shí)時(shí)運(yùn)輸?shù)膭?dòng)態(tài)柔性車間調(diào)度問(wèn)題，包括考慮緩沖區(qū)、運(yùn)輸能力限制和機(jī)器故障重新分配等。

參考文獻(xiàn)：

[1]張益，馮毅萍，榮岡.智慧工廠的參考模型與關(guān)鍵技術(shù)［J］.計(jì)算機(jī)集成制造系統(tǒng)，2016，22（1）：1-12.（Zhang Yi， Feng Yiping， Rong Gang. Reference model and key technologies of smart factory［J］.Computer Integrated Manufacturing Systems，2016，22（1）：1-12.）

［2]Li Bohu，Hou Baocun，Yu Wentao， et al.Applications of artificial intelligence in intelligent manufacturing： a review［J］.Frontiers of Information Technology & Electronic Engineering，2017，18（1）：86-96.

［3]李清，唐騫璘，陳耀棠，等.智能制造體系架構(gòu)、參考模型與標(biāo)準(zhǔn)化框架研究［J］.計(jì)算機(jī)集成制造系統(tǒng)，2018，24（3）：539-549.（Li Qing， Tang Qianlin， Chen Yaotang， et al. Research on intelligent manufacturing architecture， reference model and standardization framework［J］.Computer Integrated Manufacturing Systems，2018，24（3）： 539-549.）

［4]Johnson S M. Optimal twoand threestage production schedules with setup times included［J］.Naval Research Logistics Quarterly，1954，1（1）： 61-68.

［5]Brucker P， Schlie R. JobShop scheduling with multipurpose machines［J］.Computing，1990，45（4）：369-375.

［6]Sun Jinghe， Zhang Guohui， Lu Jiao， et al. A hybrid manyobjective evolutionary algorithm for flexible JobShop scheduling problem with transportation and setup times［J］.Computers & Operations Research，2021，132：105263.

［7]Zhang Hongliang， Xu Gongjie， Pan Ruilin， et al. A novel heuristic method for the energyefficient flexible JobShop scheduling problem with sequencedependent setup and transportation time［J］.Engineering Optimization，2021，54（10）：1646-1667.

［8]Fattahi P， Rad N B， Daneshamooz F， et al. A new hybrid particle swarm optimization and parallel variable neighborhood search algorithm for flexible job shop scheduling with assembly process［J］.Assembly Automation，2020，40（3）：419-432.

［9]陳魁， 畢利. 改進(jìn)粒子群算法在考慮運(yùn)輸時(shí)間下的FJSP研究［J］.系統(tǒng)仿真學(xué)報(bào)，2021，33（4）：845-853.（Chen Kui， Bi Li. Research on improved particle swarm algorithm on FJSP considering transport time［J］.Journal of System Simulation，2021，33（4）：845-853.）

［10]朱偉，趙水晶.考慮工件移動(dòng)和成本的多目標(biāo)柔性作業(yè)車間調(diào)度問(wèn)題優(yōu)化研究［J］.現(xiàn)代制造工程，2019（7）：104-110，95.（Zhu Wei， Zhao Shuijing. Research on optimization of multiobjective flexible job workshop scheduling problem considering workpiece movement and cost［J］.Modern Manufacturing Engineering，2019（7）：104-110，95.）

［11]張洪亮，徐公杰，鮑薔，等.考慮運(yùn)輸時(shí)間的分布式柔性作業(yè)車間綠色調(diào)度［J］.中國(guó)機(jī)械工程，2022，33（21）：2554-2563，2645.（Zhang Hongliang， Xu Gongjie， Bao Qiang， et al. Green scheduling of distributed flexible workshop considering transport time［J］.China Mechanical Engineering，2022，33（21）：2554-2563，2645.

［12]查靚，金花，潘志成，等.基于順序相關(guān)調(diào)整時(shí)間的FJSP與設(shè)備維護(hù)計(jì)劃集成優(yōu)化［J］.組合機(jī)床與自動(dòng)化加工技術(shù)，2016，507（5）：155-160.（Zha Liang， Jin Hua， Pan Zhicheng， et al. Integrated optimization of FJSP and equipment maintenance plan based on sequencedependent adjustment time［J］.Combined Machine Tool and Automated Machining Technology，2016，507（5）：155-160.）

［13]Shen Liji， DauzèrePérès S， Neufeld J S. Solving the flexible job shop scheduling problem with sequencedependent setup times［J］.European Journal of Operational Research，2018，265（2）：503-516.

［14]李俊青，杜宇，田杰，等.帶運(yùn)輸資源約束柔性作業(yè)車間調(diào)度問(wèn)題的人工蜂群算法［J］.電子學(xué)報(bào)，2021，49（2）：324-330.（Li Junqing， Du Yu， Tian Jie， et al. Artificial bee swarm algorithm with flexible workshop scheduling problem with transport resource constraint［J］.Acta Electronic Sinica，2021，49（2）：324-330.）

［15]李瑞，龔文引.改進(jìn)的基于分解的多目標(biāo)進(jìn)化算法求解雙目標(biāo)模糊柔性作業(yè)車間調(diào)度問(wèn)題［J］.控制理論與應(yīng)用，2022，39（1）：31-40.（Li Rui， Gong Wenyin. Improved decompositionbased multiobjective evolution algorithm to solve the twoobjective fuzzy flexible job shop scheduling problem［J］.Control Theory and Applications，2022，39（1）：31-40.）

［16]張聞強(qiáng)，邢征，楊衛(wèi)東.基于多區(qū)域采樣策略的混合粒子群優(yōu)化求解多目標(biāo)柔性作業(yè)車間調(diào)度問(wèn)題［J］.計(jì)算機(jī)應(yīng)用，2021，41（8）：2249-2257.（Zhang Wenqiang， Xing Zheng， Yang Weidong. Hybrid particle swarm optimization solution for multiobjective flexible job shop scheduling problem based on multiregion sampling strategy［J］.Journal of Computer Applications，2021，41（8）：2249-2257.）

［17]Deb K， Pratap A， Agarwal S， et al. A fast and elitist multiobjective genetic algorithm： NSGAⅡ［J］.IEEE Trans on Evolutionary Computation，2002，6（2）：182-197.

［18]Brandimarte P. Routing and scheduling in a flexible job shop by tabu search［J］.Annals of Operations Research，1993，41（3）：157-183.

［19]Zhang Guohui， Hu Yifan， Sun Jinghe， et al. An improved genetic algorithm for the flexible job shop scheduling problem with multiple time constraints［J］.Swarm and Evolutionary Computation，2020，54：100664.

［20]張國(guó)輝，衛(wèi)世文，張海軍，等.考慮時(shí)間與能耗約束的柔性作業(yè)車間調(diào)度優(yōu)化［J］.計(jì)算機(jī)應(yīng)用研究，2022，39（12）：3673-3677.（Zhang Guohui， Wei Shiwen， Zhang Haijun， et al. Optimization of flexible job shop scheduling considering time and energy constraints［J］.Application Research of Computers，2022，39（12）：3673-3677.）