擴(kuò)展帝國(guó)競(jìng)爭(zhēng)算法求解分布式不相關(guān)并行機(jī)車間調(diào)度問(wèn)題

摘 要：針對(duì)考慮加工約束的分布式不相關(guān)并行機(jī)車間調(diào)度問(wèn)題，以總運(yùn)輸成本、工廠間并行機(jī)齊停評(píng)價(jià)函數(shù)和工件種類平均切換次數(shù)均衡評(píng)價(jià)函數(shù)為優(yōu)化目標(biāo)，提出一種擴(kuò)展帝國(guó)競(jìng)爭(zhēng)算法進(jìn)行求解。該算法在原始帝國(guó)競(jìng)爭(zhēng)算法的基礎(chǔ)上，增加了適于工廠分配的初始化工廠-工件序列群；根據(jù)傳統(tǒng)帝國(guó)競(jìng)爭(zhēng)算法容易陷入局部最優(yōu)的缺點(diǎn)，將較劣序列同化分為了外部同化機(jī)制和內(nèi)部同化機(jī)制，采用局部和全局相結(jié)合的搜索方式實(shí)現(xiàn)擴(kuò)展帝國(guó)競(jìng)爭(zhēng)算法的智能搜索行為；采用部分匹配交叉和單點(diǎn)變異更新工廠-工件序列群，保證工廠-工件序列的多樣性。最后設(shè)計(jì)3個(gè)不同規(guī)模12個(gè)算例，通過(guò)仿真實(shí)驗(yàn)驗(yàn)證所提算法的有效性，同時(shí)對(duì)比相關(guān)領(lǐng)域研究成果驗(yàn)證了該算法在求解分布式多目標(biāo)不相關(guān)并行機(jī)調(diào)度問(wèn)題方面的優(yōu)越性。

關(guān)鍵詞：擴(kuò)展帝國(guó)競(jìng)爭(zhēng)算法；分布式不相關(guān)并行機(jī)車間調(diào)度問(wèn)題；總運(yùn)輸成本；工廠間并行機(jī)齊停評(píng)價(jià)函數(shù)；工廠間工件種類平均切換次數(shù)均衡評(píng)價(jià)函數(shù)

中圖分類號(hào)：TP181 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001-3695（2024）09-027-2758-08

doi：10.19734/j.issn.1001-3695.2023.12.0619

Extended empire competition algorithm for distributed unrelated

parallel machine workshop scheduling problem

Li Lishan1，Tao Yifei1，He Yi2，Zhou Guocheng1，Wang Jingjie1

（1.Faculty of Mechanical & Electrical，Kunming University of Science & Technology，Kunming 650504，China;2.Honghe Cigarette Factory of Hongyun Honghe Tobacco（Group）Co.，Ltd.，Honghe Yunnan 652399，China）

Abstract：Aiming at the distributed unrelated parallel machine scheduling problem with machining constraints，this paper proposed an extended empire competition algorithm to solve the problem，which took the total transportation cost，evaluation function for simultaneous shutdown of parallel machines among factories and equilibrium evaluation function for average switching frequency of workpiece types among factories as optimization objectives.Based on the original empire competition algorithm，this algorithm added an initial factory-workpiece sequence group suitable for factory assignment.According to the shortcoming of the traditional empire competition algorithm that it was easy to fall into the local optimum，this paper divided the inferior sequence assimilation into external assimilation mechanism and the internal assimilation mechanism.The extended empire competition algorithm combined local and global search methods to realize the intelligent search behavior.This paper used the partial matching crossover and single point mutation to update the factory-workpiece sequence group and ensure the diversity of the factory-workpiece sequence.Finally，this paper designed three different scales of 12 examples and verified the effectiveness of the proposed algorithm through simulation experiments.At the same time，this paper verified the advantages of the proposed algorithm in solving the distributed multi-objective unrelated parallel machine scheduling problem by comparing the research results in related fields.

Key words：extended empire competition algorithm;distributed unrelated machine parallel workshop scheduling;total transportation cost;evaluation function for simultaneous shutdown of parallel machines among factories;equilibrium evaluation function for average switching frequency of workpiece types among factories

0 引言

