考慮工人疲勞和學(xué)習(xí)效應(yīng)的裝備制造車間動態(tài)調(diào)度

郭超 郝東輝 郭鵬

摘 要：針對大型裝備制造車間人機雙資源調(diào)度中工人疲勞和學(xué)習(xí)效應(yīng)集成優(yōu)化難的問題，基于指數(shù)型疲勞表征和DeJong學(xué)習(xí)曲線，構(gòu)建混合整數(shù)規(guī)劃模型。根據(jù)雙資源調(diào)度問題的編碼特征，結(jié)合排序規(guī)則生成初始調(diào)度方案，結(jié)合移除和插入操作設(shè)計自適應(yīng)大鄰域搜索算法，以求解人機雙資源分配、工件排序、動態(tài)調(diào)度等子問題。同時，圍繞緊急插單、機器故障、工人離崗等擾動設(shè)計重調(diào)度策略，基于原有算法實現(xiàn)動態(tài)調(diào)度，并進行算法測試。結(jié)果表明，與求解器、規(guī)則、遺傳算法等相比，所提算法找到了完工時間更短的調(diào)度方案，且在緊急插單、機器故障、工人離崗等動態(tài)調(diào)度場景下，也能夠給出更好的結(jié)果。所研究的裝備制造車間調(diào)度問題同時考慮了工人疲勞與學(xué)習(xí)效應(yīng)，對應(yīng)算法可為大型裝備制造排產(chǎn)系統(tǒng)開發(fā)提供參考。

關(guān)鍵詞：計算機輔助制造；作業(yè)車間調(diào)度； 工人疲勞；學(xué)習(xí)效應(yīng)；自適應(yīng)大鄰域搜索；動態(tài)調(diào)度

Equipment manufacturing job shop dynamic scheduling with worker fatigue and learning effect

GUO Chao^1，2， HAO Donghui³， GUO Peng^1，4

（1.Technology and Equipment of Rail Transit Operation and Maintenance Key Laboratory of Sichuan Province， Chengdu， Sichuan 610031， China; 2.School of Intelligent Manufacturing， Yibin Vocational and Technical College， Yibin， Sichuan 644003， China; 3.Luoyang Institute of Electro-Optical Equipment of AVIC， Luoyang， Henan 471000， China; 4.School of Mechanical Engineering， Southwest Jiaotong University， Chengdu， Sichuan 610031， China）

Abstract：Aiming at the problem of integrating optimization of worker fatigue and learning effects faced by human and machine dual-resource scheduling in large equipment manufacturing workshops， a mixed-integer programming model was constructed based on exponential fatigue characterization and DeJong learning curves. In accordance with the coding characteristics of the dual-resource scheduling problem， an initial scheduling scheme was generated based on sorting rules， and an adaptive large neighborhood search algorithm was designed by combining removal and insertion operations to solve sub-problems， such as the allocation of human and machine resources， job sequencing and dynamic scheduling. A rescheduling strategy was also designed to address disturbances such as urgent job insertions， machine failures and worker absences. Based on the original algorithm， dynamic scheduling was implemented and tested. The results show that compared with solvers， rules， genetic algorithms and other methods， the proposed algorithm can find scheduling solutions with shorter completion times， and it also performs better in dynamic scheduling scenarios such as urgent orders insert， machine breakdowns and worker absences. The proposed equipment manufacturing workshop scheduling problem takes into account worker fatigue and learning effects， and the corresponding algorithm can provide reference for the development of large-scale equipment manufacturing production scheduling systems.

Keywords：computer aided manufacturing; job shop scheduling; worker fatigue; learning effect; adaptive large neighborhood search; dynamic scheduling

隨著“中國制造2025”戰(zhàn)略的實施與推進，人機協(xié)同成為智能制造的主流發(fā)展趨勢。一方面，在大型裝備制造過程中，復(fù)雜的焊接或裝配工藝導(dǎo)致難以依靠機器人自動化實現(xiàn)，高素質(zhì)工人成為此類企業(yè)關(guān)鍵的生產(chǎn)資源^［1］。但過度的疲勞會對工人的身體健康產(chǎn)生不利的影響，甚至?xí)斐蓢?yán)重的安全事故和經(jīng)濟損失^［2］。在車間調(diào)度問題中考慮工人的疲勞因素是十分必要的。另一方面，在生產(chǎn)過程中往往存在著工件動態(tài)到達、插單、機器故障等擾動事件，系統(tǒng)則需要根據(jù)擾動事件類型對初始調(diào)度方案作出調(diào)整以滿足加工需求，通過合理的工作分配和休息策略，可以在保障工人安全生產(chǎn)的同時有效縮短生產(chǎn)周期、提高資源利用率。此外，學(xué)習(xí)效應(yīng)同樣是影響人機雙資源柔性作業(yè)車間調(diào)度問題的重要因素。

