付 梅，史英超，申高攀，王蓀馨

（1.中國(guó)航發(fā)西安動(dòng)力控制科技有限公司，西安 710077；2.西北工業(yè)大學(xué) 機(jī)電學(xué)院，西安 710072；3.西安理工大學(xué) 機(jī)械與精密儀器學(xué)院，西安 710048）

0 引言

車間作為制造企業(yè)的效益源泉，它是整個(gè)企業(yè)物料流、控制流和信息流的匯集點(diǎn)。長(zhǎng)期以來(lái)，假設(shè)調(diào)度參數(shù)已知、忽略擾動(dòng)因素、尋求最優(yōu)解的確定性調(diào)度問題一直是生產(chǎn)調(diào)度領(lǐng)域的研究重點(diǎn)，這種具有剛性、靜態(tài)和理想的確定性調(diào)度優(yōu)化方案在隨機(jī)擾動(dòng)沖擊下其性能指標(biāo)將急劇劣化，而調(diào)度方案的頻繁變動(dòng)則會(huì)導(dǎo)致車間的毛料供應(yīng)、刀具/夾具/測(cè)具準(zhǔn)備、設(shè)備人員安排等生產(chǎn)準(zhǔn)備環(huán)節(jié)無(wú)所適從。

從辯證的觀點(diǎn)看：在人、機(jī)、料、法、環(huán)組成的復(fù)雜制造系統(tǒng)中，不確定性是絕對(duì)的，而確定性則是相對(duì)的。因此，充分考慮不確定因素的影響，事先預(yù)測(cè)與評(píng)估隨機(jī)擾動(dòng)因素對(duì)調(diào)度性能指標(biāo)的影響程度，并采取積極主動(dòng)的調(diào)度策略，有助于保持整個(gè)制造系統(tǒng)的穩(wěn)定性、有序性和高效性，同時(shí)避免由于頻繁重調(diào)度而導(dǎo)致車間現(xiàn)場(chǎng)生產(chǎn)組織陷于紊亂。因此，充分考慮不確定性因素，確保調(diào)度性能指標(biāo)在擾動(dòng)情況下仍能保持較優(yōu)性能，以避免由于頻繁重調(diào)度而導(dǎo)致車間現(xiàn)場(chǎng)生產(chǎn)組織陷于紊亂，保持整個(gè)制造系統(tǒng)的穩(wěn)定性、有序性和高效性，具有很強(qiáng)的理論研究意義和實(shí)用價(jià)值。

在眾多的車間隨機(jī)擾動(dòng)因素中，機(jī)器故障是車間生產(chǎn)過(guò)程中普遍存在、最具代表性的不確定因素。對(duì)于機(jī)器故障條件下的車間隨機(jī)調(diào)度問題，張國(guó)輝[1]等以最大完工時(shí)間、機(jī)器能耗和總延遲時(shí)間為目標(biāo)函數(shù)，采用改進(jìn)帝國(guó)競(jìng)爭(zhēng)算法解決機(jī)器故障重調(diào)度問題；文笑雨[2]等提出一種不確定擾動(dòng)下帶有緩沖區(qū)的作業(yè)車間調(diào)度方案，將仿真技術(shù)與智能優(yōu)化算法相結(jié)合處理生產(chǎn)車間系統(tǒng)中的擾動(dòng)性因素；靳彬鋒[3]等以最小化最大完成時(shí)間、最小成本和機(jī)器最大負(fù)荷為目標(biāo)函數(shù)，采用粒子群算法對(duì)機(jī)器故障發(fā)生后的未加工工序進(jìn)行重調(diào)度安排。然而，這些研究忽略了“穩(wěn)定性”這一重要指標(biāo)，在機(jī)器故障發(fā)生后對(duì)未加工工序進(jìn)行穩(wěn)定性重調(diào)度，有助于保持整個(gè)制造系統(tǒng)的穩(wěn)定性、有序性和高效性，避免車間現(xiàn)場(chǎng)生產(chǎn)組織陷于紊亂。辛悅[4]等采用離散改進(jìn)粒子群算法求解柔性作業(yè)車間不確定性調(diào)度問題，其調(diào)度方案具有較好的穩(wěn)定性；路光明[5]等針對(duì)柔性作業(yè)車間生產(chǎn)過(guò)程中存在的機(jī)器故障等問題，提出應(yīng)用多目標(biāo)遺傳算法進(jìn)行求解；劉秀鳳[6]等對(duì)機(jī)器故障下的作業(yè)車間魯棒調(diào)度問題進(jìn)行了研究，并采用遺傳算法對(duì)問題進(jìn)行求解。目前的穩(wěn)定性調(diào)度研究側(cè)重于調(diào)度優(yōu)化，算法復(fù)雜，車間實(shí)際使用較為困難。

