考慮預防性維護的分布式柔性作業車間調度問題研究

鄭景文 付亞平

摘 ?要：隨著全球制造業的快速發展，物流企業競爭加劇，生產制造缺乏有效協同，企業急需更加高效的生產運作模式。分布式制造可以將位于不同地點的原材料、機器設備、操作人員等資源進行有效地整合協同并充分利用。此外，設備維護是企業運營管理的核心內容，直接關系到企業的生產成本、質量與交貨期。基于以上背景，文章提出了考慮機器預防性維護的分布式柔性作業車間調度問題，建立了目標為最小化最大完工時間的數學模型，提出了協同進化算法對問題進行求解。通過與兩種經典的元啟發式算法進行對比實驗，結果表明所提出的算法能較好地求解所研究的問題。

關鍵詞：分布式柔性作業車間;預防性維護;協同進化算法

中圖分類號：F403.3文獻標志碼：ADOI：10.13714/j.cnki.1002-3100.2024.11.004

Abstract： With the rapid development of the global manufacturing industry， the competition of logistics enterprises has intensified， and the production and manufacturing lack of effective coordination， and enterprises are in urgent need of more efficient production and operation mode. Distributed manufacturing can effectively integrate and coordinate raw materials， machinery and equipment， operators and other resources located in different locations and make full use of them. In addition， equipment maintenance is the core content of enterprise operation management， which is directly related to the production cost， quality and delivery time of the enterprise. Based on the above background， this paper proposes a distributed flexible job shop scheduling problem considering machine preventive maintenance， establishes a mathematical model with the goal of minimizing the maximum completion time， and proposes a coevolutionary algorithm to solve the problem. Compared with two classical meta-heuristic algorithms， the results show that the proposed algorithm can solve the problem well.

Key words： distributed flexible job shop; preventive maintenance; cooperative evolutionary algorithm

0 ?引 ?言

隨著經濟全球化的發展，科技不斷進步，物流企業競爭也日益激烈，現代物流管理要想在競爭中脫穎而出，就必須把科技手段轉化為企業的生產力，其中，調度問題是急需解決的重要問題。由于市場中產品需求多變，需要企業具備快速響應市場的能力，眾多企業紛紛引進柔性制造系統，逐漸具備了柔性制造的能力[1]。基于此背景的分布式柔性作業車間調度問題（Distributed Flexible Job Shop Scheduling Problem， DFJSP）一經提出就成為了研究熱點。由于分布式柔性作業車間調度問題本身的復雜性，使得考慮其維護任務時更加困難。為了描述這個問題，本文建立了目標為最小化最大完成時間的數學模型，設計了一種協同進化算法對該模型進行求解。通過對一組測試算例進行仿真實驗，并與兩種流行的元啟發式算法進行比較，實驗結果驗證了所提方法的有效性。

1 ?相關研究

目前，分布式車間調度問題備受關注，理論研究的重心轉移到將算法與實際問題的結合上[2]。Jiang等[3]提出了考慮節能的分布式作業車間調度問題，通過改進帶有分解的多目標進化算法來解決這個問題。為了最小化分布式作業車間調度問題中的完工時間，Xie等[4]設計了人工蜂群算法。方瀟珞等[5]建立了設備隨機故障下的經濟生產批量模型，目的是求得使單位費用期望值最低的最優經濟生產批量和檢查次數。Ahmadi等[6]提出了進化算法來解決機器故障下的多目標柔性作業車間問題。Park等[7]提出了一種基于遺傳規劃的超啟發式方法來解決機器故障下的動態車間調度問題。Zandieh等[8]提出了改進的帝國主義競爭算法，用于基于條件的柔性作業車間調度問題的維護。

基于上述情況，本文以最小化最大完成時間為目標建立數學模型，針對考慮預防性維護的分布式柔性作業車間調度問題，設計了一種協同進化算法（Cooperative Evolutionary Algorithm， CEA），并與兩種經典算法進行比較，通過對一組測試算例進行仿真實驗，驗證了所提方法的有效性。

2 ?問題描述及數學模型

