基于離散人工蜂群算法的分布式裝配置換流水車間調度問題

摘 ?要：文章針對分布式裝配置換流水車間調度問題，提出一種離散人工蜂群算法，以最小化最大完工時間。首先，提出一種基于隨機產品與工件順序的初始解生成方法。然后，設計一種基于關鍵路徑的種群個體領域搜索策略，并結合錦標賽選擇與新型精英保留策略，以達到加速種群收斂的目的。最后，通過變換陷入局部陷阱的種群個體，實現挖掘與探索能力的平衡。研究中基于1 710個算例，進行了大量的計算實驗，計算結果驗證了所提算法的優越性。

關鍵詞：流水車間;調度;人工蜂群算法;最大完工時間

中圖分類號：TP301.1 ? ? ?文獻標識碼：A文章編號：2096-4706（2021）24-0124-06

Abstract： For the distributed assembly permutation flow shop scheduling problem， a discrete artificial bee colony algorithm is proposed to minimize the makespan. Firstly， an initial solution generation method based on random product order and workpiece order is proposed. Secondly， an population individual neighborhood search strategy based on the critical path is designed， and tournament selection and novel elite retention strategy are employed to accelerate population convergence. Finally， the balance of exploitation and exploration capability is achieved by transforming the population individuals caught in local traps. A large number of computational experiments based on 1710 instances are carried out. The results verify the superiority of the proposed algorithm.

Keywords： flow shop; scheduling; artificial bee colony algorithm; makespan

0 ?引 ?言

裝配置換流水車間調度問題（Assembly Permutation Flow Shop Scheduling Problem， APFSSP）廣泛存在于消防車生產[1]、電腦裝配[2]、電路板生產[3]和塑料生產[4]等制造系統，以及分布式數據系統[5]、多頁發票打印系統[6]等服務系統中。APFSSP假定只有一個生產中心或工廠，所有工序都在同一個工廠完成。然而，市場競爭的加劇迫使很多企業選擇采用具有多個生產中心的分布式生產模式[7]。分布式生產能夠讓企業獲得產品質量很高、生產成本較低、管理風險較小的競爭優勢[8]。因此，分布式APFSSP即分布式裝配置換流水車間調度問題（Distributed Assembly Permutation Flow Shop Scheduling Problem， DAPFSSP）受到眾多學者與企業的廣泛關注。

2013年，Hatami等[9]首次提出了以最小化最大完工時間為目標的DAPFSSP。2016年，Lin和Zhang[10]提出了嵌入多種新穎啟發式的混合生物地理學優化算法;Wang等[11]提出了基于分布矩估計的文化基因算法。2017年，Lin等[12]提出了回溯搜索超啟發式方法。2019年，Pan等[13]提出了多種有效的啟發式算法;Ferone等[14]提出了一種偏隨機迭代局部搜索元啟發式算法。2020年，Zhang等[15]提出了融合改進社會蛛網優化和元-拉馬克學習與單純性搜索的文化基因算法。2021年，Zhang等[16]提出了一種基于矩陣—立方的分布矩估計算法。此外，2015年，Hatami等[17]提出了具有序列相關準備時間的DAPFSSP。2021年，Song等[18]提出了采用遺傳編程超啟發式算法求解該問題。2017年，Gonzalez-Neira等[19]提出了加工時間具有隨機性的DAPFSSP。2018年，Zhang等[20]提出了具有柔性裝配車間與準備時間的DAPFSSP。2018年，Sang等[21]提出了采用離散入侵雜草算法求解該問題。這些研究的重點集中于提出高效的算法來求解DAPFSSP。高效的調度算法能夠顯著提升生產過程的效率，因此，設計高效的調度算法具有重要意義[22]。

