加工時間不確定的作業(yè)車間滾動窗口動態(tài)調(diào)度

楊培培，李 明，袁逸萍，李曉娟

（新疆大學(xué)機械工程學(xué)院，新疆 烏魯木齊830047）

1 引言

在確定性環(huán)境中建立的模型用于實際作業(yè)車間生產(chǎn)中時，由于不確定因素存在會直接或間接受到影響，這種影響最終體現(xiàn)在加工時間波動上［1］。動態(tài)調(diào)度對于加工時間波動多是采用概率論、模糊方法等，處理結(jié)果得到的是經(jīng)驗預(yù)估值，與實時數(shù)值有著較大差距，由此制定的重調(diào)度策略便不具備其應(yīng)有之義［5］［9］。鑒于此，選擇將不確定的加工時間作為車間動態(tài)調(diào)度問題的切入點，具有重要的理論價值和現(xiàn)實意義。

文獻［2］將加工時間用區(qū)間數(shù)表示，對作業(yè)車間進行單目標(biāo)建模并改進交叉策略求解，結(jié)果證明此方法可獲得較優(yōu)全局解。文獻［3］緊扣關(guān)鍵工序集，設(shè)計相應(yīng)遺傳算法，結(jié)合滾動時域?qū)ο鄳?yīng)部分重調(diào)度。楊宏安［4］創(chuàng)新采用區(qū)間數(shù)對提前和拖期區(qū)間加以預(yù)測，確定待加工工序的開始加工時間。文獻［6］選取三種擾動事件，采用事件驅(qū)動，實驗驗證結(jié)合滾動窗口建立動態(tài)模型的可行性和改進模擬退火遺傳算法的有效性。文獻［7］混合了滾動策略和布谷鳥算法解決生產(chǎn)車間混流實施的預(yù)-反應(yīng)式調(diào)度問題。文獻［8］根據(jù)劃分的擾動類別在混合驅(qū)動重調(diào)度策略上結(jié)合預(yù)測控制，采用并行粒子群算法求解驗證。文獻［10］以柔性作業(yè)車間為研究對象，設(shè)計相應(yīng)遺傳算法，并予以驗證。

本文針對加工時間的不確定，提出加工時間偏差容忍度并設(shè)計滾動策略，建立作業(yè)車間的調(diào)度模型，改進蟻群算法的狀態(tài)轉(zhuǎn)移規(guī)則求解計算。經(jīng)實驗仿真，獲得所需的滾動調(diào)度策略參數(shù)，實驗結(jié)果顯示算法的計算時間較短，計算所得結(jié)果質(zhì)量較優(yōu)。

2 問題描述與模型建立

首先對作業(yè)車間作如下假設(shè)：Ⅰ預(yù)調(diào)度加工時間在排程中受擾動影響而波動；Ⅱ工件按需選取可用資源組合，符合所選資源數(shù)量限制；Ⅲ同一資源組合同一時間只能由同一進程使用；Ⅳ工件的加工過程持續(xù)不發(fā)生中斷；Ⅴ緊急工件插入擁有最高的優(yōu)先級。

符號定義：I為待分配的工件集合；C為單位時間成本；J為工序類別集合，j∈J；R為資源組合的集合，r∈R，rn為資源組合r中的第n類資源集合，n∈N，N為工件所需的資源種類；為工件i在資源組合r的作用下，需要第c類資源的數(shù)量，K為資源組合r可以操作的工件數(shù)量；為工件i使用資源組合r，倒數(shù)第k個位置開始加工的所需時間。

為在s情景下的加工時間，為所有可能的情景；Ω為所有的可行調(diào)度集合，X∈Ω。決策變量：工件i屬于工序類別j則=1，否則=0；資源組合r可以對工序類別j進行操作則=1，否則=0。對于X∈Ω在情景s∈S下的加工成本：

情景s∈S下的最優(yōu)調(diào)度所對應(yīng)的加工成本用表示：

定義1調(diào)度X的最大遺憾值為：

要使得最壞情景最好，即最大遺憾值最?。?/p>

將上述數(shù)學(xué)模型轉(zhuǎn)換成混合整數(shù)線性模型：

由假設(shè)Ⅱ可知，需滿足：

根據(jù)假設(shè)Ⅲ，需滿足以下關(guān)系：