JANSEN等^［3］探究了不同工作制模式與員工疲勞患病率之間的關(guān)系，發(fā)現(xiàn)疲勞因素是工人辭職或轉(zhuǎn)行的重要原因。LI等^［4］針對工人疲勞易引起員工績效下降的問題，提出基于休息的數(shù)學(xué)規(guī)劃模型，有效提高了員工的滿意度。JAMSHIDI等^［5］強調(diào)人在調(diào)度系統(tǒng)中的維護作用，并針對工人疲勞提出基于疲勞恢復(fù)的數(shù)學(xué)模型，該模型中疲勞是當(dāng)前工作時間和最大工作時間的比值。BERTI等^［6］將人體的累積疲勞整合到調(diào)度算法中，讓工人在疲勞達到一定強度時進行休息。MOUAYNI等^［7］考慮了調(diào)度作業(yè)中的人為因素，基于貪婪隨機自適應(yīng)搜索過程，提出考慮工人疲勞和可靠性的整數(shù)規(guī)劃作業(yè)調(diào)度模型。FU等^［8］考慮了源自生物數(shù)學(xué)模型的生物數(shù)學(xué)疲勞約束，開發(fā)了嵌入禁忌搜索啟發(fā)式調(diào)度算法以解決車輛路徑和調(diào)度的組合問題。ZHANG等^［9］針對人機協(xié)同裝配任務(wù)調(diào)度中人的疲勞問題，提出了基于疲勞積累恢復(fù)特性的任務(wù)調(diào)度模型和改進的化學(xué)反應(yīng)優(yōu)化算法。盡管目前企業(yè)和學(xué)者對工人疲勞的處理措施多樣，但仍然需要開發(fā)有效的調(diào)度算法來解決此類問題。

在學(xué)習(xí)效應(yīng)方面，WRIGHT^［10］提出了對數(shù)線性模型以表示工人的學(xué)習(xí)效應(yīng)，該模型中生產(chǎn)時間隨著生產(chǎn)次數(shù)的增加而減小。在后續(xù)的數(shù)十年中，許多關(guān)于學(xué)習(xí)效應(yīng)的研究都是基于此模型的改進，BISKUP^［11］總結(jié)了現(xiàn)有文獻中關(guān)于學(xué)習(xí)模型的多種變體。JANIAK等^［12］考慮了基于經(jīng)驗的學(xué)習(xí)模式。WANG等^［13］提出工件實際加工時間與序列位置和位置權(quán)重相關(guān)的學(xué)習(xí)模型。此外，考慮醫(yī)護人員疲勞效應(yīng)和截斷學(xué)習(xí)效應(yīng)的醫(yī)護調(diào)度^［14］，加工時間可變情況下具有指數(shù)學(xué)習(xí)效應(yīng)和凸資源分配排序^［15］，考慮學(xué)習(xí)效應(yīng)的雙資源約束柔性車間調(diào)度^［16］等問題均有涉及。但在實際生產(chǎn)中，作業(yè)的實際處理時間不會隨著操作次數(shù)的無限增加而趨于零，現(xiàn)有研究大多數(shù)忽略了學(xué)習(xí)效應(yīng)，或未注意到學(xué)習(xí)效應(yīng)存在著極限的問題，這將對生產(chǎn)制造系統(tǒng)的長時間調(diào)度產(chǎn)生較大的影響。

為此，本研究面向裝備制造研究人機雙資源約束柔性作業(yè)車間調(diào)度問題（dual resource constrained flexible job-shop scheduling problem， DRCFJSP），綜合考慮工人的疲勞效應(yīng)和學(xué)習(xí)效應(yīng)，以最小化完工時間為優(yōu)化目標(biāo)，建立混合整數(shù)規(guī)劃模型；針對調(diào)度過程中動態(tài)擾動事件，提出動態(tài)調(diào)度策略，并設(shè)計多種動態(tài)場景驗證模型的響應(yīng)能力；提出自適應(yīng)大規(guī)模鄰域搜索（adaptive large neighborhood search， ALNS）算法用于靜態(tài)調(diào)度和動態(tài)調(diào)度的方案獲取。

1 問題描述與模型建立

1.1 疲勞效應(yīng)與學(xué)習(xí)效應(yīng)

在生產(chǎn)調(diào)度過程中考慮工人疲勞因素，有利于保護工人健康和提高生產(chǎn)效率。文獻［1］提出的指數(shù)型疲勞模型能較好反映出工人在實際工作過程中的疲勞變化情況，計算方式如下。

ft+1=xt×（1-（1-ft）×exp（-λ））+（1-xt）×ft×exp（-μ）。（1）

式中：ft和ft+1分別為工人在t和t+1時刻末的疲勞值；λ和μ是工人疲勞累計率和疲勞恢復(fù)率；xt取值為0或1，1表示工人處在工作狀態(tài)，0表示工人處在休息狀態(tài)。而在生產(chǎn)加工過程中，適當(dāng)休息有利于整個生產(chǎn)效率提升和避免工人累計疲勞損傷。而工人的休息時間最好由工人當(dāng)前疲勞值和下一個要加工工件的加工時間動態(tài)確定。在此假設(shè)工人疲勞的休息標(biāo)準(zhǔn)為fe，工人當(dāng)前疲勞值為f0 （f0＜fe），工人加工下一工件的加工時長為tw。首先，計算工人的可繼續(xù)加工時間tc：