隨著經(jīng)濟(jì)全球化進(jìn)程的加速推進(jìn)，制造業(yè)作為國(guó)民經(jīng)濟(jì)的重要支柱，已經(jīng)從大規(guī)模、大批量的集中式制造轉(zhuǎn)變?yōu)樾∫?guī)模、小批量的分布式制造，相應(yīng)的生產(chǎn)調(diào)度問(wèn)題也從單一工廠的調(diào)度問(wèn)題擴(kuò)展為多個(gè)工廠的分布式調(diào)度問(wèn)題［1，2］。分布式并行機(jī)調(diào)度問(wèn)題（distributed parallel machine scheduling problem，DPMSP）是為了企業(yè)能快速響應(yīng)市場(chǎng)需求、提高企業(yè)競(jìng)爭(zhēng)力，由傳統(tǒng)單一工廠的并行機(jī)調(diào)度問(wèn)題（parallel machine scheduling problem，PMSP）［3，4］擴(kuò)展為在多個(gè)工廠環(huán)境下的分布式并行機(jī)調(diào)度問(wèn)題，已經(jīng)廣泛應(yīng)用到了多個(gè)行業(yè)，如煙草、鋼鐵等，因此研究DPMSP具有重要的理論意義和實(shí)際應(yīng)用價(jià)值。

近年來(lái)，DPMSP的研究取得了一些進(jìn)展。文獻(xiàn)［5，6］以最小化作業(yè)提前/拖期及總完成時(shí)間之和為優(yōu)化目標(biāo)，提出一種混合整數(shù)規(guī)劃模型，并設(shè)計(jì)了一種超啟發(fā)式算法解決分布式并行機(jī)調(diào)度問(wèn)題；文獻(xiàn)［7］針對(duì)分布式并行機(jī)與裝配調(diào)度問(wèn)題，以最小化平均流程時(shí)間和延遲作業(yè)的數(shù)量為優(yōu)化目標(biāo)，提出一種新的泛化和元啟發(fā)式算法，使用田口方法來(lái)校準(zhǔn)和討論元啟發(fā)式參數(shù)，實(shí)驗(yàn)結(jié)果證明了所提算法在解決中規(guī)模問(wèn)題的有效性；文獻(xiàn)［8］考慮了在不同并行生產(chǎn)線上的幾種產(chǎn)品的同時(shí)批量加工和調(diào)度問(wèn)題，以最小化與序相關(guān)的設(shè)置和生產(chǎn)成本為優(yōu)化目標(biāo)，通過(guò)結(jié)合局部搜索元策略閾值接受和模擬退火，結(jié)合對(duì)偶再優(yōu)化解決了該問(wèn)題；文獻(xiàn)［9］針對(duì)設(shè)備維修導(dǎo)致的生產(chǎn)延遲問(wèn)題，提出一種輔助校正的優(yōu)化方法，建立了聯(lián)合生產(chǎn)和預(yù)防性維修調(diào)度問(wèn)題的數(shù)學(xué)模型和仿真模型；文獻(xiàn)［10］研究了分布式制造環(huán)境下的裝配柔性作業(yè)車間生產(chǎn)與配送兩階段聯(lián)合調(diào)度問(wèn)題，結(jié)合實(shí)際的生產(chǎn)情況，考慮供應(yīng)鏈下生產(chǎn)與配送過(guò)程所產(chǎn)生的庫(kù)存成本，以最小化生產(chǎn)和配送的總成本為聯(lián)合調(diào)度優(yōu)化目標(biāo)，提出一種改進(jìn)鯨魚算法進(jìn)行求解；文獻(xiàn)［11］針對(duì)分布式兩階段裝配流水車間調(diào)度問(wèn)題，以最小化總延遲時(shí)間為優(yōu)化目標(biāo)，提出一種帝國(guó)競(jìng)爭(zhēng)-協(xié)作算法，并給出一種新型帝國(guó)競(jìng)爭(zhēng)策略來(lái)提高算法的搜索效率，通過(guò)實(shí)驗(yàn)驗(yàn)證了所提算法在解決含不相關(guān)并行機(jī)的分布式車間調(diào)度問(wèn)題方面的有效性；文獻(xiàn)［12］提出了一種混合帝國(guó)主義競(jìng)爭(zhēng)算法來(lái)解決分布式并行機(jī)調(diào)度問(wèn)題，以最小化總延遲為優(yōu)化目標(biāo)，將所有帝國(guó)分為最強(qiáng)帝國(guó)、最弱帝國(guó)和其他帝國(guó)三種類型，不同帝國(guó)使用不同搜索算子，有效解決了所研究的問(wèn)題；文獻(xiàn)［13］研究了異構(gòu)生產(chǎn)網(wǎng)絡(luò)中具有最大完工時(shí)間最小化的分布式不相關(guān)并行機(jī)調(diào)度問(wèn)題，并直接將其簡(jiǎn)化為擴(kuò)展機(jī)器分配問(wèn)題，提出一種新的帶有記憶的帝國(guó)主義競(jìng)爭(zhēng)算法進(jìn)行求解；文獻(xiàn)［14］提出一種求解異構(gòu)工廠分布式并行機(jī)調(diào)度問(wèn)題的新型帝國(guó)競(jìng)爭(zhēng)算法，以最小化最大完成時(shí)間作為優(yōu)化目標(biāo)，將問(wèn)題簡(jiǎn)化為工廠分配子問(wèn)題進(jìn)行求解。綜上所述，目前已有部分文獻(xiàn)對(duì)分布式不相關(guān)并行機(jī)車間調(diào)度問(wèn)題或含有不相關(guān)并行機(jī)的分布式車間調(diào)度問(wèn)題進(jìn)行了研究，特別是近年來(lái)部分學(xué)者采用帝國(guó)競(jìng)爭(zhēng)算法解決分布式不相關(guān)并行機(jī)車間調(diào)度問(wèn)題，并取得了一定的研究成果。本文基于現(xiàn)有研究成果，考慮到實(shí)際工況下的加工約束，以及運(yùn)輸成本、并行機(jī)齊停、工件種類切換次數(shù)等優(yōu)化目標(biāo)，針對(duì)分布式不相關(guān)并行機(jī)車間調(diào)度問(wèn)題展開研究。

