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

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

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

0 引言

車(chē)間作為制造企業(yè)的效益源泉，它是整個(gè)企業(yè)物料流、控制流和信息流的匯集點(diǎn)。長(zhǎng)期以來(lái)，假設(shè)調(diào)度參數(shù)已知、忽略擾動(dòng)因素、尋求最優(yōu)解的確定性調(diào)度問(wèn)題一直是生產(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)致車(chē)間的毛料供應(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)致車(chē)間現(xiàn)場(chǎng)生產(chǎn)組織陷于紊亂。因此，充分考慮不確定性因素，確保調(diào)度性能指標(biāo)在擾動(dòng)情況下仍能保持較優(yōu)性能，以避免由于頻繁重調(diào)度而導(dǎo)致車(chē)間現(xiàn)場(chǎng)生產(chǎn)組織陷于紊亂，保持整個(gè)制造系統(tǒng)的穩(wěn)定性、有序性和高效性，具有很強(qiáng)的理論研究意義和實(shí)用價(jià)值。

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

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

1 機(jī)器故障條件下作業(yè)車(chē)間穩(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)的偏差和工序開(kāi)工時(shí)間的偏差等。機(jī)器故障會(huì)對(duì)車(chē)間的初始調(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ē)間生產(chǎn)秩序陷入混亂，現(xiàn)場(chǎng)生產(chǎn)人員“到處救火”，生產(chǎn)準(zhǔn)備無(wú)從下手。在保持機(jī)器上工件加工順序不變的前提下，盡可能減小重調(diào)度和初始調(diào)度方案的工序開(kāi)工時(shí)間偏差，對(duì)既定的制造資源安排影響小，有利于整個(gè)車(chē)間的有序組織和生產(chǎn)，保證車(chē)間生產(chǎn)的穩(wěn)定性。因此，本文選擇工序開(kāi)工時(shí)間的偏差作為穩(wěn)定性指標(biāo)。

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

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

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

機(jī)器故障條件下作業(yè)車(chē)間穩(wěn)定性調(diào)度問(wèn)題可以描述為：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。以工序開(kāi)工時(shí)間偏差穩(wěn)定性指標(biāo)為調(diào)度目標(biāo)，則機(jī)器故障條件下作業(yè)車(chē)間穩(wěn)定性調(diào)度問(wèn)題的調(diào)度優(yōu)化模型為：

其中：

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

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

式(4)為機(jī)器析?。芰Γ┘s束，即同一臺(tái)機(jī)器在同一時(shí)刻只能加工一個(gè)工序任務(wù)。

2 機(jī)器故障條件下作業(yè)車(chē)間穩(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ē)間生產(chǎn)秩序難以保持穩(wěn)定。因此，在應(yīng)對(duì)車(chē)間隨機(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ú)法有效利用車(chē)間加工資源，造成工件不必要地等待，甚至導(dǎo)致工件延遲交付。受影響工序重調(diào)度法只調(diào)度直接（或間接）受影響的工序，保留了初始調(diào)度的穩(wěn)定性的同時(shí)還可以兼顧資源的利用率。AOR是一種啟發(fā)式重調(diào)度方法，它可以盡量減少重調(diào)度中Makespan的增加量和工序開(kāi)工時(shí)間偏差，生成的重調(diào)度既具有穩(wěn)定性也兼具效率。當(dāng)某一臺(tái)機(jī)器在加工工序任務(wù)時(shí)發(fā)生例外故障，且故障持續(xù)一段時(shí)間r，則AOR的解決思路是從最先受影響的工序開(kāi)始調(diào)度，并將剩余工序中受影響的工序向右移動(dòng)適量時(shí)間段，而對(duì)不受影響的工序集則不做任何變動(dòng)，如圖1所示。AOR重調(diào)度方法減少了工序開(kāi)工時(shí)間的延遲（工序開(kāi)工時(shí)間偏差減?。瑫r(shí)盡可能地保留了初始調(diào)度方案的調(diào)度性能。

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

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

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

從工件工藝路線約束的角度去看，我們可以把相互聯(lián)系的工序看成一個(gè)二進(jìn)制樹(shù)或一個(gè)從根節(jié)點(diǎn)開(kāi)始的樹(shù)圖表。二進(jìn)制樹(shù)連接各個(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)。以此類(lèi)推，把第一個(gè)受影響的工序作為根節(jié)點(diǎn)，沿著二進(jìn)制樹(shù)，研究其后的每個(gè)節(jié)點(diǎn)是否受到機(jī)器故障影響。

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

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

AOR重調(diào)度算法包含兩個(gè)操作，即：受影響工序集提取和受影響工序右移。依據(jù)2.2節(jié)中提出的受影響工序集提取方法找出機(jī)器故障發(fā)生后的所有受影響工序集合Aff，然后依次對(duì)所有受影響工序進(jìn)行適當(dāng)右移，未受影響工序則保持初始調(diào)度方案中的開(kāi)工時(shí)間安排?；诖?，本文設(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)制樹(shù)的受影響工序集提取方法獲取待加工工序集合中的受影響工序集合Aff。

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

Step4：更新機(jī)器故障后Odur的開(kāi)完工時(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è)車(chē)間穩(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中的每一類(lèi)實(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]。

兩類(lèi)重調(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ì)兩類(lèi)重調(diào)度方法右移重調(diào)度法（RSR）和受影響工序重調(diào)度法（AOR）進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果參見(jiàn)表3。在表3中，第1、2列分別為機(jī)器故障發(fā)生時(shí)刻（Downtime）和機(jī)器故障持續(xù)時(shí)間（Duration）的不同組合，第3、4列是兩類(lèi)重調(diào)度方法在不同實(shí)驗(yàn)組合條件下所獲得調(diào)度解對(duì)應(yīng)的devSt值（即所有工件工序開(kāi)工時(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可知三類(lèi)實(shí)驗(yàn)條件（機(jī)器故障發(fā)生時(shí)刻、機(jī)器故障持續(xù)時(shí)間、重調(diào)度方法）都會(huì)對(duì)工序開(kāi)工時(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在各類(lèi)情況下均可比RSR獲得的devSt指標(biāo)值更小。在最差工況（機(jī)器故障發(fā)生時(shí)間早、機(jī)器故障持續(xù)時(shí)間長(zhǎng)）條件下，AOR方法仍具有良好的穩(wěn)定性。

4 結(jié)語(yǔ)

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

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

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