考慮擾動的柔性作業(yè)車間多目標動態(tài)調度研究

王少參，唐 宇，翟書磊

（1.中國船舶集團有限公司第七一三研究所，鄭州 450015；2.南京理工大學 機械工程學院，南京210094）

生產調度是指對具體的生產任務進行決策安排，使得生產任務能夠在滿足工藝路線、加工設備等實際約束的情況下，達到優(yōu)化最大完工時間、能耗等生產指標的目標［1］。在數字經濟和信息技術的推動下，制造業(yè)的生產特征從單品種、大規(guī)模的剛性生產逐漸轉為多品種、小批量的柔性生產，生產模式的轉變讓生產過程更加復雜化，同時實際生產中隨機出現的擾動事件讓生產過程更加難以管控。因此如何有效解決柔性作業(yè)車間的生產調度問題（Flexible Job Shop Scheduling，FJSP）成為了學術界的研究熱點［2］。

在實際生產的作業(yè)車間中，由于產品制造過程繁雜冗長，生產現場的環(huán)境因素錯綜復雜，擾動事件是廣泛存在且無法完全消除或避免的。因此針對柔性作業(yè)車間的動態(tài)調度問題，國內外的專家學者進行了相關研究工作，并取得了一定成果。馮益銘［3］以電子產品復雜精密件為研究對象，對混合柔性作業(yè)車間與全自動柔性生產線中的動態(tài)調度問題進行了研究，提出了一種帶篩選機制的混合驅動方式，建立了包含尾插式調度等3種方法的組合重調度方法；朱旭東［4］以優(yōu)化最大完工時間為目標，設計了一種基于強制進化遺傳算法和記憶優(yōu)先加工通道的動態(tài)調度方法，有效解決了訂單加急擾動下的柔性車間動態(tài)調度問題；斯興瑤等［5］為解決柔性車間生產過程中生產效率與設備利用率低下的問題，提出了一種基于滾動窗口技術和遺傳算法的柔性車間動態(tài)調度方法；張祥等［6］以最大完工時間、設備負載與能耗為優(yōu)化目標，設計提出了一種多目標柔性作業(yè)車間動態(tài)調度模型與多目標粒子群遺傳算法（Multi-Objec?tive Particle Swarm Genetic Algorithm，MOPS?GA），能夠及時對柔性作業(yè)車間中的擾動做出響應；Wang 等［7］為模擬真實的柔性作業(yè)車間生產環(huán)境，提出了一種包括緊急插單在內共6種擾動的多目標動態(tài)調度模型，并設計了一種基于深度強化學習的算法，取得了較好的效果；Li等［8］研究了考慮4種動態(tài)事件的柔性作業(yè)車間調度問題，設計了一種基于蒙特卡羅樹搜索算法（Monte Carlo Tree Search，MCTS）的重調度方法以降低制造跨度，實驗證明該方法具有良好的求解質量與計算效率。

NSGA-III算法相比于其他尋優(yōu)算法具有更好的多樣性和全局搜索的能力，因此目前被廣泛應用于多目標優(yōu)化問題的求解中［9］。Liu 等［10］利用NSGA-III 算法對柔性的土方調度問題進行求解，并通過AHP 在Pareto 解集中選取最佳方案以提高效率；安友軍等［11］針對多目標柔性作業(yè)車間調度問題，設計提出了一種近似支配的NSGA-III-AD算法，有效提高了求解時算法的收斂性、多樣性以及局部搜索力度；畢曉君等［12］設計了一種基于參考點約束支配的NSGA-III 算法，以提高算法在求解帶約束的高維多目標優(yōu)化問題時的收斂性與分布性。

為了及時地、有效地應對生產過程中隨機出現的擾動事件，本文對車間擾動下的柔性作業(yè)車間多目標動態(tài)調度問題展開研究。首先確定以重調度需求度為基礎的動態(tài)調度驅動機制，并給出重調度需求度的度量方法，接著提出以客戶滿意度、設備總負載以及方案偏移度為優(yōu)化目標的多目標動態(tài)調度模型，并設計一種改進后NSGA-III算法對模型進行計算求解。最后通過實際案例驗證該種柔性作業(yè)車間動態(tài)調度策略的適用性與有效性。

1 基于重調度需求度的混合驅動機制研究

1.1 基于重調度需求度的混合動態(tài)調度驅動機制

目前制造行業(yè)中應用最為廣泛的動態(tài)調度驅動機制包括3種:事件驅動機制（Event-Driven Re?scheduling，EDR）、周期驅動機制（Periodic Re?scheduling，PR）以及混合驅動機制（Hybrid-Driv?en Rescheduling，HDR），3 種驅動機制的特點對比結果如表1所示。