帝國(guó)競(jìng)爭(zhēng)算法（imperial competition algorithm，ICA）是受古代帝國(guó)和殖民地的啟發(fā)于2007年提出的一種智能優(yōu)化算法，與粒子群優(yōu)化、蟻群等算法一樣，都屬于基于群體的隨機(jī)優(yōu)化搜索算法。因其具有較強(qiáng)的局部搜索能力和較快的收斂速度，ICA已廣泛應(yīng)用于生產(chǎn)調(diào)度、路徑規(guī)劃［15］、旅行商問(wèn)題［16］、函數(shù)優(yōu)化［17］、電網(wǎng)控制和電能分配問(wèn)題［18］等。

本文針對(duì)分布式不相關(guān)并行機(jī)車間調(diào)度問(wèn)題（distributed unrelated parallel machines scheduling problem，DUPMSP），提出一種擴(kuò)展帝國(guó)競(jìng)爭(zhēng)算法（extended empire competition algorithm，EICA），以總運(yùn)輸成本、工廠間并行機(jī)齊停評(píng)價(jià)函數(shù)和工件種類平均切換次數(shù)均衡評(píng)價(jià)函數(shù)為優(yōu)化目標(biāo)。該算法在初始階段增加適合工廠分配的初始化工廠-工件序列群，將較劣序列同化分為較劣序列外部同化和內(nèi)部同化，并且采用部分匹配交叉和單點(diǎn)變異以更新工廠-工件序列，有效解決ICA容易陷入局部最優(yōu)的情況，最后通過(guò)Pareto非支配排序得到最優(yōu)解集。

1 問(wèn)題描述

分布式不相關(guān)并行機(jī)車間調(diào)度問(wèn)題（DUPMSP）描述如下：假設(shè)i個(gè)工件（i=1，2，…，n）分配給位于不同地區(qū)和地理環(huán)境的f個(gè)工廠（f=1，2，…，F(xiàn)）進(jìn)行加工。工廠f內(nèi)有mf臺(tái)不相關(guān)并行機(jī)Mf 1，…，Mfmf，總共N=∑Ff=1mf臺(tái)并行機(jī)，每臺(tái)并行機(jī)加工同一工件的加工時(shí)間不同，并行機(jī)的加工時(shí)間包含并行機(jī)調(diào)整時(shí)間，并行機(jī)加工時(shí)間服從均勻分布，一些工件只能在特定工廠的特定并行機(jī)上加工。圖1為分布式不相關(guān)并行機(jī)車間調(diào)度模型示意圖。

2.7 工廠-工件序列更新

通過(guò)快速非支配排序，選擇第一階層的工廠-工件序列作為父代工廠-工件序列。如果第一階層工廠-工件序列的數(shù)量沒有達(dá)到初始工廠-工件序列的數(shù)量，隨機(jī)從第二和三階層中選擇一定數(shù)量的工廠-工件序列組成初始工廠-工件序列的數(shù)量，通過(guò)部分匹配交叉和單點(diǎn)變異操作對(duì)工廠-工件序列進(jìn)行更新，保證工廠-工件序列多樣性。

