郭超 郝東輝 郭鵬

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

關(guān)鍵詞：計(jì)算機(jī)輔助制造；作業(yè)車間調(diào)度； 工人疲勞；學(xué)習(xí)效應(yīng)；自適應(yīng)大鄰域搜索；動(dò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

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

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

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

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

1 問(wèn)題描述與模型建立

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

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

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

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

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

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

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

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

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

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

1.2 問(wèn)題描述

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

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

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

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

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

4）每個(gè)工件都需要被加工1次。

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

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

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

8）所有工人和所有機(jī)器的初始開始時(shí)刻為零時(shí)刻。

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

10）工件的實(shí)際加工時(shí)間由工人、機(jī)器和加工順序共同決定。

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

1.3 模型建立

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

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

minC_max。 ????（5）

約束為

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

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

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

2.1 編碼與解碼

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

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

2.2 初始解生成

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

2.3 操作算子

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

2.3.1 破壞算子

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

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

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

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

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

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

2.3.2 修復(fù)算子

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

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

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

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

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

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

2.4 接受準(zhǔn)則

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

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

2.5 改進(jìn)ALNS算法流程

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

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

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

3.1 算例生成

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

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

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

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

3.3 結(jié)果與對(duì)比

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 緊急插單場(chǎng)景

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

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

4.2 機(jī)器故障場(chǎng)景

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

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

4.3 工人離崗場(chǎng)景

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

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

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

5 結(jié) 語(yǔ)

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

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

參考文獻(xiàn)/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］.計(jì)算機(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ī)排序問(wèn)題研究［J］.重慶師范大學(xué)學(xué)報(bào)（自然科學(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］.組合機(jī)床與自動(dòng)化加工技術(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］伍國(guó)華，毛妮，徐彬杰，等.基于自適應(yīng)大規(guī)模鄰域搜索算法的多車輛與多無(wú)人機(jī)協(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］郭鵬，趙文超，雷坤.基于改進(jìn)Jaya算法的雙資源約束柔性作業(yè)車間調(diào)度［J］.吉林大學(xué)學(xué)報(bào)（工學(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.