若tc≥tw，工人可繼續(xù)工作；否則工人需要休息，休息時長τ為

fe=1-（1-f1）×exp（-μ×tw），（3）

式中：f1=f0×exp（-μ×τ）；τ=（ln f0-ln f1）/μ。

在考慮學(xué)習(xí)效應(yīng)的加工環(huán)境中，工件的實際加工時間并不會無限減少至0。在此采用DeJong學(xué)習(xí)模型^［17］對其進行描述如下：

Tx=T0×（Z+（1-Z）×x^-φ） ，（4）

式中：T0為某個工件的理論加工時長；Tx為第x次加工此工件時的實際加工時長；Z是取值在0到1之間的不可壓縮系數(shù)，表征加工此工件的最小必需時長為Z×T0；φ是與工人的個人素質(zhì)有關(guān)的學(xué)習(xí)效應(yīng)系數(shù)，即學(xué)習(xí)能力的大小。

1.2 問題描述

假設(shè)某人機協(xié)作生產(chǎn)車間中有一定數(shù)量的工人和機器，分別用集合W={W1， W2， …， Wc}和集合M={M1， M2， …， Md}表示，其中c和d分別表示工人總數(shù)和機器總數(shù)。同類型的機器具有相同的加工效率，不同類型的機器數(shù)量和效率不盡相同。由于職責(zé)和分工不同，工人所能操作的機器類型也不同。

現(xiàn)在計劃加工一批共計n個工件，用集合表示為J={J1， J2， …， Jn}，由于機器類別和工人效率的不同，每個工件的實際加工時長取決于分配的機器資源和工人資源。需要滿足下述約束條件。

1）工人的狀態(tài)分為工作和休息2種：若為工作狀態(tài)，工人只允許在一臺機器上加工1個工件；若為休息狀態(tài)，則不占用機器和工件。

2）機器的狀態(tài)分為工作和不工作，若為工作狀態(tài)，每臺機器在同一時刻只允許加工1個工件，只允許被1個工人操作；若為不工作狀態(tài)，則不占用工人和工件。

3）每個工件有2道工序：首先，需要工人在機器上輔助安裝加工模具和上料；然后，再由機器自動加工，即工人處理部分和機器加工部分，兩者之間不允許存在時間間隙。

4）每個工件都需要被加工1次。

5）某個工件一旦開始加工，負(fù)責(zé)處理的工人不能離開，直至工件的工人處理部分完成，負(fù)責(zé)加工的機器不能中斷，直至當(dāng)前工件的機器加工部分結(jié)束，除非發(fā)生動態(tài)事件。

6）所有工人和所有機器在整個加工過程中都是可用的，除非發(fā)生動態(tài)事件。

7）每臺機器的位置是固定的，忽略工件以及工人在不同機器之間的轉(zhuǎn)移時間。

8）所有工人和所有機器的初始開始時刻為零時刻。

9）在整個生產(chǎn)過程中，工人的疲勞值不允許超過指定上限。

10）工件的實際加工時間由工人、機器和加工順序共同決定。

調(diào)度的目標(biāo)是，在滿足上述所有約束的條件下，為這批工件合理地分配機器和工人，確定加工順序，以及每個工件加工的開始時間和結(jié)束時間，最終使得所有工件加工完畢時的完工時間最小化。

1.3 模型建立

基于上述問題的描述與假設(shè)，構(gòu)建如下的混合整數(shù)規(guī)劃模型，如表1所示。

目標(biāo)函數(shù)為

minC_max。 ????（5）

約束為

式（5）為最小化完工時間的目標(biāo)函數(shù)；約束（6）確保每臺機器在同一時刻只能分配一個工人和一個工件；約束（7）確保每個工件僅可被加工一次；約束（8）確保工人只能操作自己可操作的機器；約束（9）和約束（10）要求工件的開始加工時間不能早于機器和工人的可開始時間；約束（11）記錄了工人的實時工作次數(shù)；約束（12）根據(jù)工人的工作次數(shù)計算了工人的實時學(xué)習(xí)率；約束（13）和約束（14）分別計算了考慮學(xué)習(xí)效應(yīng)的工人結(jié)束時間和機器結(jié)束時間；約束（15）和約束（16）計算了工人的工作時間和休息時間；約束（17）和約束（18）基于疲勞公式（1）分別計算出了工人在休息后和工作后的疲勞值；約束（19）要求工人的疲勞值不超過規(guī)定上限。

2 改進自適應(yīng)大鄰域搜索算法