部分匹配交叉的操作步驟如下：

a）選擇交叉區(qū)域。以一定的概率選擇兩個(gè)工廠-工件序列作為父代，在父代序列中隨機(jī)選擇一個(gè)交叉區(qū)域，如圖8步驟a）所示。工廠-工件序列1：［9 3 6 4 10 2 5 7 1 8］和工廠-工件序列2：［3 7 9 5 10 4 8 6 1 2］，隨機(jī)選擇兩個(gè)交叉點(diǎn)1、2確定交叉區(qū)域，兩個(gè)工廠-工件序列被選中的區(qū)域位置相同，圖中灰色部分為交叉區(qū)域。

b）交換被選中序列。交換兩父代被選中的區(qū)域，生成兩個(gè)新的工廠-工件序列，如圖8步驟b）所示。交換被選中的序列后生成［9 3 9 5 10 4 8 7 1 8］和［3 7 6 4 10 2 5 6 1 2］。

c）元素沖突檢測(cè)。根據(jù)交換的兩個(gè)序列建立映射關(guān)系，以圖8中步驟c）的8-5-4-2為例，可以看到交換被選中序列后得到的結(jié)果中工廠-工件序列［9 3 9 5 10 4 8 7 1 8］存在兩個(gè)重復(fù)序號(hào)8，這時(shí)通過(guò)映射關(guān)系將選中區(qū)域之外的一個(gè)8轉(zhuǎn)變?yōu)?，依此類推到無(wú)沖突為止。其他重復(fù)元素按照這種映射關(guān)系進(jìn)行映射，確保新生成的工廠-工件序列中無(wú)元素沖突。

d）生成新序列。通過(guò)元素沖突檢測(cè)，生成兩個(gè)新工廠-工件序列。

單點(diǎn)變異與較劣序列革命類似，其操作步驟如下：

a）選擇變異點(diǎn)。在部分匹配交叉之后，按一定的概率將新生成的工廠-工件序列中的某個(gè)元素隨機(jī)轉(zhuǎn)變?yōu)榇诵蛄兄械钠渌?。如圖9中步驟a）所示，一個(gè)工廠-工件序列［6 3 9 5 10 4 8 7 1 2］，隨機(jī)選擇一個(gè)元素8作為變異點(diǎn)，變異為元素3。

b）元素沖突檢測(cè)，變異后變異點(diǎn)的元素不變，與變異點(diǎn)發(fā)生沖突的其他位置的元素轉(zhuǎn)變?yōu)樽儺惽白儺慄c(diǎn)的元素。如圖9中步驟b）所示，變異后的序列［6 3 9 5 10 4 3 7 1 2］進(jìn)行元素沖突檢測(cè)，圖中變異前變異點(diǎn)位置元素為8，變異后變異點(diǎn)元素為3，元素3在序列中有兩個(gè)，則元素8替換與變異點(diǎn)元素3沖突的另一個(gè)3。

c）生成新序列。生成一個(gè)新的工廠-工件序列。

3 計(jì)算實(shí)驗(yàn)

為了驗(yàn)證EICA在求解分布式不相關(guān)并行機(jī)車間調(diào)度多目標(biāo)問(wèn)題的有效性，進(jìn)行了分布式車間小規(guī)模、中規(guī)模和大規(guī)模的仿真實(shí)驗(yàn)。所有測(cè)試算例均通過(guò)Plant Simulation軟件建立仿真模型，用Simtalk編寫優(yōu)化算法程序。分布式不相關(guān)并行機(jī)車間仿真模型如圖10所示。

通過(guò)大量仿真實(shí)驗(yàn)得到相關(guān)參數(shù)設(shè)置為：工廠-工件序列即版圖規(guī)模為50，并行機(jī)-工件序列即國(guó)家數(shù)量為100，成為帝國(guó)的概率a=0.5，工廠-工件序列更新中交叉概率為0.95，變異概率為0.05。

3.1 評(píng)價(jià)指標(biāo)

參照文獻(xiàn)［19］對(duì)算法性能評(píng)價(jià)指標(biāo)的選取，將Pareto非支配解的個(gè)數(shù)NS（單位：個(gè)）、反世代距離IGD、解間距SP作為評(píng)價(jià)算法性能的指標(biāo)。

3.2 測(cè)試算例與對(duì)比算法