本文研究了考慮預防性維護的分布式柔性作業車間的單目標調度問題。該問題涉及三個調度決策：工件分配到工廠;工序分配到機器;工序的排序。同時，在實際的加工過程中，往往會出現由于機器故障導致加工中斷的情況，這會使加工完成時間、加工成本、加工能耗增加，導致企業的生產效率降低，進而影響企業的效益。因此，在生產調度的過程中提前考慮機器的維護任務，更加符合企業的實際需要。因此，本文以最小化最大完成時間為目標建立模型，在表1中定義了相關符號。

在該問題中，可行的調度必須滿足以下約束條件：（1）所有工件都在零時等待處理;（2）所有機器在零時可用;（3）每臺機器一次只能加工一道工序;（4）每道工序一次只能在一臺機器上進行加工;（5）禁止機器中斷;（6）如果一個工件被分配到一個工廠，那么這個工件的所有工序都在同一個工廠進行加工;（7）預防性維護操作可以在任何時間執行;（8）同一時刻在同一臺機器上工件的操作和預維護任務不能同時進行。基于上述描述，建立數學模型如下：

其中：式（1）表示目標是最小化最大完成時間;式（2）表示任意工廠中一臺機器上的操作排序;式（3）表示如果一個工件被分配到一個工廠，那么這個工件的所有操作都在同一個工廠進行加工;式（4）表示一個操作只能在一個工廠的一臺機器上進行加工;式（5）表示每個工件上各個操作的排序;式（6）表示在加工o之前進行維護任務;式（7）表示所有工件上的操作都要進行，且不能同時進行加工;式（8）表示必須在時間窗口內進行預維護任務;G表示一個極大數。

3 ?算法的設計與實現

協同進化算法（Cooperative Evolutionary Algorithm， CEA）的基本思想是將一個系統劃分為多個子系統，每個子系統獨立進化。通過整合子系統形成一個新的系統，以實現整體進化的目標[9]。本文將協同進化算法應用于種群和染色體。由于解的表示涉及三個問題，而這些問題是相互獨立的，因此，協同進化方法非常適合解決所研究的問題。

3.1 ?編碼與解碼。在所提出的方法中，使用三個向量來表示一個解。這三個向量分別是工廠分配向量FA、機器分配向量MA、工序序列向量OS。工廠分配向量的長度等于工件的數量。工序序列向量和機器分配向量具有相同的長度，并且等于所有工件的工序總數。同時，采用Wang等[10]設計的左移解碼方案，將解決方案轉解碼為一個可行的解。在本文中，使用以下啟發式方法動態調度維護任務[11]：在每臺機器的時間窗口開始時調度維護任務;在進行工件加工的總時間內進行維護;如果維護任務與工序o不重疊，則分別進行維護和調度操作的任務;維護任務與工序o有時間重疊時，若開始進行維護任務會中斷工序操作，則先完成該工序再進行維護任務，若工件的工序會中斷維護任務，則在調度工序之前進行維護。

3.2 ?初始化種群與種群劃分。種群的質量對種群智能算法的求解速度和求解能力有很大的影響。因此，本文采用幾種策略，通過所研究問題的特點來初始化種群。

對于操作序列向量，在初始種群中，使用兩個啟發式規則生成兩個個體的工序序列，即優先選擇余下加工時間最長[12]的工件和優先選擇余下工序數最多[12]的工件，其余的隨機生成。對于所有工廠分配向量，其中50%是隨機產生的，另外50%是通過以下啟發式規則生成的：首先，通過生成的工序序列向量獲得工件序列，迭代生成工序序列向量;其次，計算每個工件的平均工作量;然后，通過策略將每項工件連續地分配到特定的工廠;最后，根據獲得的工件順序，將每個工件依次分配給最先完成該作業的工廠。對于所有機器分配向量，有50%的部分是隨機生成的，其余50%是通過結合最小完成時間啟發式規則獲得的[12]。

根據編碼方法和問題的特點，將工廠分配、機器分配和工序序列三個子問題獨立進化，種群P可分為三個子種群，分別是工廠分配種群P，機器分配種群P，工序序列種群P。