標(biāo)準(zhǔn)自適應(yīng)大鄰域搜索算法在解決車輛路徑類問題^［18-20］（vehicle routing problem， VRP）時表現(xiàn)出了優(yōu)異的搜索效率和尋優(yōu)性能。但當(dāng)用來求解DRCFJSP時，破壞算子和修復(fù)算子的權(quán)重和得分只有在獲得更優(yōu)解后才得到更新，同時由于隨機因素的存在，算法在每次迭代中并不能準(zhǔn)確地選擇到當(dāng)前最優(yōu)的修復(fù)算子，從而導(dǎo)致算法在搜索前期不能取得較好的效果，且容易在獲得當(dāng)前鄰域局部最優(yōu)解之前過早進入下一鄰域，即早熟問題。針對這一問題，本文提出改進的ALNS算法，改進算法使用多組破壞算子和修復(fù)算子，每次迭代根據(jù)歷史表現(xiàn)對破壞算子進行自適應(yīng)選擇，然后挑選修復(fù)算子中最優(yōu)的一個進行修復(fù)操作，以獲得新解。同時為了避免陷入局部最優(yōu)，使用改進接受準(zhǔn)則在一定概率下接受劣解。

2.1 編碼與解碼

雙資源約束的調(diào)度問題可細(xì)分為工件排序、設(shè)備分配、工人指派3個子問題，相對應(yīng)地，其可行解可用一定規(guī)則的三級編碼來表達，3個編碼的長度相同且一一對應(yīng)：一級是機器分配編碼，其數(shù)字表示所選擇的機器序號；二級是工人指派編碼，其數(shù)字表示所選擇的工人編號；三級是工件排序編碼，其數(shù)字表示所選擇的工件編號。圖1展示了2個工人操作4臺設(shè)備加工10個工件時的示例編碼，以工件碼第4位置的數(shù)字6為例，其表示工件6的加工順序為第4，且分配的資源是機器2和工人1。

解碼是將編碼轉(zhuǎn)化為目標(biāo)函數(shù)的過程。首先，根據(jù)工序碼中工件的順序，依次為當(dāng)前工件分配對應(yīng)的機器和工人；然后，由所選機器和工人的最早可開始時間，確定當(dāng)前工件的開始加工時間和實際加工時長，直至最后一個工件；最后，獲得最大完工時間，即目標(biāo)函數(shù)。

2.2 初始解生成

ALNS算法需要一個初始解，其質(zhì)量在一定程度上決定算法后續(xù)的優(yōu)化效率。采用啟發(fā)式規(guī)則方法來生成初始解，在學(xué)習(xí)效應(yīng)的影響下，隨著工人操作熟練度的增加，理論時長越長的工件排序越靠后，其所減免的加工時間就越多，這將有利于目標(biāo)函數(shù)。初始解生成規(guī)則如圖2所示，首先，選擇最早的可用機器；其次，再選擇當(dāng)前機器所在單元的空閑工人中疲勞值最小的工人；最后，分配工人操作階段時間最小的工件，若工件的工人操作時間相同，則選擇機器處理時間最小的工件進行加工。

2.3 操作算子

在初始解生成后，開始迭代搜索。在每次迭代中，破壞算子會先對當(dāng)前解移除一定數(shù)量的工件節(jié)點，得到破壞解和移除列表，然后修復(fù)算子再將移除列表中的節(jié)點按照一定規(guī)則插入破壞解中，最終得到新的可行解，如圖3所示。改進的自適應(yīng)大規(guī)模鄰域搜索算法設(shè)計了6個破壞算子和6個修復(fù)算子。

2.3.1 破壞算子

1）隨機破壞算子：隨機選擇原序列中的k個工件進行移除，以此防止局部最優(yōu)，在修復(fù)算子時能夠?qū)x定的k個工件進行重排序操作；

2）貪婪破壞算子1：依次計算當(dāng)前工件移除后對原序列成本的影響，取對完工時間影響最大的前k個工件作為最終要移除的工件；

3）貪婪破壞算子2：依次計算當(dāng)前工件移除后對原序列成本的影響，取對完工時間影響最大的工件作為當(dāng)前要移除的工件，更新當(dāng)前序列并重復(fù)此步驟k次；

4）相似破壞算子：隨機移除一個工件，然后計算移除工件對剩余工件的相似度，再移除相似度較高的k-1個工件，共計k個;

5）最差破壞算子1：與貪婪破壞算子1相似，不同的是，移除的是對完工時間影響最小的工件；

6）最差破壞算子2：與貪婪破壞算子2相似，不同的是，移除的是對完工時間影響最小的工件。

2.3.2 修復(fù)算子

1）隨機修復(fù)算子：隨機選擇k個位置，將移除的工件依次插入；

2）最優(yōu)修復(fù)算子：從移除列表的第一個工件開始，每次選擇完工時間最小的位置進行插入，直至所有工件插入完畢；

3）隨機最優(yōu)修復(fù)算子：與最優(yōu)修復(fù)算子相似，但移除工件列表要先隨機打亂順序;

4）次優(yōu)修復(fù)算子：與最優(yōu)修復(fù)算子類似，但插入的位置是完工時間第2小的位置；

5）后悔修復(fù)算子：首先，計算每個移除工件的最優(yōu)插入和次優(yōu)插入的成本，后悔值即兩者的完工時間差，根據(jù)后悔值由大到小對移除工件列表排序，然后按照最優(yōu)修復(fù)算子進行相同的操作；

6）逆序最優(yōu)修復(fù)算子：與最優(yōu)修復(fù)算子相似，但移除工件列表要進行逆序操作。