本文選用分布式工廠的小規(guī)模、中規(guī)模和大規(guī)模共12個(gè)算例分別測(cè)試所提算法的有效性，表2描述了算例的基本信息，每個(gè)工件的加工時(shí)間和運(yùn)輸成本均服從均勻分布，其中工件數(shù)n=50，60，70，80的4個(gè)算例屬于小規(guī)模算例，n=90，100，110，120的4個(gè)算例屬于中規(guī)模算例，n=140，160，180，200的4個(gè)算例屬于大規(guī)模算例。

本文選擇以下兩種對(duì)比算法：張清勇等人［14］針對(duì)異構(gòu)工廠分布式并行機(jī)調(diào)度問(wèn)題提出新型帝國(guó)競(jìng)爭(zhēng)算法（ICA），原文通過(guò)大量實(shí)驗(yàn)表明新型ICA具有較強(qiáng)的搜索優(yōu)勢(shì)和較好的穩(wěn)定性；軒華等人［20］針對(duì)含不相關(guān)并行機(jī)的分布式流水車間調(diào)度問(wèn)題提出混合離散人工蜂群算法（HDABC），原文通過(guò)大量實(shí)驗(yàn)表明HDABC具有較強(qiáng)的搜索優(yōu)勢(shì)和較好的收斂性。因此本文選擇新型ICA和HDABC兩種算法作為對(duì)比算法。

3.3 實(shí)驗(yàn)結(jié)果與比較

根據(jù)算例信息表對(duì)JNQeIrsz3FblXXC19qX14w==每組算例獨(dú)立運(yùn)行20次取平均值，實(shí)驗(yàn)結(jié)果如表3所示。根據(jù)不同規(guī)模問(wèn)題的實(shí)驗(yàn)結(jié)果繪制出IGD和SP箱線圖，如圖11、12所示。表4是運(yùn)行每個(gè)算例得出的非支配解集按照文獻(xiàn)［18］的層次分析法（analytic hierarchy process，AHP）決策出最優(yōu)解，最后多次運(yùn)行每個(gè)算例取平均值。其中目標(biāo)函數(shù)F1單位為元，F(xiàn)2單位為s，F(xiàn)3單位為次，根據(jù)實(shí)際工況對(duì)目標(biāo)函數(shù)F2、F3進(jìn)行四舍五入取整。

通過(guò)不同規(guī)模的仿真實(shí)驗(yàn)結(jié)果得出以下結(jié)論：首先，對(duì)于小規(guī)模算例中的4個(gè)算例，除算例4中HDABC的非支配解個(gè)數(shù)比EICA的多外，EICA得出的Pareto非支配解個(gè)數(shù)比其他兩種對(duì)比算法都多，說(shuō)明EICA在解決小規(guī)模分布式不相關(guān)并行機(jī)車間調(diào)度問(wèn)題時(shí)能搜索到更多的前沿解，可以提供更多的調(diào)度方案。EICA的IGD平均值為12.86，均低于其他兩種算法的IGD平均值，說(shuō)明在解決小規(guī)模分布式不相關(guān)并行機(jī)車間調(diào)度多目標(biāo)問(wèn)題時(shí)EICA的收斂性較好。但EICA的SP平均值為42.57，相比兩種算法的SP平均值較大，說(shuō)明EICA在解決小規(guī)模問(wèn)題時(shí)解的分布均衡性較差。其次，在解決中規(guī)模的4個(gè)算例時(shí)，除算例6外EICA得出的非支配解個(gè)數(shù)都比新型ICA的多，說(shuō)明EICA在解決中規(guī)模問(wèn)題時(shí)與新型ICA相比，可以搜索到更多前沿解，但與HDABC相比有所不足。EICA的IGD平均值為5.75，比其他兩種算法都低，由此可知，在解決中規(guī)模分布式不相關(guān)并行機(jī)車間調(diào)度多目標(biāo)問(wèn)題時(shí)EICA的收斂性較好，但EICA的SP平均值為35.11，說(shuō)明在解決中規(guī)模問(wèn)題時(shí)相比其他兩種算法解的分布均衡性有所不足；最后，在大規(guī)模算例中，EICA得出的Pareto非支配解的個(gè)數(shù)NS都比其他兩種算法多，EICA的IGD平均值為17.51、SP平均值為18.96，都低于其他兩種算法的平均值，說(shuō)明EICA在解決大規(guī)模問(wèn)題時(shí)在解的個(gè)數(shù)、綜合性能和解的均衡性方面都具有一定的優(yōu)勢(shì)。