DAPFSSP是一種比APFSSP更復雜的NP難問題[9]，很難用精確算法來求解。人工蜂群算法[23]（Artificial Bee Colony， ABC）是一種基于種群的進化元啟發式算法。該算法模擬了蜜蜂在自然界中的智能覓食行為，由雇傭蜂、跟隨蜂、偵察蜂三個角色組成。雇傭蜂負責搜尋可行解和近鄰解;跟隨蜂通過與雇傭蜂交換信息獲得新的可行解，然后通過適應度值決定是否接受新的解，加快搜索收斂速度;如果可行解在迭代次數限制內沒有更新，雇傭蜂將會變成偵察蜂，搜尋新的可行解。由于本身具有高效的搜索性能，離散型ABC即離散人工蜂群算法（Discrete Artificial Bee Colony， DABC）經常用于求解諸多生產調度問題。

首先，提出一種結構化啟發式方法，以生成具有較高質量的初始種群。其次，提出一種基于關鍵路徑的種群個體領域搜索策略，以提高個體的局部搜索能力;最后，通過變換陷入局部陷阱的種群個體，提升種群個體的全局搜索能力，以實現種群在進化過程中挖掘與探索能力的平衡。通過大量的計算實例，驗證了DABC求解DAPFSSP的有效性和優越性。

1 ?分布式裝配置換流水車間調度問題

DAPFSSP包括生產和裝配兩個階段。在生產階段，n個工件{J1，J2，…，Jn}分配給F個工廠，每個工件只能分配給一個工廠。每個工廠有m臺機器{M1，M2，…，MM}。任一工件Ji的m道工序{Mi，1，Mi，2，…，Mi，m}依次在任一工廠的m臺機器上加工，加工時間用ti，j表示。每臺機器同一時刻只允許加工一個工件，每個工件同一時刻只允許在一臺機器上加工。在裝配階段，生產階段完工的工件在裝配機器MA組最終裝成H個產品{P1，P2，…，PH}。產品Ph由Nh個工件組裝而成，裝配時間用th表示。每個工件只屬于一個產品，任一產品只有在全部所需工件在生產階段加工完成后才能開始組裝，裝配機器一次只能裝配一個產品。

2 ?DABC算法求解DAPFSSP

2.1 ?編碼與解碼

DAPFSSP包含決定工件的工廠分配、各工廠的工件加工順序、產品的裝配順序三個子問題。工廠的工件加工順序可以唯一確定工件分配和產品的裝配順序。因此，采用基于工廠的工件加工順序編碼表示調度解。各加工廠按照所確定的工件順序進行加工，各產品所有部件實行先加工完成先裝配解碼，可以唯一確定整個調度方案。

以文獻[9]中的算例I_16_2_2_2_3為例，產品P1由工件{2，4，5，6，7，8，9，10，14，16}構成，產品P2由工件{1，3，11，12，13，15}構成。圖1為該算例的一個調度方案所對應的甘特圖，調度解為{[1，13，11，5，4，14，16，2，8]，[12，15，3，7，6，9，10]}，即工廠1的工件加工順序為[1，13，11，5，4，14，16，2，8]，工廠2的工件加工順序為[12，15，3，7，6，9，10]。

2.2 ?種群初始化

初始種群雖然可以通過隨機化方法產生，但是通過啟發式方法可能會獲得更好的搜索性能。在生產階段，屬于同一產品的工件在各工廠的加工時間盡可能接近，可以減少裝配階段的等待時間[11]。因此，以各產品所屬部件為一個整體在各工廠進行分配，可以保證所生成的整個種群具有較高質量。初始解或個體的生成過程為：

Step1：從當前產品集中隨機選出一個產品。

Step2：從所選產品隸屬的工件集中隨機選出一個工件分配給其中一個工廠，使此工廠在原有的基礎上生產該工件所需的完工時間最短。

Step3：從剩余的工件集中隨機選擇一個工件進行分配，直至分配完畢，進入下一步。

Step4：從剩余的產品集中隨機選出一個產品。如果產品分配完畢，則生產過程結束;否則，返回執行Step2。

反復執行初始解生成過程，就可以得到一個初始種群。

2.3 ?雇傭蜂階段