2.4 接受準(zhǔn)則

為了避免陷入局部最優(yōu)，本文設(shè)計了改進的接受準(zhǔn)則：

式中：r為0至1之間的隨機數(shù)；fN和fC分別是新解和當(dāng)前解的目標(biāo)函數(shù)值，即完工時間。該接受準(zhǔn)則與模擬退火接受準(zhǔn)則在形式上相似，但消除了溫度參數(shù)，避免了復(fù)雜的參數(shù)調(diào)試過程。以新解與當(dāng)前解的相對偏差作為衡量標(biāo)準(zhǔn)，可有效避免算法陷入局部最優(yōu)，且相對偏差的值越小，接受新解的概率越大。

2.5 改進ALNS算法流程

本文針對標(biāo)準(zhǔn)ALNS算法求解DRCFJSP問題時早熟和不穩(wěn)定的問題，提出改進的ALNS算法。改進算法使用啟發(fā)式規(guī)則生成初始解，使用得分機制動態(tài)選擇破壞算子，并挑選最有利于當(dāng)前解的修復(fù)算子，使得在每次迭代中都能找到較好的破壞和修復(fù)的組合方式。若新解質(zhì)量不如當(dāng)前解，使用基于相對偏差的接受準(zhǔn)則在一定概率下接受劣解繼續(xù)尋優(yōu)。算法整體步驟如表2所示。

3 靜態(tài)調(diào)度

本文算法編程的計算機硬件配置為Intel i7-12700H CPU和16 GB RAM，計算機軟件環(huán)境為Windows 11的操作系統(tǒng)和Python 3.9語言。

3.1 算例生成

為了驗證本文所提改進自適應(yīng)大鄰域搜索算法在求解考慮工人疲勞的雙資源柔性作業(yè)車間調(diào)度問題時的合理性和有效性，本文結(jié)合文獻^［1］中的算例并進行了擴展，包含小、中、大和超大4種規(guī)模共計16個算例，分別命名為D1至D16。同時，設(shè)置200個不同的工件（編號分別為J1到J200）以供選擇，其中工件的加工時長、工人的疲勞率、工人的疲勞上限、工人學(xué)習(xí)效應(yīng)不可壓縮系數(shù)與工人的學(xué)習(xí)效應(yīng)系數(shù)等信息均通過隨機的方法生成（具體的算例數(shù)據(jù)聯(lián)系作者可獲取）。算例信息如表3所示。

3.2 參數(shù)調(diào)試

算法參數(shù)的設(shè)置會影響算法的收斂速度和求解質(zhì)量，改進的ALNS算法主要涉及迭代次數(shù)和破壞算子移除的工件數(shù)量k 2個關(guān)鍵參數(shù)，接下來需要對其進行調(diào)試。從小、中、大、超大4個規(guī)模中各隨機選擇1個算例，測算了最大迭代次數(shù)為300時k值分別為1至5的表現(xiàn)，結(jié)果如圖4所示。由圖4可以看出，無論k取何值時，迭代次數(shù)在100次之后完工時間已趨于穩(wěn)定，考慮到過多的迭代次數(shù)會有較高的時間成本，因此，選擇迭代次數(shù)為100。同時，實驗運行時間如圖5所示。

從圖5中的數(shù)據(jù)可以看出程序運行時間隨著k值的增大呈線性增長；本文的優(yōu)化目標(biāo)是最小化完工時間，數(shù)據(jù)顯示隨著k值的增大目標(biāo)函數(shù)值的提升空間逐漸縮小，為了避免過多的時間消耗，選擇k值為3，此時有較好的尋優(yōu)效果和適中的運行時間。為此，后續(xù)計算中涉及的算法參數(shù)設(shè)置為：迭代次數(shù)為100，破壞算子移除的工件數(shù)量k為3。

3.3 結(jié)果與對比

由于算法存在隨機因素，為了減少隨機誤差的影響，每個算例重復(fù)獨立運行10次，并使用平均值、最優(yōu)值、標(biāo)準(zhǔn)差、變異系數(shù)和平均運行時間5個指標(biāo)來衡量算法的性能，其中變異系數(shù)是衡量實驗樣本偏離平均值的程度。實驗結(jié)果如表4所示。從表4可以看出，計算結(jié)果的標(biāo)準(zhǔn)差和變異系數(shù)都在較小范圍內(nèi)，同一規(guī)模下的程序運行時間也都保持在相同水平，這體現(xiàn)了本文改進算法在處理復(fù)雜調(diào)度問題時的優(yōu)化性能和穩(wěn)定性能，能夠較好處理不同規(guī)模的問題。

