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

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

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

1 引言

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

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

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

2 問題描述與模型建立

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

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

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

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

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

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

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

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

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

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

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

3.1 加工時(shí)間偏差容忍度

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

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

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

圖1 以時(shí)間為窗口的滾動(dòng)過程圖Fig.1 Diagram of Rolling Horizon Time-based Windows

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

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

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

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

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

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

5 實(shí)驗(yàn)仿真分析

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

5.2 動(dòng)態(tài)調(diào)度參數(shù)試驗(yàn)

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

表1 不同加工時(shí)長(zhǎng)偏差容忍度試驗(yàn)結(jié)果Tab.1 Comparison of Different LDT Scheduling Results

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

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

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

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

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

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

求解并整理可得：

在進(jìn)行了50次仿真后得到一些點(diǎn)值，采用散點(diǎn)作圖得到回歸曲線，如圖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)加工時(shí)間的偏差發(fā)生預(yù)調(diào)度前期，一般不啟動(dòng)重調(diào)度，因?yàn)樵诤罄m(xù)生產(chǎn)過程中的時(shí)間緩沖可將其吸收；如果發(fā)生在后期，也多維持原調(diào)度，這時(shí)任務(wù)大多已經(jīng)完成加工，預(yù)調(diào)度魯棒性能也已發(fā)揮，此時(shí)調(diào)整得不償失。

5.4 動(dòng)態(tài)調(diào)度算法性能試驗(yàn)

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

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

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

6 結(jié)論

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