表1 動態(tài)調度驅動機制對比

本文在考慮柔性作業(yè)車間對動態(tài)調度實際需求的基礎上，結合上述3種動態(tài)調度驅動機制的分析，構建完善的動態(tài)調度驅動機制。本文考慮在決策是否進行動態(tài)調度時，需要綜合考慮擾動事件的嚴重性與生產系統的可調度性。一方面，盡可能地消除擾動事件對生產活動造成的不利影響，另一方面也要避免過于頻繁的動態(tài)調度操作引起的生產資源的浪費以及生產系統的震蕩。

因此，本節(jié)在構建混合動態(tài)調度驅動機制時引入重調度需求度的概念，表示在綜合考慮擾動嚴重性以及生產系統可調度性的情況下，衡量原定生產計劃需要進行動態(tài)調度的程度。基于重調度需求度的混合動態(tài)調度驅動機制兼顧了顯性、隱性擾動對生產車間的影響:對于顯性擾動，當擾動出現且重調度需求度大于所設閾值時，則進行動態(tài)調度；對于隱性擾動，到達周期調度節(jié)點時進行重調度需求度的計算，若需求度大于閾值則觸發(fā)動態(tài)調度。

1.2 重調度需求度度量方法

本文中的重調度需求度為綜合性評判指標，需結合生產進度變動率以及加工設備開動率進行確定，各參數的定義以及重調度需求度的具體計算方法如下。

1.2.1 生產進度變動率

將擾動后繼續(xù)按原調度方案生產的最大完工時間與理想情況下按原調度方案的最大完工時間作對比，將得到的最大完工時間偏移量定義為生產進度變動系數θ。絕對的最大完工時間延遲量不能充分描述擾動對原調度方案的影響程度，因此提出生產進度變動率V的概念，用以表征由擾動造成的生產進度延后對原調度方案的影響程度，由生產進度變動系數與原調度方案最大完工時間T的比值來確定，具體計算公式為:

1.2.2 加工設備開動率

在決策是否需要動態(tài)調度之前，需衡量原調度方案的可調度性。本文通過加工設備開動率R表征調度方案的可調度性，可調度性高表明原調度方案加工節(jié)奏并不緊湊，設備空閑時間較多。加工設備開動率由原調度方案中加工設備的實際工作時間與最大完工時間的比值確定，計算公式為:

式中，m 為調度方案中的設備數量，Tk為第k臺設備的實際加工時長。

1.2.3 重調度需求度

通過綜合考慮擾動嚴重性以及生產系統可調度性，衡量原調度方案需要進行動態(tài)調度的程度。重調度需求度S可根據上述兩個參數進行確定，計算公式為:

2 考慮車間擾動的柔性作業(yè)車間多目標動態(tài)調度模型

2.1 問題描述

本文研究的問題可以描述為:優(yōu)化目標為客戶滿意度、設備總負載與方案偏移度，調度對象為多個待加工工件，調度結果是為每個工件的每道工序選擇合適的加工設備，并安排同一加工設備上各工件的加工順序，最終達到優(yōu)化目標的最優(yōu)化。建立數學模型之前做出以下假設:

1）各個待加工工件優(yōu)先級相同；

2）工序間轉移時間可忽略；

3）各個待加工工件工藝路線唯一；

4）工件完工后入庫、發(fā)運時間可忽略。

2.2 模型建立

2.2.1 相關參數

1）待加工工件集合J包含了n個待加工工件，每個工件可表示為ji，每個工件的交貨期可以用Di表示，每個工件的完工時間可以用Ei表示（i=1，2，…，n）；

2）對于任意一個待加工工件ji，對應的工藝路線為li，li中含有Si個工序，li中的任意工序都可以用Ois（s=1，2，…，Si）表示；

3）作業(yè)車間設備的集合為M，總數為m臺，每臺設備可以記作Mk（k=1，2，…，m）；

4）對于任意工序Ois，設定至少可以由設備集合M中的一臺設備進行加工，由Mis來表示工序Ois可以選擇的設備集合；

5）yisk均為{0，1}變量，yisk=1表示工件ji的第s道工序選擇了第k臺設備，否則yisk=0；

6）tisk表示工件ji的第s道工序在第k臺設備上的加工耗時；

2.2.2 目標函數

1）客戶滿意度

