加工時間不確定的作業車間滾動窗口動態調度

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

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

1 引言

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

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

本文針對加工時間的不確定，提出加工時間偏差容忍度并設計滾動策略，建立作業車間的調度模型，改進蟻群算法的狀態轉移規則求解計算。經實驗仿真，獲得所需的滾動調度策略參數，實驗結果顯示算法的計算時間較短，計算所得結果質量較優。

2 問題描述與模型建立

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

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

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

情景s∈S下的最優調度所對應的加工成本用表示：

定義1調度X的最大遺憾值為：

要使得最壞情景最好，即最大遺憾值最小：

將上述數學模型轉換成混合整數線性模型：

由假設Ⅱ可知，需滿足：

根據假設Ⅲ，需滿足以下關系：

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

3 滾動調度策略

3.1 加工時間偏差容忍度

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

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

3.2 自動觸發滾動調度策略

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

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

其中，ΔT代表時間窗口長度，ΔTp代表預測窗口長度，w(l)表示預測窗口，Ps(l)表示完工窗口，Fs(l)表示等待窗口。

4 改進蟻群算法的狀態轉移規則

編號為k的螞蟻，假設它現在處于節點r，下一步將會轉移，在眾多的節點中，節點s被選中的概率為：

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

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

5 實驗仿真分析

5.1 參數設定

5.2 動態調度參數試驗

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

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

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

表2 窗口步長不同的重調度結果對比Tab.2 Comparison of Rescheduling Results with Different Size Rolling Windows

5.3 動態調度策略可行性分析

采用回歸分析的方法，確定重調度時刻與調度目標最大遺憾值之間的相關關系。擬采用多項式回歸模型，假設如下：

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

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

求解并整理可得：

在進行了50次仿真后得到一些點值，采用散點作圖得到回歸曲線，如圖2所示。根據最小二乘法由式（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

分析總結，當加工時間的偏差發生預調度前期，一般不啟動重調度，因為在后續生產過程中的時間緩沖可將其吸收；如果發生在后期，也多維持原調度，這時任務大多已經完成加工，預調度魯棒性能也已發揮，此時調整得不償失。

5.4 動態調度算法性能試驗

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

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

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

6 結論

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