3.3 ?交叉與變異。為了實現更高效的搜索，對子種群P采用了多重工序交叉[13]，其目的是通過使用工序序列來增加種群多樣性;對于子種群P，采用均勻交叉[1];對于子種群P，采用隨機概率交叉[14]。本文設計了四種變異算子，對于種群P，使用交換和插入方法;種群P使用隨機選擇方法，隨機選擇一個工件，并將其工廠更改為另一個工廠;種群P使用隨機選擇方法，隨機選擇一種工序，并將其機器更改為所選工廠中另一臺可用的機器。其中，交換方法即交換兩個隨機選擇的工序的位置;插入方法即隨機選擇一個工序并插入到其他位置。當每個子種群發生變異時，需要注意以下方面：所有種群的每個個體都需要進行變異;新個體直接取代父個體;各個種群的變異率相同。

3.4 ?局部搜索。在生產中，解決方案的加工時間取決于關鍵路徑的長度，在關鍵路徑保持不變的情況下，加工時間無法縮短。為了減少加工總時間，通過在執行本地搜索時打破關鍵路徑，來獲得更好的解。因此，設計三種打破關鍵路徑的方法，分別是工序位置變換方法、改變工件所屬工廠的方法和改變某一工序的加工機器的方法。此外，設計了一種迭代局部搜索方法[15]來優化最優個體。

3.5 ?更新種群的方法。為了保證下一段種群具有更高的質量，首先，將當前種群中的最優個體直接保留到下一代種群。其次，下一代種群的其他個體通過交叉、變異和局部搜索方法產生。

3.6 ?CEA的算法步驟

步驟1：初始化算法參數，即種群大小PS，變異率Pm;

步驟2：使用啟發式規則生成初始種群;

步驟3：評估初始種群并確定最佳個體;

步驟4：重復以下步驟，直到滿足給定的停止條件;

步驟4.1：交叉。對子種群P進行多重工序交叉;對子種群P進行均勻交叉;對子種群P進行隨機概率交叉;

步驟4.2：變異。從區間0，1中生成隨機數r，如果r小于p，繼續步驟4.1，否則，請轉步驟4.3;從區間0，1中獲取隨機小數r，如果r<0.5，則對子種群P執行交換方法，否則，對子種群P執行插入方法;對子種群P和子種群P執行隨機選擇方法;

步驟4.3：評估各個種群;

步驟4.4：局部搜索。通過迭代局部搜索方法，尋找找獲得新個體的最優解;

步驟4.5：更新種群;

步驟4.6：如果給定條件不滿足，返回步驟4.1，否則，執行步驟5;

步驟5：輸出最佳個體及其目標值。

算法流程圖如圖1所示。其中包括各種工廠分配規則、機器分配規則和工序順序規則;工廠分配向量、機器分配向量和工序序列向量協同優化;打破關鍵路徑，增強局部搜索能力。該算法通過多種搜索策略的協同使用，有望在考慮的問題上取得優異的性能。

4 ?算例分析

4.1 ?參數設置及比較算法。為了評估CEA在處理所提問題方面的性能，本文采用關于柔性作業車間的Hurink， Jurisch和thole基準[19]測試問題構建了一組測試實例。此外，選擇了兩種著名的智能優化算法，即混合遺傳算法（Hybrid Genetic Algorithm， HGA）[16]和混合教學優化算法（Hybrid Teaching-Learning-Based Optimization， HTLBO）[17]進行比較。為了公平比較，CEA的參數設置如下：種群規模為30，變異概率為0.20，局部搜索次數為12。HGA的參數設置如下：種群規模為30，變異概率為0.15。HTLBO的參數設置如下：種群規模為50，TS搜索次數為15，適應值評估次數為150n，n表示工件數，將適應值評估次數設置為算法停止準則。

4.2 ?評價指標。本文選用相對百分比偏差（Relative Percentage Difference， RPD）指標[18]CEA與其比較算法的結果進行比較，RPD指標的計算公式如下：

RPD= ?（9）

其中：θ為最佳目標函數值，θ為某算法在第v次復制時的目標函數值。在接下來的實驗中，計算20個重復的平均RPDaRPD、最優RPDbRPD和RPD的標準差sRPD，并對實驗結果進行分析。