在雇傭蜂階段，雇傭蜂或種群個體在它的領域內搜索新的可行解。雇傭蜂的搜索效率決定了整個算法的搜索性能。在調度問題中，調度方案的關鍵路徑決定了整個調度方案的最大完工時間。只要關鍵路徑上的工序不變，整個調度方案的最大完工時間就不會發生變化[24]。因此，設計一種基于關鍵路徑的領域搜索策略。關鍵路徑上工序的所屬工件稱作關鍵工件，所有關鍵工件構成的集合稱作關鍵工件集。將與某工件的加工時間存在重合的工件稱作該工件的時間相關工件，某工件的所有時間相關工件稱作該工件的時間相關工件集。選擇某一關鍵工件作為交換工件，選擇該關鍵工件的時間相關工件作為被交換工件，執行位置交換，得到新的調度解。

領域搜索策略為：

Step1：確定調度解中的關鍵工件集。

Step2：從關鍵工件集中隨機選出一個工件作為交換工件。

Step3：確定交換工件的時間相關工件集。

Step4：從時間相關工件集中隨機選出一個工件作為被交換工件。

Step5：將交換工件與被交換工件互換位置，得到新的調度解。

Step6：如果新的調度解的最大完工時間小于原來的最大完工時間，則新的調度解代替原來的調度解，結束搜索;否則，從剩余的時間相關工件集中隨機選出一個工件作為被交換工件，如果原來的調度解的時間相關工件集為空集，結束搜索;否則，返回執行step3。

由圖1可知，該調度方案的關鍵工件集為{1，13，11，5，4，14，16，2，8}，工件2的時間相關工件集為{16，6，9，10，8}。交換工件9和2可得到新的調度解{[1，13，11，5，4，14，16，2，8]，[12，15，3，7，6，9，10]}。

2.4 ?跟隨蜂階段

在跟隨蜂階段，錦標賽選擇可以改善算法的效率，同時還可以避免陷入局部最優解。從種群中隨機選擇λ個個體，比較個體適應度值。選擇適應度最小的一個個體，執行領域搜索策略，得到一個調度解。執行錦標賽選擇φ次，得到φ個個體。再與原種群的所有個體進行比較，選擇最大完工時間最小的ρ個個體組成新的種群。種群進化速度的決定因素是最壞的個體，而不是最好的個體，而這種基于貪婪的種群更新方法可以有效保證種群的全局質量。

2.5 ?偵察蜂階段

在偵察蜂階段，如果某個體的最大完工時間在累計執行η次領域搜索策略后沒有減小，則舍棄該個體，按照初始解生成過程生成一個新的調度解，代替原來的解，成為新的種群個體。這種個體替換方式實現種群個體在全域范圍的搜索能力。

2.6 ?算法描述

DABC求解DAPFSSP的具體過程為：

Step1：按照初始解的產生過程，生成具有ρ個個體的初始種群。

Step2：讓種群中的每個個體執行一次領域搜索策略，生成一個新的種群。

Step3：應用錦標賽選擇挑選φ個個體，各執行一次領域搜索策略，生成φ個個體。與原種群中的ρ個個體做比較，選擇最大完工時間較短的前ρ個個體，構成一個新的種群。

Step4：如果個體的最大完工時間在累計執行η次領域搜索策略后未得到優化，則舍棄掉該解，按照初始解產生過程生成一個新解來代替該解。

Step5：如果滿足終止條件，求解結束，輸出最優調度;否則，返回執行Step2。

3 ?實驗結果與分析

為了驗證DABC算法求解DAPFSSP的有效性，對文獻[9]中的兩組基準算例進行仿真計算。兩組基準算例由不同的工件數量、機器數量、工廠數量和產品數量構成。第一組算例包含900個小尺度算例，工件數量n={8，12，16，20，24}，機器數量m={2，3，4，5}，工廠數量F={2，3，4}，產品數量H={2，3，4};第二組算例包含810個大算例，工件數量n={100，200，500}，機器數量m={2，3，4，5}，工廠數量F={4，6，8}，產品數量H={30，40，50}。為了比較各種算法的有效性和效率，實驗結果通常采用平均相對百分比偏差（ARPD）作為比較指標[25]，計算過程為：

其中，Cbest表示每個算例的已知最優解，Ci表示每個實例在第次試驗中所獲得的最優結果，R表示執行計算的次數。ARPD越小表示算法的性能越好，ARPD的值小于零表示最優解得到了優化。

3.1 ?參數設置