為了深入分析問題，使用Gurobi求解器來求解數(shù)學(xué)規(guī)劃模型。生成規(guī)則具有計算量低、速度快的優(yōu)點，但求解質(zhì)量往往不高，通常用作生成初始解；遺傳算法是應(yīng)用較為廣泛的經(jīng)典啟發(fā)式算法；Jaya算法求解柔性作業(yè)車間調(diào)度問題^［21］，表現(xiàn)出較好的性能。因此，將Jaya算法作為求解DRCFJSP的對比算法之一；標(biāo)準(zhǔn)ALNS算法則用于比較所提算法改進部分的優(yōu)勢。本文使用以上5種不同的算法作為對比，以進一步驗證改進算法的性能和效率。其中，設(shè)置Gurobi的最大求解時間為5 h。表5為最終得到的實驗結(jié)果，其中“—”表示Gurobi未在指定時間內(nèi)求得可行解。

表5結(jié)果顯示，改進ALNS算法在多個算例的求解中都取得了最好的調(diào)度結(jié)果，表明改進算法具有一定的優(yōu)越性；由于數(shù)學(xué)規(guī)劃模型中加入了非線性的疲勞約束，在線性化處理的過程中需要引入多個中間變量，使得Gurobi算法的求解難度增大，在中大規(guī)模問題的求解中未獲得可行解；相較于Jaya算法，改進算法具有較好的尋優(yōu)速度；相較于生成規(guī)則、遺傳算法和標(biāo)準(zhǔn)ALNS算法，改進算法具有較好的求解質(zhì)量。數(shù)據(jù)共同表明本文改進算法的穩(wěn)定性和有效性，具有求解質(zhì)量高、適用規(guī)模大和求解穩(wěn)定性強的優(yōu)點。

4 動態(tài)調(diào)度

由于客戶需求和生產(chǎn)環(huán)境的變化，實際生產(chǎn)過程存在著緊急插單、機器故障、工人離崗等多種不確定因素，極大擾亂生產(chǎn)線的效率以及交貨期。因此，系統(tǒng)需要一定的重調(diào)度能力來應(yīng)對此種不確定性的動態(tài)事件，以保證生產(chǎn)系統(tǒng)的穩(wěn)定性。在此研究緊急插單、機器故障、工人離崗3個動態(tài)事件下的調(diào)度策略，以增強所提模型在應(yīng)對擾動時的靈活性和魯棒性，使之更貼合于實際。應(yīng)對動態(tài)事件的重調(diào)度策略如圖6所示。其中調(diào)度決策過程如下。

步驟1：以動態(tài)發(fā)生時間為線，將工件分為已加工、正在加工、未加工3類；

步驟2：遍歷所有正在加工工件，更新當(dāng)前工人、當(dāng)前機器的可用時間為當(dāng)前工件的完工時間；

步驟3：判斷當(dāng)前工件是否在取消的訂單中，是則執(zhí)行步驟4，否則跳過步驟4；

步驟4：停止此工件的加工，修改當(dāng)前工人、當(dāng)前機器的可用時間為當(dāng)前時刻；

步驟5：判斷當(dāng)前工件的加工工人是否為離崗工人，是則執(zhí)行步驟6和步驟7，否則跳過步驟6和步驟7；

步驟6：停止加工此工件，修改當(dāng)前機器的可用時間為當(dāng)前時刻，將此工件添加到未加工的工件集合中；

步驟7：修改當(dāng)前工人的可用時間為當(dāng)前時刻+缺崗時長，并更新疲勞；

步驟8：判斷當(dāng)前工件的加工機器是否為故障機器，是則執(zhí)行步驟9和步驟10，否則跳過步驟9和步驟10；

步驟9：停止此工件的加工，修改當(dāng)前工人的可用時間為當(dāng)前時刻，更新疲勞，并將此工件添加到未加工的工件集合中；

步驟10：修改當(dāng)前機器的可用時間為當(dāng)前時刻加維修時長；

步驟11：從未加工的工件中刪除取消的工件，將插單的工件添加到未加工的工件集合；

步驟12：獲得新批次工件（未加工）、機器和工人的可開始時間，以及工人疲勞等。

本節(jié)獲得初始調(diào)度方案和重調(diào)度方案的方法仍使用改進ALNS算法。

4.1 緊急插單場景

緊急插單除滿足基礎(chǔ)約束外，還需滿足：1）插單時刻之前已開始加工但未完工的工件具有最高的加工優(yōu)先權(quán)，其加工過程不允許中斷，此工件工人工序的結(jié)束時間是該工人重調(diào)度的可開始時間，機器工序的結(jié)束時間是該機器重調(diào)度的可開始時間；2）插單時刻之前未開始加工的工件需要和插單工件一起進行重調(diào)度。

根據(jù)緊急插單事件的特點，設(shè)計了典型的插單場景：以D8算例為初始加工任務(wù)，在t=80時刻增派工件集合為{J1， J2， J3， J4， J5， J6， J7， J8， J9， J10}的訂單。插單場景下的調(diào)度甘特圖如圖7所示。圖7中0～80 min之間是初始調(diào)度計劃，在80 min發(fā)生了插單事件，以黑色豎線表示，此時新工件的插入并不會影響正在加工的工件；在80 min后，開始執(zhí)行重調(diào)度方案，最終完工時間為314 min。與其他算法的對比結(jié)果如表6所示，表6中的結(jié)果說明改進算法具有良好的尋優(yōu)性能。

4.2 機器故障場景