4.3 ?結果分析。CEA及其對比算法對aRPD、bRPD和sRPD的實驗結果如表2所示。從表2中可以發現，幾乎在所有情況下，CEA都明顯優于HGA和HTLBO。通過比較CEA和HTLBO的sRPD值，我們可以看到HTLBO只有一組數據優于CEA，有一組數據表現相同。對于HGA而言，CEA在所有情況下都優于它。HGA、HTLBO和CEA的平均aRPD值分別為1.027 8、0.370 4和0.024 8，平均bRPD值分別為0.333 0、0.305 4和0.000 0，平均sRPD值分別為0.058 6、0.036 7和0.017 4。三種算法的平均aRPD值、平均bRPD值和平均sRPD值的比較結果也進一步證明了CEA比其比較算法具有更好的性能。

此外，還使用Friedman檢驗，Nemenyi后續檢驗和Wilcoxon符號秩檢驗比較了CEA與比較算法之間的差異[19]。

（1）通過對三種算法的實驗結果進行Friedman檢驗，可以得到p值為0.000 0，說明三種算法的實驗結果是有明顯差異的，結果如圖2所示。

（2）在Friedman檢驗結果的基礎上，進行了Nemenyi后續檢驗。可以發現CEA和HGA的秩平均值之差為1.75，此值大于臨界范圍值0.781 3，說明CEA的實驗結果是顯著優于HGA的實驗結果的。此外，CEA和HTLBO的秩平均值之差為1.166 6，此值也大于臨界范圍值0.781 3，同樣說明CEA的實驗結果是顯著優于HTLBO的實驗結果的。

（3）另外，對實驗結果進行了Wilcoxon符號秩檢驗。第一步，對于每個實例，計算兩種算法之間的差異。第二步，根據每個指標的差的絕對值對每個實例進行排序。第三步，通過秩值得到兩兩比較的“R”和“R”值。用“R”表示第一種算法優于第二種算法的秩和，用“R”表示第二種算法優于第一種算法的秩和。p值可以由“R”和“R”值確定。在實驗時，第一種算法是CEA，第二種算法是比較算法。兩兩比較的Wilcoxon符號秩檢驗結果如表3所示。符號“w”、“w”和“w”分別表示測試實例中的CEA優于、等于和低于其比較算法。

通過分析表3可以發現，與HGA算法相比，在aRPD、bRPD和sRPD的18個測試實例中，CEA在性能方面優于HGA。與HTLBO算法相比，CEA分別在17、17和16個測試實例上獲得了更好的結果。通過觀察“R”和“R”的值可以發現，對于aRPD、bRPD和sRPD，每次兩兩比較的“R”值都大于“R”值。此外，CEA與其他兩種比較算法兩兩比較的P值均為0.000 0。

5 ?總 ?結

分布式制造系統有助于降低運營成本和提高生產效率，因此它正在逐步取代單一工廠生產流程。為了充分利用分布式柔性作業車間的優勢，提高企業競爭優勢，分布式柔性作業車間調度方法被用于各個行業。在實際生產過程中，機器不可避免地會出現不可用期。這種情況將給企業帶來一定的生產成本和經濟損失。因此，基于以上現實需求，本文設計了一種協同進化算法來解決帶有預防性維護的分布式柔性作業車間調度問題，選擇兩種比較算法進行仿真實驗，實驗結果表明所提出的算法性能更好。本文從理論上設計了考慮問題特點的算法，針對預防性維護問題，豐富了分布式柔性作業車間調度問題的研究內容。幫助企業降低成本、提高生產效率，進一步促進企業效益的提高，有一定的實踐意義。從管理學角度分析，考慮預防性維護的分布式柔性作業車間調度問題能夠將生產出現的問題提前了解并做好防護，有效調動各個生產裝置，消除安全隱患，保證生產安全有序地運行。本文限制了一個工件只能在一個工廠進行加工，不同工廠之間不可轉移，然而在企業真實的制造系統中，可能由于環境污染等因素造成某些操作必須在某一工廠進行加工的情形。因此，未來研究可以考慮工件在工廠之間可以轉移的情況，建立新的考慮工件轉移的問題模型。

參考文獻：

[1] ?FU Y， WANG H， HUANG M. Integrated scheduling for a distributed manufacturing system： A stochastic multi-objective model[J]. Enterprise Information Systems， 2019，13（4）：557-573.

[2] 鄭睿. 制造業的車間調度問題優化算法比較研究[J]. 物流科技，2008（6）：117-119.