客戶滿意度一般與訂單交付時間有關，訂單交付時間越準時客戶滿意度越高，因此，客戶滿意度的評價值可通過產品完工時間和交貨期的差值確定，且目標函數值越大越優(yōu)，計算公式如下:

2）設備總負載

本文的設備總負載指標通過所有設備實際工作時長表征，且目標函數值越小越優(yōu)，計算公式為:

3）方案偏移度

方案偏移度表征動態(tài)調度方案相對于原調度方案的優(yōu)化程度，目標函數值越大越優(yōu)，可通過客戶滿意度與設備總負載指標的偏移量進行定義，計算公式為:

式中，α與β取值按實際需求確定。

2.2.3 優(yōu)化變量

第一個優(yōu)化變量{0，1}變量yisk，此變量決定了第s道工序的設備選擇，設備性能不同導致工序的加工時間會發(fā)生變化，進而影響目標函數值。其次，由于動態(tài)調度模型中引入了混合驅動機制，所以調度周期Tf、與重調度需求度閾值S0的取值都將影響動態(tài)調度模型以及算法的求解，因此將Tf、S0均設置為優(yōu)化變量。

2.2.4 約束條件

1）設備進行工件加工具有先后順序:

2）工件加工順序的正確性:

3）工序加工的完整性:

4）工序對設備的獨占性:

5）工序選擇設備的唯一性:

6）{0，1}變量約束:

對于約束條件1）和2），若同一臺設備上需要加工多個待加工工件，本文構建的生產調度模型需要確定該臺設備上工件之間的加工順序，并嚴格按照加工順序依次對工件進行加工，前一個工件加工完成后才可進行下一個工件的加工。對于約束條件3）～5），生產調度模型首先確定每個待加工工件的工藝路線，所有工件必須按照相應工藝路線中的工序順序進行加工，且任意一道加工工序一旦開始，必須等待其完成才可以進行下道工序的加工；每個待加工工件的任意一道工序僅能選擇一臺可選設備進行加工，且在同一時刻每臺設備只能對一個工件的其中一道工序進行加工。對于約束條件6），在本文構建的動態(tài)調度模型中，變量yisk與的取值只能為0或者1。

3 求解算法設計

NSGA-III算法的主要機理與NSGA-II算法相似，兩者之間的區(qū)別在于選擇機制的不同。NS?GA-III 算法中采用參考點機制代替NSGA-II 中擁擠度排序機制，使得NSGA-III 在高維目標空間內也能保持優(yōu)異的性能。本文針對實際問題的需要，對標準NSGA-III算法進行設計改進，以最終得到的INSGA-III作為模型求解算法。

3.1 染色體編碼

本文提出的柔性作業(yè)車間動態(tài)調度模型對初始解的質量十分敏感，因此本文采用混沌Logistic映射實數編碼方式，提高初始種群在解集空間內分布的均勻度。利用式（13）產生混沌序列:

式中，μ為分叉參數，當3.57<μ≤4 時，Logis?tic 映射處于完全混沌狀態(tài)，本文取μ=4，y0的值由隨機函數自動生成。

3.2 交叉算子

采用正態(tài)分布交叉算子（NDX）代替原交叉算子，有效提高算法的全局搜索能力，更好地保證解集的多樣性，其中，NDX算子的數學表達如式14所示:

式中，P1與P2代表父代種群，Q1與Q2代表子代種群，N(0,1) 為正態(tài)分布隨機變量，θ為隨機數，且取值區(qū)間在(0,1) 上均勻分布。

3.3 自適應交叉、變異概率

本文采取自適應交叉、變異概率以提高算法整體性能，保證算法的收斂性與解集的多樣性，自適應交叉、變異概率表達式如式（15）和式（16）所示。

式中，pc為自適應交叉概率，pm為自適應變異概率；fmaxi、fmini與favgi分別為第i個目標函數的適應度的最大值、最小值與平均值；fi表示待交叉?zhèn)€體中較大的適應度值，f'i表示待變異個體的適應度值；k1、k2、k3以及k4均為常數，且0

綜合上述分析，整理得到INSGA-III算法流程如圖1所示:

圖1 INSGA-III算法流程

4 案例分析

結合上述混合動態(tài)調度驅動機制與INS?GA-III 算法的研究，整理得到柔性作業(yè)車間的動態(tài)調度框架，具體流程如圖2所示:

圖2 考慮擾動的柔性作業(yè)車間動態(tài)調度流程

4.1 案例描述