為確保工件和資源組合的匹配性，需遵從以下不等式：

3 滾動調(diào)度策略

3.1 加工時間偏差容忍度

不同調(diào)度方案總加工時間不相同，不同調(diào)度方案對加工時間偏離的穩(wěn)定能力不同，因此提出加工時間偏差容忍度的概念，對加工時間波動進行定量化控制，表達式為：

式中：max()、max(Ti)—計劃完工時間和實際完工時間。根據(jù)計算得到δmax，將工件加工時間偏差率與偏差容忍度作比較，大于偏差容忍度時才開啟重調(diào)度。

3.2 自動觸發(fā)滾動調(diào)度策略

圖1 以時間為窗口的滾動過程圖Fig.1 Diagram of Rolling Horizon Time-based Windows

當(dāng)超過加工時間偏差容忍度時需要進行重調(diào)度，將已加工完成工件從滾動窗口移除，與此同時，選取數(shù)量適宜的待加工工件，進入其中。重調(diào)度的啟動不影響當(dāng)前時刻的車間進程。不斷進行滾動，直到車間任務(wù)全部完工。

其中，ΔT代表時間窗口長度，ΔTp代表預(yù)測窗口長度，w(l)表示預(yù)測窗口，Ps(l)表示完工窗口，F(xiàn)s(l)表示等待窗口。

4 改進蟻群算法的狀態(tài)轉(zhuǎn)移規(guī)則

編號為k的螞蟻，假設(shè)它現(xiàn)在處于節(jié)點r，下一步將會轉(zhuǎn)移，在眾多的節(jié)點中，節(jié)點s被選中的概率為：

式中：Nu—螞蟻數(shù)量，N—截止目前的迭代次數(shù)，經(jīng)過路徑(i,j)的螞蟻不止一個，其數(shù)量用mij表示。信息素在算法局部趨于最優(yōu)時會不斷增加，同時x會隨路徑上螞蟻的增多而減少，使得狀態(tài)轉(zhuǎn)移概率因信息素增長受到的影響得到抑制，進而提高算法全局搜索能力。由mij≤NuN，ηij/max(ηij)≤1得到1≥xij≥xmin=1/( 1+δ)。x強度大小用δ加以控制，xmin隨δ減小而增大，螞蟻爬經(jīng)路徑數(shù)在狀態(tài)轉(zhuǎn)移規(guī)則中的權(quán)值也隨之減小。節(jié)點r到節(jié)點s的信息素；—節(jié)點r到節(jié)點s的可見度；選用字母α—信息素，β—可見度偏重系數(shù)，分別體現(xiàn)著和在轉(zhuǎn)移概率中的重要程度。由公式（13）計算可見度：

式中：工件進入加工窗口前需要等待，時間用twait表示。在算法實現(xiàn)時取b=2。計算后，重新選擇一個節(jié)點，使用輪盤賭隨機從待加工工件集選取，記錄下節(jié)點的起始時間，進而計算等待加工時間和加工完成的時間。

5 實驗仿真分析

5.1 參數(shù)設(shè)定

5.2 動態(tài)調(diào)度參數(shù)試驗

偏差容忍度值和最佳窗口步長無法依據(jù)專家經(jīng)驗等獲取，且目前無法根據(jù)作業(yè)車間生產(chǎn)實際案例采集實時生產(chǎn)數(shù)據(jù)，故用4階愛爾朗分布方法予以模擬。對相同規(guī)模的同一個算例，分別進行10次實驗，{I,J,C,R}分別取值{3 0,350,2,4}，變量設(shè)為10個偏差容忍值。記錄下最大完工時間，滾動次數(shù)，目標(biāo)函數(shù)值以及資源利用率。得到對比結(jié)果如表1所示：當(dāng)大于0.25后，自始至終都沒有啟動重調(diào)度，顯然此種情形車間無法應(yīng)對擾動，當(dāng)取值降低兩個量級，滾動次數(shù)急速增大，即局部重調(diào)度頻繁地進行，不但浪費資源，多數(shù)情況下還會擾亂整個生產(chǎn)進程。分析可知，在滿足最大完工時間最小前提下，取值為0.1時，滾動次數(shù)較少的同時滿足調(diào)度要求。