本文研究用于機(jī)器故障條件下的作業(yè)車間穩(wěn)定性調(diào)度方法，首先提出了一種工序開工時(shí)間偏差穩(wěn)定性指標(biāo)并建立了問題的調(diào)度優(yōu)化模型，然后采用二進(jìn)制樹方法準(zhǔn)確提取機(jī)器故障發(fā)生后受影響工序集，在此基礎(chǔ)上設(shè)計(jì)了受影響工序重調(diào)度方法，最后通過(guò)析因?qū)嶒?yàn)驗(yàn)證了所提出的受影響工序重調(diào)度方法相較于右移重調(diào)度方法具有良好的實(shí)用性和可操作性。

1 機(jī)器故障條件下作業(yè)車間穩(wěn)定性調(diào)度模型

1.1 穩(wěn)定性指標(biāo)

調(diào)度中穩(wěn)定性指標(biāo)定義為：初始調(diào)度（Initial schedule）與實(shí)際調(diào)度（Realized schedule）之間的偏差，包括重調(diào)度前后調(diào)度方案性能指標(biāo)的偏差和工序開工時(shí)間的偏差等。機(jī)器故障會(huì)對(duì)車間的初始調(diào)度方案造成一定程度的破壞，通過(guò)穩(wěn)定性指標(biāo)來(lái)衡量重調(diào)度對(duì)初始調(diào)度方案的破壞程度。

一個(gè)具有較好穩(wěn)定性的調(diào)度方案，它的實(shí)際調(diào)度結(jié)果應(yīng)該盡可能與初始調(diào)度偏差最小。片面地追求調(diào)度性能指標(biāo)會(huì)導(dǎo)致車間生產(chǎn)秩序陷入混亂，現(xiàn)場(chǎng)生產(chǎn)人員“到處救火”，生產(chǎn)準(zhǔn)備無(wú)從下手。在保持機(jī)器上工件加工順序不變的前提下，盡可能減小重調(diào)度和初始調(diào)度方案的工序開工時(shí)間偏差，對(duì)既定的制造資源安排影響小，有利于整個(gè)車間的有序組織和生產(chǎn)，保證車間生產(chǎn)的穩(wěn)定性。因此，本文選擇工序開工時(shí)間的偏差作為穩(wěn)定性指標(biāo)。

在本文中，通過(guò)對(duì)重調(diào)度和初始調(diào)度的各個(gè)工序的開工時(shí)間之差的絕對(duì)值求和來(lái)得到工序開工時(shí)間偏差。工序開工時(shí)間偏差可計(jì)算如下：

其中，NSTi，j和STi，j分別表示任一工序Oi，j的重調(diào)度工序開工時(shí)間和初始調(diào)度工序開工時(shí)間。

1.2 穩(wěn)定性調(diào)度優(yōu)化模型

機(jī)器故障條件下作業(yè)車間穩(wěn)定性調(diào)度問題可以描述為：n個(gè)工件j={J1，J1，...，Jn}在m臺(tái)機(jī)器M={M1，M1，...，Mn}上加工，工件Ji的任一工序Oi，j只能在某一機(jī)器上加工一次，且機(jī)器同一時(shí)間只能加工一個(gè)工序，機(jī)器Mk加工某一工序時(shí)在t時(shí)刻發(fā)生故障，故障持續(xù)時(shí)間為r。對(duì)于任意工件Ji，其相關(guān)的調(diào)度參數(shù)為工序Oi，j加工時(shí)間Pi，j、工序Oi，j完工時(shí)間ETi，j、承制機(jī)器M(Oi，j)∈M。以工序開工時(shí)間偏差穩(wěn)定性指標(biāo)為調(diào)度目標(biāo)，則機(jī)器故障條件下作業(yè)車間穩(wěn)定性調(diào)度問題的調(diào)度優(yōu)化模型為：

其中：

式(2)為穩(wěn)定性調(diào)度目標(biāo)函數(shù)，即：機(jī)器故障發(fā)生后，在保持各機(jī)器上工件加工順序不變的前提下進(jìn)行重調(diào)度，使得所有工件的工序開工時(shí)間偏差最??；

式(3)為工藝路線約束，即同一工件Ji內(nèi)不同工序之間的時(shí)序關(guān)系約束；

