王少參，唐 宇，翟書磊

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

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

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

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

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

1 基于重調(diào)度需求度的混合驅(qū)動機制研究

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

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

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

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

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

1.2 重調(diào)度需求度度量方法

本文中的重調(diào)度需求度為綜合性評判指標，需結(jié)合生產(chǎn)進度變動率以及加工設(shè)備開動率進行確定，各參數(shù)的定義以及重調(diào)度需求度的具體計算方法如下。

1.2.1 生產(chǎn)進度變動率

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

1.2.2 加工設(shè)備開動率

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

式中，m 為調(diào)度方案中的設(shè)備數(shù)量，Tk為第k臺設(shè)備的實際加工時長。

1.2.3 重調(diào)度需求度

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

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

2.1 問題描述

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

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

2）工序間轉(zhuǎn)移時間可忽略；

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

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

2.2 模型建立

2.2.1 相關(guān)參數(shù)

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

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

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

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

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

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

2.2.2 目標函數(shù)

1）客戶滿意度

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

2）設(shè)備總負載

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

3）方案偏移度

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

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

2.2.3 優(yōu)化變量

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

2.2.4 約束條件

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

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

3）工序加工的完整性:

4）工序?qū)υO(shè)備的獨占性:

5）工序選擇設(shè)備的唯一性:

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

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

3 求解算法設(shè)計

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

3.1 染色體編碼

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

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

3.2 交叉算子

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

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

3.3 自適應(yīng)交叉、變異概率

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

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

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

圖1 INSGA-III算法流程

4 案例分析

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

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

4.1 案例描述

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

圖3 初始調(diào)度方案

表2 待加工工件信息

表3 工件可選加工設(shè)備與加工時間

4.2 周期驅(qū)動

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

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

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

表4 周期調(diào)度時刻加工信息表

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

表5 周期驅(qū)動調(diào)度方案目標函數(shù)對比

4.3 顯性擾動驅(qū)動

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

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

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

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

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

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

表7 顯性擾動驅(qū)動調(diào)度方案目標函數(shù)對比

5 結(jié)論

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