表1 不同加工時長偏差容忍度試驗結(jié)果Tab.1 Comparison of Different LDT Scheduling Results

將事件驅(qū)動應(yīng)用在緊急工件到達的情況下，其余使用周期驅(qū)動。針對同一規(guī)模的算例，分別設(shè)置不同的步長進行試驗，如表2所示：當(dāng)ΔT=90～100，滾動次數(shù)為4～5次時，可取得全局最優(yōu)得調(diào)度方案。

表2 窗口步長不同的重調(diào)度結(jié)果對比Tab.2 Comparison of Rescheduling Results with Different Size Rolling Windows

5.3 動態(tài)調(diào)度策略可行性分析

采用回歸分析的方法，確定重調(diào)度時刻與調(diào)度目標(biāo)最大遺憾值之間的相關(guān)關(guān)系。擬采用多項式回歸模型，假設(shè)如下：

式中：xt—重調(diào)度的時刻，yt—最大遺憾值，且β1＞0，β2＞0，…，βk＞0。令多元一次線性方程為：

由最小二乘法原理可知，回歸曲線就是當(dāng)殘差平方和εt～N(0,σ2)達到最小的曲線，令…-bkxtk)2，要使sse最小，則有：

求解并整理可得：

在進行了50次仿真后得到一些點值，采用散點作圖得到回歸曲線，如圖2所示。根據(jù)最小二乘法由式（17）、（18）求得α1=715.3，β1=-1.535，β2=0.003026，回 歸 方 程 為yt=715.3-1.535xt+0.003026。

圖2 最大遺憾值的回歸曲線Fig.2 Maximum Regret Value Regression Curve

分析總結(jié)，當(dāng)加工時間的偏差發(fā)生預(yù)調(diào)度前期，一般不啟動重調(diào)度，因為在后續(xù)生產(chǎn)過程中的時間緩沖可將其吸收；如果發(fā)生在后期，也多維持原調(diào)度，這時任務(wù)大多已經(jīng)完成加工，預(yù)調(diào)度魯棒性能也已發(fā)揮，此時調(diào)整得不償失。

5.4 動態(tài)調(diào)度算法性能試驗

將基本蟻群算法（Ant colony optimization，ACO）、標(biāo)準(zhǔn)遺傳算法(GA)與設(shè)計的改進的蟻群算法（Improved ant colony optimization，IACO）分別進行驗證。GA采用實數(shù)編碼，種群大小為100，個體為a維的向量，其中a為工件數(shù)量，每個基因表示工件i，i=1,2,···，I表示被采用的資源組合的編號。為有效評價算法的性能以平均計算時間Tavg、目標(biāo)函數(shù)值Z(X)作為算法評價指標(biāo)。

如表3所示：分析可知對于不同規(guī)模算例，GA計算效率高于ACO，而ACO解的質(zhì)量高于GA。IACO比ACO求得的解的質(zhì)量更高，求解速度也更快；當(dāng)I，J，R相同時，Z()X隨C的增大而增大；當(dāng)I，J，R相同時，Z()X隨R的增大而減小，可見解的質(zhì)量會隨著可以利用資源組合數(shù)量增加而改善；當(dāng)I，C，R不變而J增大時，目標(biāo)函數(shù)值變大；當(dāng)J，R和C相同時，目標(biāo)函數(shù)值隨I的增大而增大，而解的質(zhì)量變差是由于問題規(guī)模的增大。

表3 規(guī)模不同的算例問題結(jié)果對比Tab.3 Comparisons of the Results of Different Scales Examples

6 結(jié)論

針對加工時間不確定的作業(yè)車間動態(tài)調(diào)度問題，提出一種基于滾動技術(shù)的混合驅(qū)動重調(diào)度策略。只有緊急工件到達時，采用事件驅(qū)動機制。提出加工時間偏差容忍度來過濾掉不必要的重調(diào)度。改進狀態(tài)轉(zhuǎn)移規(guī)則，提高螞蟻算法全局收斂性能。通過實驗仿真，對滾動調(diào)度策略參數(shù)進行分析并對動態(tài)調(diào)度算法性能進行比較驗證，得出較優(yōu)參數(shù)并驗證了算法在計算時間和計算結(jié)果上均較優(yōu)。