根據(jù)表4可知，與新型ICA相比，除算例7、8、11三個(gè)算例的優(yōu)化結(jié)果呈互不支配外，EICA在其他算例上的優(yōu)化結(jié)果完全支配其優(yōu)化結(jié)果。由此可知，EICA在解決分布式不相關(guān)并行機(jī)車間調(diào)度的多目標(biāo)問(wèn)題時(shí)優(yōu)于新型ICA。與HDABC相比，EICA在算例4、6、8三個(gè)算例的優(yōu)化結(jié)果與HDABC所求結(jié)果互不支配，在其余算例的優(yōu)化結(jié)果均優(yōu)于HDABC的優(yōu)化結(jié)果。

由于上述優(yōu)化結(jié)果有較多的互不支配狀態(tài)，無(wú)法直觀反映算法的好壞，結(jié)合圖11、12和表3、4，從整體上直觀分析所提算法的有效性和優(yōu)越性。

從整體上分析可以得出以下結(jié)論：首先，從Pareto非支配解的個(gè)數(shù)NS角度分析，EICA非支配解的個(gè)數(shù)相較于新型ICA提升9%，相較于HDABC基本持平，說(shuō)明EICA可以得到較多的非支配解。在此基礎(chǔ)上根據(jù)表4可以看出，58%的算例得出的最優(yōu)解中三個(gè)目標(biāo)函數(shù)值相較其他兩種算法得出的值更低，說(shuō)明更加接近真實(shí)的Pareto非支配解。因此，EICA不僅在非支配解的個(gè)數(shù)上表現(xiàn)出其優(yōu)越性，而且得出最優(yōu)解的質(zhì)量也高于其他兩種算法。其次，依據(jù)表3和圖11可以得出EICA的IGD平均值相比其他兩種算法平均低了64%。因此，EICA相比新型ICA和HDABC有著更好的收斂性。最后，依據(jù)表3和圖12可以得出EICA的SP均值相比新型ICA高了32%，相比HDABC的SP值高了0.9%，說(shuō)明EICA在解決中小規(guī)模問(wèn)題時(shí)，解的分布均衡性方面相對(duì)不足。綜合分析以上幾個(gè)因素可以得出EICA解集的質(zhì)量較優(yōu)且算法收斂性較好。

綜上所述，EICA在求解分布式不相關(guān)并行機(jī)車間調(diào)度多目標(biāo)問(wèn)題時(shí)，得到解的個(gè)數(shù)較多、算法收斂性較好，特別在求解較大規(guī)模問(wèn)題時(shí)表現(xiàn)出較好的綜合性能，能夠保證最優(yōu)解的個(gè)數(shù)和解的質(zhì)量，為分布式不相關(guān)并行機(jī)車間調(diào)度提供更多的調(diào)度方案以供選擇。

下面給出算例12的調(diào)度甘特圖，如圖13所示。

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

針對(duì)分布式不相關(guān)并行機(jī)車間調(diào)度的多目標(biāo)問(wèn)題，提出一種擴(kuò)展帝國(guó)競(jìng)爭(zhēng)算法。該算法在傳統(tǒng)帝國(guó)競(jìng)爭(zhēng)算法的基礎(chǔ)上增加適用于工廠分配的初始化工廠-工件序列群；并生成適用于并行機(jī)分配的并行機(jī)-工件序列群；將選出的較劣并行機(jī)-工件序列同化分為與選出的較優(yōu)序列進(jìn)行外部同化和較劣序列自身進(jìn)行內(nèi)部同化兩種；最后工廠-工件序列新采用部分匹配交叉和單點(diǎn)變異進(jìn)行更新。以總運(yùn)輸成本、工廠間并行機(jī)齊停評(píng)價(jià)函數(shù)和工件種類平均切換次數(shù)均衡評(píng)價(jià)函數(shù)為優(yōu)化目標(biāo)，設(shè)計(jì)不同規(guī)模的算例對(duì)算法性能進(jìn)行測(cè)試，驗(yàn)證了所提算法的有效性，并與新型ICA、HDABC進(jìn)行對(duì)比，擴(kuò)展帝國(guó)競(jìng)爭(zhēng)算法在Pareto非支配解的搜尋能力上具有一定的優(yōu)勢(shì)。