式(4)為機(jī)器析取（能力）約束，即同一臺(tái)機(jī)器在同一時(shí)刻只能加工一個(gè)工序任務(wù)。

2 機(jī)器故障條件下作業(yè)車間穩(wěn)定性調(diào)度算法

2.1 穩(wěn)定性調(diào)度方法選擇

穩(wěn)定性調(diào)度方法主要有三種方式：完全重調(diào)度（Total Rescheduling，TR）、右移重調(diào)度[7]（Right Shift Rescheduling，RSR）和受影響工序重調(diào)度（Affected Operation Rescheduling，AOR）。其中，完全重調(diào)度方法不考慮初始調(diào)度方案，對(duì)全部工序進(jìn)行重調(diào)度安排，完全打亂生產(chǎn)秩序，導(dǎo)致車間生產(chǎn)秩序難以保持穩(wěn)定。因此，在應(yīng)對(duì)車間隨機(jī)機(jī)器故障時(shí)，主要以右移重調(diào)度和受影響工序重調(diào)度兩種調(diào)度方法為主。

當(dāng)機(jī)器故障發(fā)生時(shí)，右移重調(diào)度方法將當(dāng)前所有待加工工序向后延遲故障持續(xù)時(shí)間r，重新得到一個(gè)可行的調(diào)度方案。然而，該方法得到的調(diào)度方案無(wú)法有效利用車間加工資源，造成工件不必要地等待，甚至導(dǎo)致工件延遲交付。受影響工序重調(diào)度法只調(diào)度直接（或間接）受影響的工序，保留了初始調(diào)度的穩(wěn)定性的同時(shí)還可以兼顧資源的利用率。AOR是一種啟發(fā)式重調(diào)度方法，它可以盡量減少重調(diào)度中Makespan的增加量和工序開工時(shí)間偏差，生成的重調(diào)度既具有穩(wěn)定性也兼具效率。當(dāng)某一臺(tái)機(jī)器在加工工序任務(wù)時(shí)發(fā)生例外故障，且故障持續(xù)一段時(shí)間r，則AOR的解決思路是從最先受影響的工序開始調(diào)度，并將剩余工序中受影響的工序向右移動(dòng)適量時(shí)間段，而對(duì)不受影響的工序集則不做任何變動(dòng)，如圖1所示。AOR重調(diào)度方法減少了工序開工時(shí)間的延遲（工序開工時(shí)間偏差減小），同時(shí)盡可能地保留了初始調(diào)度方案的調(diào)度性能。

圖1 RSR和AOR二類重調(diào)度方法比較

2.2 基于二進(jìn)制樹的受影響工序集提取方法

AOR只對(duì)直接或者間接受影響的工序進(jìn)行重調(diào)度，前提是能夠分辨出當(dāng)前待加工工序中哪些是受影響的工序哪些是不受影響的工序，這里采用二進(jìn)制樹方法[8]準(zhǔn)確地完成這個(gè)復(fù)雜工作。

從工件工藝路線約束的角度去看，我們可以把相互聯(lián)系的工序看成一個(gè)二進(jìn)制樹或一個(gè)從根節(jié)點(diǎn)開始的樹圖表。二進(jìn)制樹連接各個(gè)工序節(jié)點(diǎn)而不包含節(jié)點(diǎn)循環(huán)，并且其每個(gè)節(jié)點(diǎn)最多發(fā)出兩個(gè)分支節(jié)點(diǎn)（如圖2所示）。如果選擇某個(gè)節(jié)點(diǎn)表示當(dāng)前工序，節(jié)點(diǎn)的左分支表示工件分支，表示根據(jù)工藝路線確定的工件的下一個(gè)工序（noj），節(jié)點(diǎn)的右分支表示機(jī)器分支，表示按生產(chǎn)調(diào)度確定的機(jī)器下一個(gè)要加工的工序（nom）。當(dāng)機(jī)器故障發(fā)生后，我們觀察第一個(gè)受影響的工序（當(dāng)機(jī)器發(fā)生故障時(shí)，正在加工的工序）完工時(shí)間的延誤是否影響到它的工件分支節(jié)點(diǎn)和機(jī)器分支節(jié)點(diǎn)。以此類推，把第一個(gè)受影響的工序作為根節(jié)點(diǎn)，沿著二進(jìn)制樹，研究其后的每個(gè)節(jié)點(diǎn)是否受到機(jī)器故障影響。

圖2 基于二進(jìn)制樹的受影響工序集提取方法

2.3 AOR重調(diào)度算法