機器故障事件除了滿足基礎(chǔ)約束外，還需要滿足：1）機器故障發(fā)生時，若此機器正在加工工件，需立即停止此工件的加工，由于此工件的加工被打斷，需要重新開始加工；2）其他非故障機器的加工不受影響。

基于上述問題的描述與約束條件，構(gòu)建的機器故障重調(diào)度場景為：以D12算例為初始加工任務(wù)，在t=60時刻機器M4發(fā)生故障，且經(jīng)過50 min維修后，在t=110時刻重新投入使用。機器故障場景下調(diào)度甘特圖如圖8所示。圖8顯示機器M4在60 min發(fā)生了故障，此時正在加工的工件為J165，由于加工中斷，因此該工件需要重新加工，其重加工任務(wù)由工人W8在機器M12上執(zhí)行；在經(jīng)過50 min的維修后，機器M4在110 min重新投入了使用，圖中網(wǎng)狀方塊表示機器的不可使用時間。此外，與其他算法的對比結(jié)果如表7所示，數(shù)據(jù)表明了改進ALNS算法的優(yōu)異性能。

4.3 工人離崗場景

工人離崗事件除了必要的約束外，還需要滿足：1）工人離崗事件發(fā)生時，此工人加工的工件按完成度可分為4種狀態(tài)：若該工件還未開始加工，則需要安排重調(diào)度；若已完成工人處理部分和機器處理部分，則該工件不需要重新調(diào)度；若該工件處在工人加工部分且未完工，則立即停止此工件的加工，由于此工件的加工被打斷，需要重新開始加工；若該工件已完成工人加工部分，處在機器自動處理階段且未完工，由于機器自動處理階段不需要工人操作，因此該工件不需要重新調(diào)度，待機器自動處理結(jié)束即可完成該工件的加工；2）其他非離崗工人的工作狀態(tài)不受影響。

基于上述問題的描述與約束條件，構(gòu)建了典型的工人離崗場景：以D16算例為初始加工任務(wù)，在t=80 min工人W4由于參加緊急會議而離崗，且經(jīng)過60 min后，在t=140 min重新進入工作崗位。工人離崗場景下調(diào)度甘特圖如圖9所示。

圖9中同顏色的2條豎線之間的區(qū)間表示的是工人W4的不在崗時間。在離崗時刻，工件J126的工人處理部分未完成，因此，需要重新安排調(diào)度，其重加工任務(wù)由工人W8在機器M15上執(zhí)行；在140 min工人W4回歸崗位，開始加工的第一個工件是J185，最終的完工時間為352 min。與其他算法的對比結(jié)果如表8所示，表8的數(shù)據(jù)進一步說明本文改進算法可以有效地處理工人離崗動態(tài)事件，且具有一定的優(yōu)越性。

5 結(jié) 語

本文基于雙資源柔性作業(yè)車間調(diào)度問題，重點研究了調(diào)度過程中工人的疲勞和學(xué)習(xí)效應(yīng)，以及動態(tài)調(diào)度問題，并建立了相應(yīng)的混合整數(shù)規(guī)劃模型。根據(jù)問題的特點，本文對標(biāo)準(zhǔn)的自適應(yīng)大規(guī)模鄰域搜索算法進行了合理改進，通過設(shè)置多組破壞算子和修復(fù)算子來尋求最早的完工時間，以提高人機協(xié)同調(diào)度過程中的資源利用率和生產(chǎn)效率，并保障工人的身心健康和安全。最終不同規(guī)模的多個算例實驗結(jié)果驗證了本文模型和改進算法的可行性和合理性，同時，緊急插單、機器故障、工人離崗復(fù)雜場景下的測試進一步驗證了本文改進ALNS算法的正確性，有效解決了考慮工人疲勞和學(xué)習(xí)效應(yīng)的雙資源柔性作業(yè)車間的動態(tài)調(diào)度問題，為實際的人機協(xié)同車間生產(chǎn)系統(tǒng)提供了有力的理論基礎(chǔ)。

未來將進一步優(yōu)化算法的性能，提出更好的搜索方法提升算法的搜索效率。除此之外，將研究在更復(fù)雜約束條件下的DRCFJSP，如工件隨機到達、工件臨時取消以及多目標(biāo)求解等。

參考文獻/References：

［1］ DU Hangming，QIAO Fei，WANG Junkai，et al.A hybrid metaheuristic algorithm with novel decoding methods for flexible flow shop scheduling considering human fatigue［C］//2021 IEEE International Conference on Systems，Man，and Cybernetics （SMC）.Melbourne：IEEE，2021：2328-2333.

［2］ BALAS J. How You Could Pay the Price for Exhausted Employees［EB/OL］. https：//www.constructionbusinessowner.com/safety/how-you-could-pay-price-exhausted-employees， 2023-01-29.

［3］ JANSEN N W H，van AMELSVOORT L G P M，KRISTENSEN T S，et al.Work schedules and fatigue：a prospective cohort study［J］.Occupational and Environmental Medicine，2003，60（sup1）：47-53.

