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

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

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

0 引言

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

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

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

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

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

1.1 穩(wěn)定性指標

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

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

在本文中，通過對重調(diào)度和初始調(diào)度的各個工序的開工時間之差的絕對值求和來得到工序開工時間偏差。工序開工時間偏差可計算如下：

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

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

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

其中：

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

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

式(4)為機器析取（能力）約束，即同一臺機器在同一時刻只能加工一個工序任務。

2 機器故障條件下作業(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)度方案，對全部工序進行重調(diào)度安排，完全打亂生產(chǎn)秩序，導致車間生產(chǎn)秩序難以保持穩(wěn)定。因此，在應對車間隨機機器故障時，主要以右移重調(diào)度和受影響工序重調(diào)度兩種調(diào)度方法為主。

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

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

2.2 基于二進制樹的受影響工序集提取方法

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

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

圖2 基于二進制樹的受影響工序集提取方法

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

AOR重調(diào)度算法包含兩個操作，即：受影響工序集提取和受影響工序右移。依據(jù)2.2節(jié)中提出的受影響工序集提取方法找出機器故障發(fā)生后的所有受影響工序集合Aff，然后依次對所有受影響工序進行適當右移，未受影響工序則保持初始調(diào)度方案中的開工時間安排。基于此，本文設計了AOR重調(diào)度算法，相關(guān)的變量如表1所示。

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

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

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

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

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

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

Step5：判斷工序Odur是否為受影響工序：對當前工序Odur和集合Aff的工序進行匹配，檢查當前工序是否被影響兩次。若集合Aff中的任一工序Aff[v]都和當前工序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：更新當前工序：將重調(diào)度后的受影響工序Aff[i]設為當前工序Odur，i++。

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

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

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

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

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

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

3.1 析因?qū)嶒炘O計

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

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

表2 析因?qū)嶒灲M合設計

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

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

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

3.2 實驗結(jié)果及分析

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

圖4 各實驗組合條件下兩種方法的devSt均值

表3 重調(diào)度析因?qū)嶒灲Y(jié)果

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

4 結(jié)語

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

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

采用析因?qū)嶒灥姆椒ǎ谌悓嶒灄l件（機器故障發(fā)生時刻，機器故障持續(xù)時間，重調(diào)度方法）組合下進行了仿真實驗，實驗結(jié)果表明受影響工序重調(diào)度方法相較于右移重調(diào)度方法可以顯著降低工序開工時間偏差，具有良好的實用性和可行性。