AOR重調(diào)度算法包含兩個(gè)操作，即：受影響工序集提取和受影響工序右移。依據(jù)2.2節(jié)中提出的受影響工序集提取方法找出機(jī)器故障發(fā)生后的所有受影響工序集合Aff，然后依次對(duì)所有受影響工序進(jìn)行適當(dāng)右移，未受影響工序則保持初始調(diào)度方案中的開工時(shí)間安排?；诖耍疚脑O(shè)計(jì)了AOR重調(diào)度算法，相關(guān)的變量如表1所示。

表1 AOR重調(diào)度方法相關(guān)變量說(shuō)明

AOR重調(diào)度算法計(jì)算步驟如下：

Step1：初始化：i=1，g=1，devSt=0，Y=?，對(duì)機(jī)器故障發(fā)生時(shí)所有待加工工序有jobST=0，mcST=0。

Step2：提取受影響工序集合Aff：機(jī)器故障發(fā)生后，采用基于二進(jìn)制樹的受影響工序集提取方法獲取待加工工序集合中的受影響工序集合Aff。

Step3：更新當(dāng)前工序：機(jī)器故障發(fā)生時(shí)被中斷的工序設(shè)為當(dāng)前工序Odur，設(shè)潛在受影響工序Y[g]=Odur，mcSTdur設(shè)為機(jī)器故障修復(fù)后工件的開始加工時(shí)間，g++。

Step4：更新機(jī)器故障后Odur的開完工時(shí)間：NSTdur=max(jobSTdur，mcSTdur)，NSTdur=NSTdur+Pdur，Pdur為當(dāng)前工序的加工時(shí)間。

Step5：判斷工序Odur是否為受影響工序：對(duì)當(dāng)前工序Odur和集合Aff的工序進(jìn)行匹配，檢查當(dāng)前工序是否被影響兩次。若集合Aff中的任一工序Aff[v]都和當(dāng)前工序Odur不同，直接轉(zhuǎn)到Step6；否則比較NETdur和NETA f f[v]，若前者小，則跳到Step 9；否則，令devSt=devSt+(NETdur-NETAff[v])，NSTAff[v]=NSTdur；NETAff[v]=NSTAff[v]+pAff[v]；然后跳轉(zhuǎn)到Step7。

Step6：更新當(dāng)前工序：將重調(diào)度后的受影響工序Aff[i]設(shè)為當(dāng)前工序Odur，i++。

Step7：查找當(dāng)前工件的下一道工序noj：若noj存在，且其ST小于NETdur，令Y[g]=noj，jobSTnoj=NETdur，g++；否則，則不執(zhí)行任何操作。

Step8：查找當(dāng)前機(jī)器加工序列上的下一道工序nom：若nom存在，且其ST小于NETdur，令Y[g]=nom，mcSTnom=NETdur，g++；否則，則不執(zhí)行任何操作。

Step9：從潛在受影響工序集合中移除當(dāng)前工序：把當(dāng)前工序Odur從集合Y中移除。

Step10：判斷是否已全部完成重調(diào)度：若Y=?，則算法結(jié)束；否則，選擇集合Y的任意元素作為當(dāng)前工序Odur，并返回Step4。

3 穩(wěn)定性調(diào)度算法仿真驗(yàn)證

為驗(yàn)證本文構(gòu)建機(jī)器故障條件下作業(yè)車間穩(wěn)定性調(diào)度模型和AOR重調(diào)度算法的有效性，考慮機(jī)器故障的發(fā)生時(shí)刻早晚和持續(xù)時(shí)間長(zhǎng)短兩方面因素，與右移重調(diào)度（RSR）方法進(jìn)行比較，設(shè)計(jì)了一組2×2×2組合的析取實(shí)驗(yàn)進(jìn)行實(shí)驗(yàn)驗(yàn)證。

3.1 析因?qū)嶒?yàn)設(shè)計(jì)

表2中的每一類實(shí)驗(yàn)條件組合分別進(jìn)行5次隨機(jī)實(shí)驗(yàn)，故將得到40組數(shù)據(jù)。本文采用FT06作為穩(wěn)定性調(diào)度測(cè)試算例，圖3為算例的初始最優(yōu)調(diào)度方案。

圖3 FT06初始最優(yōu)調(diào)度方案

表2 析因?qū)嶒?yàn)組合設(shè)計(jì)

機(jī)器故障發(fā)生時(shí)刻（Downtime）：分為兩個(gè)等級(jí)：等級(jí)E（early）表示機(jī)器故障在較早時(shí)間發(fā)生，等級(jí)L（late）表示機(jī)器故障在較晚的時(shí)間發(fā)生。若M表示初始調(diào)度的Makespan，t表示機(jī)器故障發(fā)生時(shí)刻，則：E：t∈[0.05M，0.4M]，L：t∈[0.6M，0.9M]。