[3] ?JIANG E D， WANG L， PENG Z P. Solving energy-efficient distributed job shop scheduling via multi-objective evolutionary algorithm with decomposition[J]. Swarm and Evolutionary Computation， 2020，58：100745-100760.

[4] ?XIE J， GAO L， PAN Q， et al. An effective multi-objective artificial bee colony algorithm for energy efficient distributed job shop scheduling[J]. Procedia Manufacturing， 2019，39：1194-1203.

[5] 方瀟珞，呂文元. 設備隨機故障條件下的經濟生產批量模型[J]. 物流科技，2015，38（12）：78-83.

[6] ?AHMADI E， ZANDIEH M， FARROKH M， et al. A multi objective optimization approach for flexible job shop scheduling problem under random machine breakdown by evolutionary algorithms[J]. Computers & Operations Research， 2016，73：56-66.

[7] ?PARK J， MEI Y， NGUYEN S， et al. Investigating the generality of genetic programming based hyper-heuristic approach to dynamic job shop scheduling with machine breakdown[C] // Australasian Conference on Artificial Life and Computational Intelligence. Springer， Cham， 2017.

[8] ?ZANDIEH M， KHATAMI A R， RAHMATI S. Flexible job shop scheduling under condition-based maintenance： Improved version of imperialist competitive algorithm[J]. Applied Soft Computing， 2017，58：449-464.

[9] ?LEI D. Co-evolutionary genetic algorithm for fuzzy flexible job shop scheduling[J]. Applied Soft Computing Journal， 2012，12（8）：2237-2245.

[10] ?WANG L， ZHOU G， XU Y， et al. An effective artificial bee colony algorithm for the flexible job-shop scheduling problem[J]. International Journal of Advanced Manufacturing Technology， 2012，60（1-4）：303-315.

[11] ?JQLA B， QKPA B， MFT C. A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities[J]. Applied Mathematical Modelling， 2014，38（3）：1111-1132.

[12] ?KAI Z G， SUGANTHAN P N， TASGETIREN M F， et al. Effective ensembles of heuristics for scheduling flexible job shop problem with new job insertion[J]. Computers & Industrial Engineering， 2015，90：107-117.

[13] ?LU C， GAO L， GONG W， et al. Sustainable scheduling of distributed permutation flow-shop with non-identical factory using a knowledge-based multi-objective memetic optimization algorithm[J]. Swarm and Evolutionary Computation， 2021，60：100803.

[14] ?GONG G， CHIONG R， DENG Q， et al. A hybrid artificial bee colony algorithm for flexible job shop scheduling with worker flexibility[J]. International Journal of Production Research， 2019，58（14）：1-15.

[15] ?HOU Y， FU Y， GAO K， et al. Modelling and optimization of integrated distributed flow shop scheduling and distribution problems with time windows[J]. Expert Systems with Application， 2022，187：115827.

[16] ?CHENG R， GEN M， TSUJIMURA Y. A tutorial survey of job-shop scheduling problems using genetic algorithms： Part II. Hybrid genetic search strategies[J]. Computers & Industrial Engineering， 1999，37（1-2）：51-55.

[17] ?DING Y， ZHANG Q， LEI D. A novel hybrid teaching learning based optimization algorithm for function optimization[C]

// 2017 Chinese Automation Congress （CAC）. IEEE， 2017：4383-4388.

[18] ?HURINK J， JURISCH B， THOLE M. Tabu search for the job-shop scheduling problem with multi-purpose machines[J]. Operations-Research-Spektrum， 1994，15（4）：205-215.

[19] ?DERRAC J， GARC?A S， MOLINA D， et al. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms[J]. Swarm and Evolutionary Computation， 2011，1（1）：3-18.

收稿日期：2023-06-12

作者簡介：鄭景文（1996—），女，山西侯馬人，青島大學商學院碩士研究生，研究方向：工業工程與管理;付亞平（1985—），男，山東平度人，青島大學商學院，教授，博士，研究方向：復雜系統計劃與調度、多目標優化。

引文格式：鄭景文，付亞平. 考慮預防性維護的分布式柔性作業車間調度問題研究[J]. 物流科技，2024，47（11）：19-23.