所選參數的合適與否對啟發式算法求解的質量、計算效率等性能具有重要影響。因此，采用田口試驗方法確定影響DABC求解DAPFSSP的四個關鍵參數，包括種群個體數量ρ、參與錦標賽選擇的種群個體數量φ、種群個體最大允許領域搜索次數η、最大迭代次數κ。每個參數選擇4個不同的水平，參數值組合如表1所示。

參數正交陣列L16（44）的選擇基于參數的數量和因子水平。選擇實例I_24_5_3_2_2進行仿真試驗。每個參數組合獨立運行20次，計算平均最大完工時間（AM）。φ=ρ×10%，參數正交陣列和AM計算結果如表2所示。計算各參數的平均AM值，并對各因素的因子水平進行顯著性檢驗。各參數的平均AM值和顯著性水平如表3所示，各參數不同取值下AM值的變化趨勢如圖2所示。

由圖2和表3可知，種群個體數量ρ是4個影響因素中影響最明顯的，選擇較大的ρ可以得到更優的AM值。然而，選擇較大的ρ意味著需要更大的計算成本（即更多的計算時間）。在最大迭代次數κ達到200次時，AM值存在逐漸減少的變化趨勢。λ和η在選擇較小的因子水平時可以得到更小的AM值。因此，選擇ρ=100、λ=5、η=2、κ=100作為DABC的參數值。

3.2 ?計算結果與分析

基于兩組算例，對比已知的12種啟發式算法，分析DABC求解DAPDSSP的性能。針對每個算例，獨立運行5次，計算平均ARPD值。對于900個小尺度算例，其計算結果按照工廠數量F與工件數量n的組合分組，每組F×n表示60個算例的ARPD平均值。12種參與對比的啟發式算法的計算結果直接取自文獻[9]。如表4所示，DABC在所有算法結果里取得了最優的結果。在15組算例分組中，有8組的平均ARPD值小于0。計算結果顯示，87個小尺度算例取得了更小的最大完工時間。

對于810個大尺度算例，計算結果分別按照工廠數量F、產品數量H、工件數量n進行分組，每組表示270個大尺度算例的ARPD平均值。12種參與對比的啟發式算法的計算結果直接取自文獻[9]。如表5所示，DABC在所有算法中取得了最好的計算結果。在9組算例分組中，所有分組的平均ARPD值小于0。計算結果顯示，114個小尺度算例取得了更小的最大完工時間。

4 ?結 ?論

本文針對以最大完工時間最小化為目標的分布式裝配置換流水車間調度問題，提出了一種離散人工蜂群算法。通過大量調度問題標準算例進行實驗研究，結果表明該算法具有較好的搜索性能和效果。本文只討論了單目標分布式裝配調度問題，未來將進一步探索使用人工蜂群算法解決更加復雜的多目標或多約束的分布式裝配調度問題。

參考文獻：

[1] LEE C Y，CHENG T C E，LIN B M T. Minimizing the Makespan in the 3-Machine Assembly-Type Flowshop Scheduling Problem [J].Management Science，1993，39（5）：616-625.

[2] POTTS C N，SEVASTJANOV S V，STRUSEVICH V A，et al. The Two-Stage Assembly Scheduling Problem：Complexity and Approximation [J].Operations Research，1995，43（2）：346-355.

[3] CHENG T C E，WANG G. Scheduling the fabrication and assembly of components in a two-machine flowshop [J].IIE Transactions，1999，31（2）：135-143.

[4] ALI A，HARUN A. The two stage assembly flowshop scheduling problem to minimize total tardiness [J].Journal of Intelligent Manufacturing，2015，26（2）：225-237.

[5] ALI A，AL-ANZI F S. The two-stage assembly scheduling problem to minimize total completion time with setup times [J].Computers and Operations Research，2009，36（10）：2740-2747.

[6] ZANG Y，ZHOU Z L，LIU J Y. The production scheduling problem in a multi-page invoice printing system [J].Computers and Operations Research，2010，37（10）：1814-1821.

[7] BEHNAMIAN J，GHOMI S M T F. A survey of multi-factory scheduling [J].Journal of Intelligent Manufacturing，2016，27（1）：231-249.

