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

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

1 引言

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

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

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

2 問題描述與模型建立

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

符號定義：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可以對工序類別j進(jìn)行操作則=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 加工時(shí)間偏差容忍度

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

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

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

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

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

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

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

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

式中：Nu—螞蟻數(shù)量，N—截止目前的迭代次數(shù)，經(jīng)過路徑(i,j)的螞蟻不止一個(gè)，其數(shù)量用mij表示。信息素在算法局部趨于最優(yōu)時(shí)會不斷增加，同時(shí)x會隨路徑上螞蟻的增多而減少，使得狀態(tài)轉(zhuǎn)移概率因信息素增長受到的影響得到抑制，進(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 動態(tài)調(diào)度參數(shù)試驗(yàn)

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

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

將事件驅(qū)動應(yīng)用在緊急工件到達(dá)的情況下，其余使用周期驅(qū)動。針對同一規(guī)模的算例，分別設(shè)置不同的步長進(jìn)行試驗(yàn)，如表2所示：當(dāng)ΔT=90～100，滾動次數(shù)為4～5次時(shí)，可取得全局最優(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)度時(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)度前期，一般不啟動重調(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 動態(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表示被采用的資源組合的編號。為有效評價(jià)算法的性能以平均計(jì)算時(shí)間Tavg、目標(biāo)函數(shù)值Z(X)作為算法評價(jià)指標(biāo)。

如表3所示：分析可知對于不同規(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ì)量會隨著可以利用資源組合數(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é)果對比Tab.3 Comparisons of the Results of Different Scales Examples

6 結(jié)論

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