機(jī)器故障持續(xù)時(shí)間（Duration）：這個(gè)自變量表示機(jī)器故障的持續(xù)時(shí)間，它分為兩個(gè)等級(jí)。等級(jí)S（short）表示較短的故障時(shí)間，等級(jí)O（long）表示較長(zhǎng)的故障時(shí)間。如果M表示初始調(diào)度的Makespan，d表示故障持續(xù)時(shí)間，則：S：d∈[0.005M，0.035M]，O：d∈[0.04M，0.07M]。

兩類重調(diào)度方法（Method）：將上述兩種重調(diào)度方法分為兩個(gè)等級(jí)。R對(duì)應(yīng)右移重調(diào)度法（RSR），A對(duì)應(yīng)受影響工序重調(diào)度法（AOR）。

3.2 實(shí)驗(yàn)結(jié)果及分析

以上述圖3初始最優(yōu)調(diào)度方案作為實(shí)驗(yàn)輸入初始算例，然后采用3.1節(jié)所給出的實(shí)驗(yàn)條件參數(shù)和析因?qū)嶒?yàn)組合，分別采用對(duì)兩類重調(diào)度方法右移重調(diào)度法（RSR）和受影響工序重調(diào)度法（AOR）進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果參見表3。在表3中，第1、2列分別為機(jī)器故障發(fā)生時(shí)刻（Downtime）和機(jī)器故障持續(xù)時(shí)間（Duration）的不同組合，第3、4列是兩類重調(diào)度方法在不同實(shí)驗(yàn)組合條件下所獲得調(diào)度解對(duì)應(yīng)的devSt值（即所有工件工序開工時(shí)間偏差）。對(duì)同一組合條件下的5次重復(fù)實(shí)驗(yàn)結(jié)果取均值，得到各實(shí)驗(yàn)組合條件下兩種方法的devSt均值，如圖4所示。

圖4 各實(shí)驗(yàn)組合條件下兩種方法的devSt均值

表3 重調(diào)度析因?qū)嶒?yàn)結(jié)果

從表3和圖4可知三類實(shí)驗(yàn)條件（機(jī)器故障發(fā)生時(shí)刻、機(jī)器故障持續(xù)時(shí)間、重調(diào)度方法）都會(huì)對(duì)工序開工時(shí)間偏差（devSt）造成較大影響。從該實(shí)驗(yàn)結(jié)果可以得到以下結(jié)論：在其他實(shí)驗(yàn)條件相同的前提下，機(jī)器故障發(fā)生時(shí)間越早，重調(diào)度后得到的devSt越大；機(jī)器故障持續(xù)時(shí)間越長(zhǎng)，重調(diào)度后得到的devSt越大；AOR在各類情況下均可比RSR獲得的devSt指標(biāo)值更小。在最差工況（機(jī)器故障發(fā)生時(shí)間早、機(jī)器故障持續(xù)時(shí)間長(zhǎng)）條件下，AOR方法仍具有良好的穩(wěn)定性。

4 結(jié)語(yǔ)

針對(duì)機(jī)器故障這類作業(yè)車間最常見的隨機(jī)故障，以工序開工時(shí)間偏差作為穩(wěn)定性調(diào)度指標(biāo)構(gòu)建了調(diào)度優(yōu)化模型，從而為復(fù)雜作業(yè)車間的有序、穩(wěn)健生產(chǎn)提供了數(shù)學(xué)模型支持。

采用二進(jìn)制樹方法準(zhǔn)確提取受影響工序集，在此基礎(chǔ)上設(shè)計(jì)了一種簡(jiǎn)單實(shí)用的受影響工序穩(wěn)定性重調(diào)度方法。該方法在保持機(jī)器上工件加工順序不變的前提下，將受影響工序適當(dāng)右移，以盡可能減小工件的工序開工時(shí)間偏差，保證了車間現(xiàn)場(chǎng)生產(chǎn)秩序的穩(wěn)定性、有序性。

采用析因?qū)嶒?yàn)的方法，在三類實(shí)驗(yàn)條件（機(jī)器故障發(fā)生時(shí)刻，機(jī)器故障持續(xù)時(shí)間，重調(diào)度方法）組合下進(jìn)行了仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明受影響工序重調(diào)度方法相較于右移重調(diào)度方法可以顯著降低工序開工時(shí)間偏差，具有良好的實(shí)用性和可行性。