分布式車間調(diào)度是目前車間優(yōu)化調(diào)度研究的焦點(diǎn)，在實(shí)際分布式不相關(guān)并行機(jī)車間調(diào)度問(wèn)題中，約束條件更加復(fù)雜，工件多以批量生產(chǎn)的方式進(jìn)行加工。因此，在未來(lái)的研究中，將對(duì)擴(kuò)展帝國(guó)競(jìng)爭(zhēng)算法作進(jìn)一步的改進(jìn)，并使用擴(kuò)展帝國(guó)競(jìng)爭(zhēng)算法求解以總運(yùn)輸成本、工廠間并行機(jī)齊停評(píng)價(jià)函數(shù)及工廠間工件種類平均切換次數(shù)均衡為優(yōu)化目標(biāo)的分布式不相關(guān)并行機(jī)車間分批調(diào)度問(wèn)題。

參考文獻(xiàn)：

［1］Marandi F，Ghomi F S.Network configuration multi-factory scheduling with batch delivery：a learning-oriented simulated annealing approach［J］.Computers & Industrial Engineering，2019，132：239-310.

［2］王思涵，李新宇，高亮，等.分布式車間調(diào)度研究綜述［J］.華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2022，50（6）：1-10.（Wang Sihan，Li Xinyu，Gao Liang，et al.A review of distributed workshop scheduling research［J］.Journal of Huazhong University of Science and Technology：Natural Science Edition，2022，50（6）：1-10.）

［3］Maryam E，Parviz D，Mohamad S，et al.A new approach based on the learning effect for sequence-dependent parallel machine scheduling problem under uncertainty［J］.Discrete Dynamics in Nature and Society，2022，2022：article ID 2648936.

［4］Mecler D，Abu-Marrul V，Martinelli R，et al.Iterated greedy algorithms for a complex parallel machine scheduling problem［J］.European Journal of Operational Research，2022，300（2）：545-560.

［5］Behnamian J，Asgari H.A hyper-heuristic for distributed parallel machine scheduling with machine-dependent processing and sequence-dependent setup times［J］.RAIRO-Operations Research，2022，56（6）：4129-4143.

［6］Behnamian J，Ghomi F S.Multi-objective multi-factory scheduling［J］.RAIRO-Operations Research，2021，55：1447-1467.

［7］Ikhlasul A，Budi S.Solving multi-objective modified distributed parallel machine and assembly scheduling problem（MDPMASP）with eligibility constraints using metaheuristics［J］.Production Manufacturing Research，2022，10（1）：198-225.

［8］Herbert M.Simultaneous lotsizing and scheduling on parallel machines［J］.European Journal of Operational Research，2002，139（2）：277-292.

［9］葉飛，李梓晴，賴?yán)铈戮?分布式車間生產(chǎn)維修聯(lián)合調(diào)度仿真優(yōu)化方法［J］.系統(tǒng)仿真學(xué)報(bào)，2022，34（4）：688-699.（Ye Fei，Li Ziqing，Lai Liyuanjun.Optimization method for distributed workshop production and maintenance joint scheduling simulation［J］.Journal of System Simulation，2022，34（4）：688-699.）

［10］唐紅濤，沈毅，張偉，等.改進(jìn)鯨魚算法求解分布式裝配柔性作業(yè)車間生產(chǎn)與配送聯(lián)合調(diào)度問(wèn)題［J］.計(jì)算機(jī)應(yīng)用研究，2023，40（7）：1982-1990.（Tang Hongtao，Shen Yi，Zhang Wei，et al.Improved whale algorithm for solving the joint scheduling problem of production and distribution in distributed flexible assembly workshops［J］.Application Research of Computers，2023，40（7）：1982-1990.）

［11］Zheng Youlian，Yuan Yue，Zheng Qiaoxian，et al.A hybrid imperialist competitive algorithm for the distributed unrelated parallel machines scheduling problem［J］.Symmetry，2022，14（2）：204.

［12］陳雅玲，雷德明.求解分布式兩階段裝配流水車間調(diào)度的帝國(guó)競(jìng)爭(zhēng)-協(xié)作算法［J］.控制理論與應(yīng)用，2021，38（12）：1957-1967.（Chen Yaling，Lei Deming.Empire competition collaboration algorithm for solving distributed two stage assembly flow shop scheduling［J］.Control Theory and Applications，2021，38（12）：1957-1967.）

［13］Lei Deming，Yuan Yue，Cai Jingcao，et al.An imperialist competitive algorithm with memory for distributed unrelated parallel machines scheduling［J］.International Journal of Production Research，2020，58（2）：597-614.