［4］ LI Kai，XU Shuling，F(xiàn)U Hong.Work-break scheduling with real-time fatigue effect and recovery［J］.International Journal of Production Research，2020，58（3）：689-702.

［5］ JAMSHIDI R，MAADI M.Maintenance and work-rest scheduling in human-machine system according to fatigue and reliability［J］.International Journal of Engineering（IJE），2017，30（1）：85-92.

［6］ BERTI N，ARTIGUES C，BATTAA O，et al.Heuristic approaches for scheduling manufacturing tasks while taking into account accumulated human fatigue［J］.IFAC-PapersOnLine，2019，52（13）：963-968.

［7］ MOUAYNI I E，DEMESURE G，HAOUZI H B E，et al.Jobs scheduling within Industry 4.0 with consideration of workers fatigue and reliability using Greedy Randomized Adaptive Search Procedure［J］.IFAC-PapersOnLine， 2019，52（19）：85-90.

［8］ FU Jiawei，MA Liang.Long-haul vehicle routing and scheduling with biomathematical fatigue constraints［J］. Transportation Science，2022，56（2）：404-435.

［9］ ZHANG Ming，LI Chunquan，SHANG Yuling，et al.Cycle time and human fatigue minimization for human-robot collaborative assembly cell［J］.IEEE Robotics and Automation Letters，2022，7（3）：6147-6154.

［10］WRIGHT T P.Factors affecting the cost of airplanes［J］.Journal of the Aeronautical Sciences，1936，3（4）：122-128.

［11］BISKUP D.A state-of-the-art review on scheduling with learning effects［J］.European Journal of Operational Research，2008，188（2）：315-329.

［12］JANIAK A，RUDEK R.Experience-based approach to scheduling problems with the learning effect［J］.IEEE Transactions on Systems，Man，and Cybernetics-Part A：Systems and Humans，2009，39（2）：344-357.

［13］WANG Jibo，WANG Jianjun.Scheduling jobs with a general learning effect model［J］.Applied Mathematical Modelling，2013，37（4）：2364-2373.

［14］成舒凡，葉春明.嵌入疲勞效應(yīng)和學(xué)習(xí)效應(yīng)的應(yīng)急手術(shù)調(diào)度研究［J］.計算機工程與應(yīng)用，2022，58（13）：295-302.

CHENG Shufan，YE Chunming.Study on emergency surgical scheduling with fatigue effect and learning effect［J］.Computer Engineering and Applications，2022，58（13）：295-302.

［15］楊舒涵，王吉波.帶指數(shù)學(xué)習(xí)效應(yīng)和凸資源分配的單機排序問題研究［J］.重慶師范大學(xué)學(xué)報（自然科學(xué)版），2022，39（5）：24-28.

YANG Shuhan，WANG Jibo.Study on single machine scheduling problems with exponential learning effects and convex resource allocation［J］.Journal of Chongqing Normal University （Natural Science），2022，39（5）：24-28.

［16］侯天天，張守京，杜昊天.考慮工人學(xué)習(xí)效應(yīng)的雙資源約束柔性車間調(diào)度［J］.組合機床與自動化加工技術(shù)，2022， 586（12）：164-168.

HOU Tiantian，ZHANG Shoujing，DU Haotian.Research on dual-resource constrained flexible job shop scheduling problem considering workers' learning effect［J］.Modular Machine Tool & Automatic Manufacturing Technique，2022，586（12）：164-168.

［17］de JONG J R.The effects of increasing skill on cycle time and its consequences for time standards［J］. Ergonomics，1957，1（1）：51-60.

［18］伍國華，毛妮，徐彬杰，等.基于自適應(yīng)大規(guī)模鄰域搜索算法的多車輛與多無人機協(xié)同配送方法［J］.控制與決策，2023，38（1）：201-210.

WU Guohua，MAO Ni，XU Binjie，et al.Research on the cooperative delivery of multiple vehicles and multiple drones based on adaptive large neighborhood search［J］.Control and Decision，2023，38（1）：201-210.

［19］徐倩，熊俊，楊珍花，等.基于自適應(yīng)大鄰域搜索算法的外賣配送車輛路徑優(yōu)化［J］.工業(yè)工程與管理，2021，26（3）：115-122.

XU Qian，XIONG Jun，YANG Zhenhua，et al.Route optimization of takeout delivery vehicles based on adaptive large neighborhood search algorithm［J］.Industrial Engineering and Management，2021，26（3）：115-122.

［20］MARA S T W，NORCAHYO R，JODIAWAN P，et al.A survey of adaptive large neighborhood search algorithms and applications［J］.Computers & Operations Research，2022，146.DOI：10.1016/j.cor.2022.105903.

［21］郭鵬，趙文超，雷坤.基于改進Jaya算法的雙資源約束柔性作業(yè)車間調(diào)度［J］.吉林大學(xué)學(xué)報（工學(xué)版），2023，53（2）：480-487.

GUO Peng，ZHAO Wenchao，LEI Kun.Dual-resource constrained flexible job shop optimal scheduling based on an improved Jaya algorithm［J］.Journal of Jilin University （Engineering and Technology Edition），2023，53（2）：480-487.