本文選取某企業(yè)2022 年12 月15 日上午的加工計劃為例，已知當日該企業(yè)柔性作業(yè)車間內共有5個待加工工件與8臺可用加工設備，待加工工件與加工設備的相關信息見表2 和表3，當日初始調度方案甘特圖如圖3所示。同時，設定本案例中INSGA-III 算法中種群規(guī)模為150，最大迭代次數為500 次，α與β均為0.5，調度周期Tf=60 min。為了驗證本文INSGA-III 算法的有效性，將NS?GA-III作為對比算法，參數設置與INSGA-III保持一致。

圖3 初始調度方案

表2 待加工工件信息

表3 工件可選加工設備與加工時間

4.2 周期驅動

當t=60 min時，由隱性擾動累積引起的生產進度變動系數為6 min，計算得到重調度必要度大于閾值，執(zhí)行動態(tài)調度操作。整理得到周期調度時刻加工信息如表4所示，根據表4中信息驅動動態(tài)調度，由INSGA-III算法求得的動態(tài)調度方案的甘特圖如圖4 所示，由NSGA-III 算法求得的動態(tài)調度方案如圖5所示。由圖4可得，動態(tài)調度方案中工序O33于t=67 min時在設備M8上開始加工，工序O53于t=66 min 時在設備M7上開始加工；由圖5 可得，工序O33于t=67 min 時在設備M8上開始加工，工序O53于t=73 min時在設備M8上開始加工。

圖4 INSGA-III動態(tài)調度方案甘特圖

圖5 NSGA-III動態(tài)調度方案甘特圖

表4 周期調度時刻加工信息表

由表5 動態(tài)調度方案與原調度方案目標函數對比可知，INSGA-III算法求得的動態(tài)調度方案相比于原調度方案，客戶滿意度提高了10.77%，設備總負載降低了0.86%，方案偏移度為5.82%；相比于NSGA-III 算法求得的動態(tài)調度方案，客戶滿意度提高了2.37%，設備總負載升高了0.88%，方案偏移度增大17.10%，雖然設備總負載有所升高，但幅度較低，且客戶滿意度與方案偏移度均有所提升，因此本文提出的動態(tài)調度方法具有較好的應用效果。

表5 周期驅動調度方案目標函數對比

4.3 顯性擾動驅動

設在t=1 min時刻，工件5的交貨期發(fā)生變更，由原本的2022 年12 月15 日10:30 變更為同一天08:05，計算得到重調度必要度大于閾值，對生產系統進行動態(tài)調度。整理得到顯性擾動發(fā)生時刻加工信息如表6所示。

表6 顯性擾動發(fā)生節(jié)點加工信息

根據表6 中信息驅動動態(tài)調度，由INSGA-III算法求得的動態(tài)調度方案的甘特圖如圖6 所示，由NSGA-III算法求得的動態(tài)調度方案的甘特圖如圖7 所示。由圖6 可得，動態(tài)調度方案中工序O53于t=48 min時在設備M7上開始加工，工序O23于t=68 min 時開始加工，工序O33于t=61 min 時在設備M8開始加工；由圖7可得，動態(tài)調度方案中工序O53于t=48 min時在設備M7上開始加工，工序O23于t=68 min 時開始加工，工序O33于t=61 min 時在設備M8開始加工。

圖6 INSGA-III動態(tài)調度方案甘特圖

圖7 NSGA-III動態(tài)調度方案甘特圖

動態(tài)調度方案與原調度方案目標函數對比如表7 所示，可知由INSGA-III 算法求得的動態(tài)調度方案相比于原調度方案，客戶滿意度提高了23.21%，設備總負載降低了0.86%，方案偏移度為12.04%；相比于NSGA-III 算法求得的動態(tài)調度方案，客戶滿意度提高了4.03%，設備總負載一致，方案偏移度增大24.77%，雖然設備總負載沒有明顯優(yōu)化，但客戶滿意度與方案偏移度均有所提升，且提升幅度較大，因此本文提出的動態(tài)調度方法具有較好的應用效果。

表7 顯性擾動驅動調度方案目標函數對比

5 結論

本文首先結合現有理論研究內容確定了基于重調度需求度的混合動態(tài)調度驅動機制，并給出了重調度需求度的計算方法。然后針對柔性作業(yè)車間的實際需求，建立了考慮車間擾動的多目標動態(tài)調度模型，并設計了一種INSGA-III算法對模型的客戶滿意度、設備總負載以及方案偏移度3個目標函數進行優(yōu)化求解。最后分別設置周期驅動以及顯性擾動驅動兩個案例，驗證了本文提出的動態(tài)調度驅動機制、動態(tài)調度模型以及求解算法的可行性與有效性。