［14］張清勇，王皓冉，雷德明.求解分布式并行機(jī)調(diào)度的新型帝國(guó)競(jìng)爭(zhēng)算法［J］.華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2019，47（8）：86-91.（Zhang Qingyong，Wang Haoran，Lei Deming.A novel imperial competition algorithm for solving distributed parallel machine scheduling［J］.Journal of Huazhong University of Science and Technology：Natural Science Edition，2019，47（8）：86-91.）

［15］Babak R，Gadelha F G，Rasul E，et al.Combining genetic local search into a multi-population imperialist competitive algorithm for the capaci-tated vehicle routing problem［J］.Applied Soft Computing，2023，142：110309.

［16］徐偉華，張根瑞，魏傳祥，等.基于自適應(yīng)繼承策略的帝國(guó)競(jìng)爭(zhēng)算法求解旅行商問(wèn)題［J］.計(jì)算機(jī)應(yīng)用研究，2021，38（11）：3349-3353.（X1ARblVoPHx+zJghmE8uwmg==u Weihua，Zhang Genrui，Wei Chuanxiang，et al.Empire competition algorithm based on adaptive inheritance strategy for solving traveling salesman problem［J］.Application Research of Computers，2021，38（11）：3349-3353.）

［17］Charadi S，Chakir E H，Redouane A，et al.A novel hybrid imperialist competitive algorithm-particle swarm optimization metaheuristic optimization algorithm for cost-effective energy management in Multi-Source residential microgrids［J］.Energies，2023，16（19）：6896.

［18］徐宜剛，陳勇，王宸，等.改進(jìn)NSGA-Ⅲ求解高維多目標(biāo)綠色柔性作業(yè)車間調(diào)度問(wèn)題［J/OL］.系統(tǒng)仿真學(xué)報(bào).（2023-09-18）.https：//kns.cnki.net/kcms/detail/11.3092.V.20230915.1327.007.html.（Xu Yigang，Chen Yong，Wang Chen，et al.Improving NSGA-Ⅲ for high-dimensional multi-objective green flexible job shop scheduling problem［J/OL］.Journal of System Simulation.（2023-09-18）.https：//kns.cnki.net/kcms/detail/11.3092.V.20230915.1327.007.html.）

［19］荀洪凱，陶翼飛，張?jiān)?，?多目標(biāo)啟發(fā)式狼群算法求解不相關(guān)并行機(jī)分批調(diào)度問(wèn)題［J］.信息與控制，2023，52（1）：93-103.（Xun Hongkai，Tao Yifei，Zhang Yuan，et al.Multi objective heuristic wolf swarm algorithm for solving batch scheduling problems on unrelated parallel machines［J］.Information and Control，2023，52（1）：93-103.）

［20］軒華，李文婷，李冰.混合離散人工蜂群算法求解含不相關(guān)并行機(jī)的分布式柔性流水線調(diào)度［J］.控制與決策，2023，38（3）：779-789.（Xuan Hua，Li Wenting，Li Bing.Hybrid discrete artificial bee colony algorithm for distributed flexible pipeline scheduling with unrelated parallel machines［J］.Control and Decision Making，2023，38（3）：779-789.）

收稿日期：2023-12-20

修回日期：2024-02-29

基金項(xiàng)目：云南省重點(diǎn)研發(fā)計(jì)劃（工業(yè)領(lǐng)域）資助項(xiàng)目（2018BA086）

作者簡(jiǎn)介：李立山（1994—），男，甘肅會(huì)寧人，碩士研究生，主要研究方向?yàn)閺?fù)雜生產(chǎn)系統(tǒng)建模與優(yōu)化調(diào)度；陶翼飛（1983—），男（通信作者），陜西西安人，講師，碩導(dǎo)，博士，主要研究方向?yàn)閺?fù)雜系統(tǒng)建模、調(diào)度與智能算法等（676379098@qq.com）；何毅（1976—），男，云南個(gè)舊人，工程師，主要研究方向?yàn)槠髽I(yè)信息化建設(shè)；周國(guó)誠(chéng)（1997—），男，山東安丘人，碩士研究生，主要研究方向?yàn)槲锪飨到y(tǒng)仿真建模與優(yōu)化調(diào)度；王鏡捷（1998—），男，云南昆明人，碩士研究生，主要研究方向?yàn)閺?fù)雜生產(chǎn)系統(tǒng)建模與優(yōu)化調(diào)度.