[8] NADERI B，RUIZ R. The distributed permutation flowshop scheduling problem [J].Computers and Operations Research，2010，37（4）：754-768.

[9] HATAMIS，Ruiz R，ANDRES-ROMANO C. The Distributed Assembly Permutation Flowshop Scheduling Problem [J].International Journal of Production Research，2013，51（17）：5292-5308.

[10] LIN J，ZHANG S. An effective hybrid biogeography-based optimization algorithm for the distributed assembly permutation flow-shop scheduling problem [J].Computers & Industrial Engineering，2016，97：128-136.

[11] WANG S Y，WANG L. An Estimation of Distribution Algorithm-Based Memetic Algorithm for the Distributed Assembly Permutation Flow-Shop Scheduling Problem [J].IEEE Transactions on Systems， Man， and Cybernetics： Systems，2016，46（1）：139-149.

[12] LIN J，WANG Z J，LI X. A backtracking search hyper-heuristic for the distributed assembly flow-shop scheduling problem [J]. Swarm and Evolutionary Computation，2017，36：124-135.

[13] PAN Q K，GAO L，LI X Y，et al. Effective constructive heuristics and meta-heuristics for the distributed assembly permutation flowshop scheduling problem [J].Applied Soft Computing，2019，81：105492.

[14] FERONE D，HATAMI S，GONZ?LEZ‐NEIRA EM，et al. A biased‐randomized iterated local search for the distributed assembly permutation flow‐shop problem [J]. International Transactions in Operational Research，2020，27（3）：1368-1391.

[15] ZHANG G H，XING K Y，Zhang G Y，et al. Memetic algorithm with meta-Lamarckian learning and simplex search for distributed flexible assembly permutation flowshop scheduling problem [J].IEEE Access，2020，8：96115-96128.

[16] ZHANG Z Q，QIAN B，HU R，et al. A matrix-cube-based estimation of distribution algorithm for the distributed assembly permutation flow-shop scheduling problem [J].Swarm and Evolutionary Computation，2021，60：100785.

[17] HATAMI S，RUIZ R，ANDRES-ROMANO C. Heuristics and metaheuristics for the distributed assembly permutation flowshop scheduling problem with sequence dependent setup times [J].International Journal of Production Economics，2015，169：76-88.

[18] SONG H B，LIN J . A genetic programming hyper-heuristic for the distributed assembly permutation flow-shop scheduling problem with sequence dependent setup times [J].Swarm and Evolutionary Computation，2021，60：100807.

[19] GONZALEZ-NEIRA E M，FERONE D，HATAMI S，et al. A biased-randomized simheuristic for the distributed assembly permutation flowshop problem with stochastic processing times [J].Simulation Modelling Practice and Theory，2017，79：23-36.

[20] ZHANG G H，XING K Y，CAO F. Scheduling distributed flowshops with flexible assembly and set-up time to minimize makespan [J].International Journal of Production Research，2018，56（9-10）：3226-3244.

[21] SANG H Y，PAN Q K，LI J Q，et al. Effective invasive weed optimization algorithms for distributed assembly permutation flowshop problem with total flowtime criterion [J]. Swarm and Evolutionary Computation，2019，44：64-73.

[22] LI D N，Li M，Meng X W，et al. A Hyperheuristic Approach for Intercell Scheduling With Single Processing Machines and Batch Processing Machines [J].IEEE Transactions on Systems， Man， and Cybernetics： Systems，2015，45（2）：315-325.

[23] OZTURK C，GORKEMLI B，KARABOGA D，et al. A comprehensive survey： artificial bee colony （ABC） algorithm and applications [J].Artificial Intelligence Review： An International Science and Engineering Journal，2014，42：21-57.

[24] LIU Z M. A bi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem [J].Computers & Industrial Engineering，2012，62（4）：917-926.

[25] RUIZ R，MAROTO C，ALCARAZ J. Two new robust genetic algorithms for the flowshop scheduling problem [J].Omega，2006，34（5）：461-476.

作者簡介：段秀山（1995—），男，漢族，重慶彭水人，碩士研究生在讀，研究方向：智能制造。