訂單陸續(xù)到達下虛擬單元重調(diào)度驅動決策

韓文民，朱 弢，李正義，翁紅兵，蔣家尚

(1.江蘇科技大學經(jīng)濟管理學院，江蘇 鎮(zhèn)江 212003；2.滬東中華造船集團有限公司，上海 200129；3.江蘇科技大學數(shù)理學院，江蘇 鎮(zhèn)江 212003)

1 引言

虛擬單元制造系統(tǒng)(下文簡稱虛擬單元)是單元生產(chǎn)方式新的發(fā)展，是一種先進的生產(chǎn)組織形式。虛擬單元不需要對設備的物理位置進行重新安排，在邏輯上對資源進行聚類成組形成單元，大大減少了設備的移動成本和調(diào)整時間[1]。虛擬單元結合了單元式布局和工藝化布局的優(yōu)點，能夠充分挖掘制造系統(tǒng)中設備資源的能力，可以很好地適應當前多品種小批量的生產(chǎn)要求[2]。虛擬單元可以更為靈活地進行調(diào)整和變動，但同時必然會為其調(diào)度過程增加復雜度。

制造業(yè)環(huán)境復雜多變，存在著大量不確定的因素，各種類型的干擾事件隨時會出現(xiàn)，如工件優(yōu)先級變動[3]、機器故障[4]等。為了對出現(xiàn)的擾動作出響應，以適應當前的生產(chǎn)狀態(tài)，需要對原有的生產(chǎn)調(diào)度計劃進行重新調(diào)整。

先前的學者已經(jīng)對單機、平行機、流水車間、加工車間等不同生產(chǎn)制造方式下的重調(diào)度問題進行了大量的研究。劉樂[5]研究了一批新工件到達干擾條件下的單機重調(diào)度，在保證最小化最大延遲時間的同時，限制了干擾對初始最優(yōu)排序工件序位的影響量。Yin Yunqiang等[6]面對平行機發(fā)生機器加工中斷，在不過多破壞原調(diào)度的基礎上，提出了解決受影響工件的重調(diào)度模型，并分析了模型求解算法。Wang Kai等[7]提出了一個新的兩階段仿真模型，用于評估加工時間不確定的混合流水車間重調(diào)度候選方案的性能。薄洪光等[8]分析了在工件變更擾動情況下如何運用干擾管理理論來應對，解決了原調(diào)度受干擾事件影響而出現(xiàn)與實際偏離的問題。Lu等[9]分析了制造車間重調(diào)度過程中不同分派規(guī)則的效率與性能。Elnaz等[10]建立了動態(tài)環(huán)境下的虛擬單元調(diào)度數(shù)學模型，綜合考慮了需求變化、機器加工能力以及人員分配等多個因素。

目前國內(nèi)外關于重調(diào)度問題的研究，主要集中在重調(diào)度方法的優(yōu)化和重調(diào)度性能的評價這兩個方面[11]。大多數(shù)研究的重點是在確定觸發(fā)重調(diào)度的前提下，通過調(diào)度模型的優(yōu)化與算法的改進，使重調(diào)度方案具有更好的性能，且更符合生產(chǎn)實際情況。而針對重調(diào)度的驅動決策，即是否需要進行重調(diào)度以及何時進行重調(diào)度的問題，給予的關注相對較少。

Adibi等[12]在研究柔性流水作業(yè)動態(tài)調(diào)度問題時，將新工件到達以及機器故障選取為進行重調(diào)度的時刻。Wortmann[13]根據(jù)基于事件的驅動方式，通過評估重調(diào)度的可行性，以選擇合適的重調(diào)度方法。張潔等[14]考慮到了工件在生產(chǎn)會發(fā)生加工工時偏差的問題，設計了基于交貨期偏差容忍度的混合流水車間滾動調(diào)度策略。汪雙喜等[15]采用周期性再調(diào)度的方式，以應對柔性作業(yè)車間中工件隨機到達的情況，并對周期驅動中不同長度的調(diào)度周期對生產(chǎn)的影響進行了研究。Qiao Fei等[16]面向半導體生產(chǎn)線的不確定性問題，建立了一種重調(diào)度模糊PETRI網(wǎng)推理模型。劉明周等[17]針對制造車間機器故障和工件加工時間延長，基于損益云模型判斷選擇合適的重調(diào)度策略。Iraj[18]等根據(jù)虛擬單元生產(chǎn)系統(tǒng)中產(chǎn)品組合與部件需求變化，將生產(chǎn)計劃分為多個階段，基于模糊目標規(guī)劃方法，建立了多周期調(diào)度模型。

現(xiàn)有研究中，常用的重調(diào)度驅動有周期性驅動、事件型驅動以及混合驅動。對重調(diào)度驅動的分析與討論，大多是針對特定干擾事件進行驅動方法的應用，對重調(diào)度驅動方法本身進行改善的較少。同時，現(xiàn)有的重調(diào)度驅動也存在對生產(chǎn)系統(tǒng)產(chǎn)生負面影響之處。周期驅動應對突發(fā)事件干擾能力不強[15]；事件驅動會對系統(tǒng)穩(wěn)定性造成較大程度的影響[14]；混合驅動大多為單一驅動方式的簡單疊加，反而會導致調(diào)動更加地頻繁[12]。

新訂單到達是虛擬單元最常見的干擾事件之一。在實際的生產(chǎn)中，現(xiàn)有的加工任務會在加工開始之前已按某一調(diào)度方案安排好，然而在加工開始后，新訂單會在某個不確定的時刻到達。若得不到合理的調(diào)度安排，會使新到訂單等待時間過長，生產(chǎn)設備利用率低下，因此需要考慮重新進行新到達任務與原有未完成任務的時間安排[5]。新訂單的到達不是一次性的，而是在時域上陸續(xù)到達。在先前研究中，面對陸續(xù)到達的訂單，學者大都在新訂單到達時立即構建新的優(yōu)化調(diào)度，以保證新訂單到達后及時融入調(diào)度之中。這種方式下，生產(chǎn)調(diào)度計劃不斷變動，往往使作業(yè)人員無所適從，影響了車間層的控制，降低了生產(chǎn)系統(tǒng)的穩(wěn)定性，導致了調(diào)度的“神經(jīng)質(zhì)”現(xiàn)象[19]。生產(chǎn)計劃改變過于頻繁，嚴重的將導致生產(chǎn)計劃系統(tǒng)的崩潰。

因此，針對訂單陸續(xù)到達的這一干擾，為了保證虛擬單元重調(diào)度兼具適應性和穩(wěn)定性，本文側重于執(zhí)行重調(diào)度方案之前的驅動決策，即決定是否以及何時進行重調(diào)度。通過對重調(diào)度驅動進行決策，以減少重調(diào)度對生產(chǎn)計劃產(chǎn)生的震蕩。為了合理解決是否進行重調(diào)度以及何時進行重調(diào)度的問題，本文首先建立了一個新的虛擬單元重調(diào)度模型作為驅動決策的基礎，該模型在約束條件中考慮了調(diào)度方案的繼承性，對虛擬單元中物流路線龐雜的問題也進行了優(yōu)化。基于此模型，本文提出了一種新的基于損益的虛擬單元周期-事件混合重調(diào)度驅動決策方法，以解決單純進行周期或事件驅動以及兩者簡單疊加驅動的不足。該方法通過衡量重調(diào)度方案的損失與收益，對每個重調(diào)度時刻進行選擇，從而實現(xiàn)對重調(diào)度頻率的優(yōu)化。

2 虛擬單元重調(diào)度模型及算法

本文所提出的重調(diào)度驅動決策方法的流程如圖1所示。由于本文從重調(diào)度方案損失和收益的角度判斷是否進行重調(diào)度，需要預先制定重調(diào)度方案作為驅動決策的基礎。因此，本節(jié)將結合虛擬單元特性建立重調(diào)度優(yōu)化模型。圖中虛線表示生成的調(diào)度方案并不一定是最終會實際執(zhí)行的方案，需要根據(jù)驅動決策的結果進行判斷。

圖1 重調(diào)度驅動決策方法

2.1 多目標優(yōu)化模型

在新訂單陸續(xù)到達的環(huán)境下，訂單不斷累積等待加工，系統(tǒng)的完工時間會因為加工任務總數(shù)的增加而被延長。因此，本文將最大完工時間作為重調(diào)度優(yōu)化目標之一，最小化新訂單對完工時間產(chǎn)生的擾動。同時，完工時間越小，機器的等待時間也就越小，系統(tǒng)的設備利用率就越高。

虛擬單元是由物流連接而成的，單元內(nèi)的設備并不像傳統(tǒng)單元一樣聚集在一起，前后道工序所需的機器并不相互靠近放置同一區(qū)域。在整個加工生產(chǎn)過程中，設備之間的距離不可被忽略不計。每個工件可以有多條不同的加工路徑，而且每道工序的加工有多臺相同或相似的設備可供選擇。不同的調(diào)度安排，會導致工件運輸路線也不一樣。虛擬單元中物流路線十分龐雜，頻繁的重調(diào)度會使運輸路線更為紊亂。本文將工件總運輸距離也作為模型的目標之一，以保證生產(chǎn)系統(tǒng)物流的優(yōu)化。

與一般靜態(tài)調(diào)度不同的是，在重調(diào)度開始時刻，并不是所有設備和工件都是處在閑置狀態(tài)，部分工序正在對應的機器上進行加工。在加工任務具有不可中斷性的前提下，重調(diào)度不能打斷當前正在工作的機器設備，即機器必須完成當前正在進行的任務后，方可安排其他加工任務；工件必須等待當前正在加工的工序完成后，方可進行下一道工序的生產(chǎn)。此外，對于重調(diào)度時刻所有等待加工的工件，無論到達時間先后，不考慮其他因素，相互之間沒有優(yōu)先級與緊迫程度的區(qū)分；工件的工序必須按照工藝要求的先后順序進行加工；在某一時刻，每個工件最多只能在一臺設備上加工，相應地，每臺設備最多只能在加工一個工件；不考慮批量分割。

符號說明：

j表示工件的序號(j=1,2,3,...,J)，J為本次重調(diào)度中工件的總數(shù)；

i表示各工件的工序序號(i=1,2,3,...,Ij)，Ij為工件j的工序數(shù)；

m、k為設備序號(m,k=1,2,3,...,M)，M為虛擬單元系統(tǒng)內(nèi)設備總臺數(shù)；

h表示某一設備上所有加工任務的順序號(h=1,2,3,...,Hm)，Hm為設備m上的任務總數(shù)；

oj,i表示工件j的第i道工序；

pm,h表示設備m上加工的第h個任務；

參數(shù)：

Tj,i,m——表示工件j的第i道工序在設備m上的單位加工時間；

Bj——表示工件j的加工批量；

Dm,k——表示工件從設備m到設備k之間的運輸距離；

N——表示一個非常大的正數(shù)；

ω1、ω2——分別表示目標函數(shù)中完工時間與總運輸距離的權重；

決策變量：

Cmax——表示系統(tǒng)的完工時間，即最后一個工件加工完成的時間；

Yj,i,m——當工序oj,i被分配至設備m上加工時為1，否則為0；

Zj,i,m,h——當工序oj,i被分配在設備m上第h個加工時為1，否則為0；

STj,i——表示工序oj,i的開始加工時間；

SMm,h——表示任務pm,h的開始時間。

虛擬單元重調(diào)度數(shù)學模型建立如下。

目標函數(shù)：

(1)

約束條件：

Cmax≥STj,i+Bj·Tj,i,m?i,j,m

(2)

STj,i+Bj·Tj,i≤STj,i+1?i,j,m

(3)

SMm,h≥SMm,h-1+Zj,i,m,h-1·Tj,i·Bj?i,j,m,h

(4)

STj,i+N·(1-Zj,i,m,h)≥SMm,h?i,j,m,h

(5)

SMm,h+N·(1-Zj,i,m,h)≥STj,i?i,j,m,h

(6)

(7)

(8)

(9)

Cmax≥0，STj,i≥0，SMm,h≥0

(10)

Yj,i,m∈{0,1}，Zj,i,m,h∈{0,1}

(11)

模型的目標函數(shù)為最大完工時間和總運輸距離加權最小。式(1)中，第一項表示加權后的最大完工時間指標，第二項表示加權后的所有工件總運輸距離指標。

在約束條件中，式(2)表示最大完工時間變量的取值范圍約束，該變量值必須大于或等于所有工序的最終完成時間；式(3)確保同一工件各道工序的前后順序滿足加工工藝約束，每個工件的前道工序加工完成后才能開始后道工序的加工；式(4)為每臺設備上的加工任務繼承性約束，每個任務必須等該設備上先前的任務加工完成后才可進行，若為本次調(diào)度期內(nèi)機器上的第一個加工任務，則需等待上一調(diào)度期遺留的、當前仍正處于加工狀態(tài)的工件生產(chǎn)完成；式(5)和(6)表示若工件j的第i道工序被分配在設備m上第h個加工時，oj,i與pm,h開始時間相等，用于關聯(lián)時間層面上工件的先后安排與設備的資源分配；式(7)保證每臺設備每個時刻最多只能被安排對一道工序進行加工；式(8)保證每個工件的每道工序不可能被分配到超過一臺設備上進行生產(chǎn)；式(9)保證每道工序在滿足其工藝需求的設備集中選擇機器；式(10)表明決策變量的非負性；式(11)表明決策變量為二進制變量，即對該變量的賦值只能為0或者為1。

2.2 混合離散粒子群算法

為了保證調(diào)度結果的方案的最優(yōu)化，本文采用一種結合粒子群算法和遺傳算法的混合離散粒子群算法，來求解上文中所建立的虛擬單元重調(diào)度模型。該混合算法將遺傳算法的部分操作加入到粒子的狀態(tài)更新中，指導整個群體的進化過程。粒子群算法所需要的控制參數(shù)比較少，而且可以很快收斂，同時具有很好的魯棒性，被普遍應用于各種類型的優(yōu)化問題[20]。與之相比，遺傳算法盡管局部搜索效率比較低，但它的全局搜索能力相對粒子群更好。利用粒子群算法與遺傳算法的有機組合，能夠充分利用各算法的優(yōu)勢，避免使用單一算法的不足。該混合算法的原理與傳統(tǒng)連續(xù)型粒子群算法類似，主要的改進在其中于遺傳粒子的編碼以及遺傳粒子更新的方式。

粒子編碼：虛擬單元內(nèi)的機器設備“一專多能”，工件具有多條工藝路徑，在原調(diào)度與重調(diào)度方案中，同一工件可以被分配到不同機器上加工。粒子的編碼，不僅要能體現(xiàn)工件加工順序信息，也要包含工件對機器選擇的信息。

圖2 粒子編碼示意圖

在算法開始前，需進行初始化處理，將種群信息設置為某一狀態(tài)。在保證編碼合法性的前提條件下，將隨機地生成的初始位置與初始速度賦予給粒子。求出各個粒子當前位置所對應的目標函數(shù)值，并找出當前種群最優(yōu)解。由于尚未進行迭代，各粒子初始位置對應的目標函數(shù)值即為最優(yōu)，則設為當前的歷史最優(yōu)解。

粒子更新：粒子從個體及鄰域獲得更新信息的方法并不是單一的，可采用多種形式的，遺傳算法的交叉操作[21]也可以成為是粒子改變速度和位置的一種方式，而變異操作可以看作是粒子的隨機搜索過程。粒子通過模仿染色體的交叉方法，實現(xiàn)速度和位置的更新。粒子的速度與當前其個體最優(yōu)解以及群體最優(yōu)解分別進行交叉來得到改進，粒子的位置更新則由粒子的當前位置與當前速度進行交叉來獲得。引入遺傳操作后，粒子的速度-位置更新公式表示形式如下：

Vi(n+1)=Vi(n)?Pibest?Pgbest

(12)

Xi(n+1)=Vi(n+1)?Xi(n)

(13)

其中n表示迭代次數(shù)，Vi表示粒子速度，Xi表示粒子位置，Pibest表示當前個體最優(yōu)位置，Pgbest表示當前群體最優(yōu)位置。

當某個粒子經(jīng)過連續(xù)多次迭代，可能會出現(xiàn)自身信息與之前相比變化的差異幅度很小，那么說明這個粒子可能被限制在當前所在區(qū)域，陷入了局部最優(yōu)的狀況。需引入新的信息，促使粒子跳到解空間中的其他區(qū)域，繼續(xù)進行移動并搜尋。此時，對粒子個體極值進行變異的處理，具體處理方式的公式表示如下：

Pibest(n+1)=mutation(Pibest(n))

(14)

該混合離散粒子群算法流程如圖3：

圖3 混合離散粒子群算法流程

3 重調(diào)度驅動決策

3.1 重調(diào)度決策時刻

新訂單陸續(xù)到達的環(huán)境下，調(diào)度任務集是不斷變化的。運用滾動時域法中的滾動窗口技術，可以將新訂單陸續(xù)到達的動態(tài)過程進行分解，將動態(tài)調(diào)度分成多個連續(xù)有重疊的靜態(tài)區(qū)間，把不確定性調(diào)度問題轉變成一系列確定的調(diào)度問題。滾動窗口與任務集合的關系如圖4所示，在重調(diào)度時刻，已完工的任務將被從調(diào)度窗口中移除，同時，新到的任務將被添加到窗口中。隨著窗口的前移，如此反復直到所有工件都加工完成，以此應對新訂單陸續(xù)到達干擾下，加工任務集合的不確定性問題。

圖4 基于滾動窗口的任務集劃分

從單個訂單層面看，新訂單到達屬于顯性干擾事件，可采用事件驅動重調(diào)度。將新訂單到達作為關鍵事件，該關鍵事件一旦發(fā)生即主動觸發(fā)一次重調(diào)度。采用事件驅動，系統(tǒng)能夠及時和靈活地應對新到訂單。

周期驅動在一定程度上也可以應對新訂單到達對虛擬單元的擾動。實際生產(chǎn)中，訂單由計劃層不斷下發(fā)，制造系統(tǒng)會陸續(xù)地接受到新的訂單任務。采用周期驅動，每間隔固定時段將新到達的訂單納入調(diào)度窗口，對所有待加工訂單進行重調(diào)度，使系統(tǒng)更為平穩(wěn)。

從周期與事件混合策略生成的重調(diào)度時刻集合中進行重調(diào)度驅動決策，可以結合兩者優(yōu)勢，保證用于決策的時刻更為有效。因此將混合策略生成的重調(diào)度時刻集合作為驅動決策與篩選的來源。

然而由于訂單到達時間的不確定性，重調(diào)度周期的設置是關鍵問題?？紤]到在單位時間內(nèi)，到達的新訂單數(shù)量越多，對系統(tǒng)的擾動越大，重調(diào)度頻率也應相應加大。因此，重調(diào)度周期與新訂單到達速率密切相關。

新訂單的到達是不可確知的，但是可視為服從某種概率分布。普遍認為工件到達時間間隔服從參數(shù)為λ的指數(shù)分布。參數(shù)λ為工件的平均到達率，一般地，該參數(shù)可用如下公式表示[22]：

(15)

上式中，η表示所有設備的總體利用率，M表示設備的總數(shù)，μt表示每道工序的平均加工時間，μp表示每個工件的平均所含工序數(shù)。

由此，根據(jù)周期驅動方式可以得到一系列重調(diào)度點T1={tn|tn=t0+n·ΔT}；根據(jù)事件驅動方式得到另一系列重調(diào)度點T2={tn|tn=t0+∑τn}。則T3={tn|tn∈T1∪T2} 即為新的重調(diào)度決策時刻集合。

3.2 重調(diào)度收益

在虛擬單元制造系統(tǒng)中，當單元內(nèi)的加工任務完成，機器設備就可以從該邏輯單元中釋放，與其他設備組成新的虛擬單元進行其他生產(chǎn)任務。完工時間越小，意味著機器能夠及早被釋放。系統(tǒng)的產(chǎn)出與生產(chǎn)時間是正相關的，借用經(jīng)濟學中機會成本的概念，完工時間提前，用于其他生產(chǎn)任務的時間增加，為系統(tǒng)帶來額外的潛在收益。

當新訂單到達系統(tǒng)后，若不進行重新安排，系統(tǒng)原有訂單按原調(diào)度計劃繼續(xù)生產(chǎn)，新訂單進行等待。若不考慮后續(xù)訂單的到達的影響，新訂單的加工在原有已調(diào)度任務加工完成后進行。單獨完成新訂單所需的時間記為TCN。

重調(diào)度后，系統(tǒng)生產(chǎn)結束時間的提前量：

(16)

則重調(diào)度帶來的額外收益為：

(17)

式中，θ為延期懲罰系數(shù)。

3.3 重調(diào)度損失

重調(diào)度可以使某個調(diào)度目標得以優(yōu)化，但與此同時，也會引起生產(chǎn)資源的重新配置，必然會帶來額外的成本。調(diào)度方案的改變，給生產(chǎn)系統(tǒng)帶來或大或小的損失。在重調(diào)度后，由于新到訂單的插入生產(chǎn)，導致部分原有訂單的生產(chǎn)計劃受到影響，工序的加工安排被延后。而由于這樣的變動，相關配套件的需求計劃以及生產(chǎn)物流的規(guī)劃都隨之發(fā)生改變，物料供給和運輸時間安排都需要做出相應的調(diào)整，導致庫存和運輸成本的增加。

本文用重調(diào)度前后工序開始時間的變動來反映重調(diào)度帶來額外的損失，以所有工序被推遲的時間總和來衡量成本的大小。

原調(diào)度中所有工件的工序集合記為UO，重調(diào)度所涉及的工序集合記為UR。重調(diào)度時，原有的且已加工完成的工序不參與重調(diào)度，后續(xù)到達的新訂單的工序則會被添加至調(diào)度窗口;則受重調(diào)度影響的工序集合為UE=UO∩UR。

若工序oj.i在集合UE之中，用STj,i和ST'j,i分別其表示在原調(diào)度和重調(diào)度方案中工序的加工開始時間。

工件j的工序oj,i在新舊調(diào)度方案中的開始加工時間偏差為：

SCj,i=ST'j,i-STj,i

若ST'j,i-STj,i<0，令SCj,i=0

則重調(diào)度引起的額外損失為：

(18)

式中，δji為工件j第i道工序oj,i的加工開始時間變動懲罰系數(shù)。

3.4 決策方法

若混合驅動僅僅將周期驅動與事件驅動產(chǎn)生的重調(diào)度時刻相疊加，這將導致重調(diào)度次數(shù)過多。上文中，T1和T2是按照各自的驅動方式獨立生成的，當它們加合在一起后，數(shù)量較多，而且很有可能在短時間內(nèi)，連續(xù)觸發(fā)重調(diào)度，出現(xiàn)重調(diào)度點相鄰過近或者分布過于緊密的問題。另外，從成本角度考慮，并不是每一個重調(diào)度點都是恰當?shù)闹卣{(diào)度時刻。因而，需要對重調(diào)度時刻進行判斷和決策。

本文將從重調(diào)度帶來損失與收益的角度，提出混合驅動下的重調(diào)度驅動決策。該混合驅動決策方法，不是在生產(chǎn)加工開始前的一次性的全局判斷，而是在每個重調(diào)度點，基于當前實際工況，進行一次在線決策。

每當新訂單到達，或是周期時刻來臨時，根據(jù)上文中所提的虛擬單元重調(diào)度模型，生成重調(diào)度預實施方案。計算出重調(diào)度方案的額外收益RDC與額外損失LSC的值。判斷當執(zhí)行預實施方案時，重調(diào)度過程中帶來的損失是否能夠彌補其能獲得的收益。

若RDC≤LSC，表明產(chǎn)生的新調(diào)度方案與原調(diào)度方案相比，獲得的預期收益不能夠彌補或僅僅能夠彌補調(diào)整帶來的損失，此次重調(diào)度不能在成本層面使系統(tǒng)得到優(yōu)化，此時刻沒有更新調(diào)度方案的必要，取消此重調(diào)度點，繼續(xù)執(zhí)行原調(diào)度方案至下一個重調(diào)度時刻。

若RDC>LSC，則表明重新調(diào)度帶來收益相對于其造成的損失更大，此時刻按照新方案執(zhí)行重調(diào)度。具體的重調(diào)度驅動詳細流程如圖5所示。

圖5 基于損益的重調(diào)度流程圖

4 實例分析

船舶建造是虛擬單元的典型代表，本文選取了H船廠中的分段建造車間為對象，應用實例數(shù)據(jù)，研究所提出重調(diào)度驅動決策方法的有效性和可行性。

4.1 基本數(shù)據(jù)

本案例中，根據(jù)加工任務的相似性所形成虛擬單元制造系統(tǒng)涉及5個工作區(qū)，每個工作區(qū)內(nèi)的設備類型不同，每種類型的設備有多臺，設備的基本信息如表1所示；設備間運輸距離信息如表2所示。

表1 設備信息

在正式生產(chǎn)開始之前，已有部分訂單到達生產(chǎn)系統(tǒng)，訂單信息如表3所示。

在開始加工后，新訂單將會在不確定的時刻，陸續(xù)到達系統(tǒng)。為了體現(xiàn)訂單到達的隨機性，本案例中新訂單的到達時間，將通過模擬獲得。根據(jù)生產(chǎn)車間的歷史數(shù)據(jù)，設備總體利用率η=68.6%，設備總數(shù)M=11，工序平均加工時間μt=25.9h，工件平均工序數(shù)μp=4.3。由式(15)計算可得新工件的平均到達率λ=0.0679，通過隨機生成一組服從參數(shù)為λ的指數(shù)分布的數(shù)列，可得到的新訂單的到達時間間隔，通過累計時間差可得到各訂單實際的到達時間。為了簡化計算便于說明問題，對到達時間進行了取整。新訂單的信息如表4所示，但實際上，新訂單的各項屬性以及其到達時間在其到達之前未知。

表2 設備間運輸距離(單位：米)

表3 訂單加工任務信息

表4 新到達訂單信息

表5 初始調(diào)度計劃時間安排

圖6 初始調(diào)度方案甘特圖

工件加工設備(工序開始時間-結束時間)工序1工序2工序3工序4工序5P1——M7(22-39)M10(39-51)P2—M3(38-50)M6(61-81)M7(96-114)P3M1(14-34)M6(41-61)M7(61-96)M11(96-121)P4M2(24-48)M3(50-70)M6(81-105)M10(105-133)P5—M4(16-28)M6(32-41)M8(41-56)M10(56-71)P6—M4(28-58)M5(58-94)M8(94-124)P7—M6(16-32)M7(39-59)P8M3(14-38)M5(38-56)M9(56-77)M11(77-92)

4.2 結果分析

根據(jù)所給出的算例基本信息，對于本文提出的虛擬單元重調(diào)度模型，使用matlab7.0軟件進行計算；混合粒子群算法迭代次數(shù)為200，交叉率為0.8，變異率為0.6；設置重調(diào)度周期ΔT=25，取δji=0.4，θ=0.6。

下面將結合案例，詳細闡述本文所提出的重調(diào)度驅動方式，說明其具體步驟。

在初始0時刻，將虛擬單元內(nèi)原有訂單調(diào)度安排完畢，初始調(diào)度方案如表5所示，相應甘特圖如圖6所示。

當t=14時，新訂單8到達。此時，工序o1,1、o2,1、o5,1已加工完成，工序o1,2、o6,1、o7,1正在加工。若此時將剩余的未加工工序與新訂單進行重調(diào)度，求解重調(diào)度模型，生成的新的調(diào)度計劃如表6所示。

在重調(diào)度方案中，由于訂單8的加入，原工序集中共有9道工序的開始加工時間被推遲，工序開始加工時間偏差總和為170h；而重調(diào)度預計完工時間提前量為65h。假設實施重調(diào)度，根據(jù)式(17)和(18)計算，得LSC=68，RDC=39，RDC

t=25時，此時到達第一次周期性重調(diào)度時刻。原有工序集合中，有16個工序尚未加工，新訂單8處于等待狀態(tài)。首先生成預調(diào)度方案如表7，計算得LSC=45.2，RDC=39，此時刻重調(diào)度損失較上一時刻的小，但仍不是最佳調(diào)度時刻。

新訂單9在t=32時到來，表8為此次重調(diào)度方案，再次進行重調(diào)度收益與損失的比較，LSC=50.4，RDC=81.6，RDC-LSC>0，通過判定，生產(chǎn)系統(tǒng)將會按照表8的方案進行新的調(diào)度。

同樣地，在接下來的每一個由周期驅動或事件驅動生成的重調(diào)度點，均生成一重調(diào)度方案，然后通過對比LSC和RDC，決定是刪除該重調(diào)度點，或是立即執(zhí)行重調(diào)度方案。案例中各重調(diào)度點的決策情況如表9。

當所有訂單加工完成，在改進的混合驅動方式下，調(diào)度甘特圖最終如圖7所示，圖中虛線表示該時刻進行了重調(diào)度。

表7 重調(diào)度方案(t=25時刻)

表8 重調(diào)度方案(t=32時刻)

表9 重調(diào)度判定

圖7 混合驅動決策后的調(diào)度甘特圖

4.3 對比分析

為表明本文所提出的重調(diào)度驅動決策方法的有效性，將其與使用周期驅動以及事件驅動下的調(diào)度安排進行對比。圖8為單獨使用事件驅動下的調(diào)度甘特圖，圖9為單獨使用周期驅動下的調(diào)度甘特圖。

三種驅動方式評價對比，如表10所示。由于周期驅動不能及時響應動態(tài)變化，所需完工時間最長，且存在明顯的不必要重調(diào)度；事件驅動可以使得調(diào)度的完工時間目標更優(yōu)，但需要的重新調(diào)度次數(shù)也較多。使用改進的混合驅動方式，調(diào)度次數(shù)在三種方式中最少，完工時間也比單獨使用周期驅動要好。盡管完工時間并不是最優(yōu)結果，但是減少了重調(diào)度次數(shù)，亦即減少了對生產(chǎn)系統(tǒng)的震蕩影響，因而也減少了由此帶來的一系列損失，而完工時間指標也在可接受范圍之內(nèi)。因此，本文的驅動決策方法對于重調(diào)度的優(yōu)化結果是令人滿意的，且更具有實際應用價值。

表10 三種驅動方式結果比較

圖8 事件驅動下的調(diào)度甘特圖

圖9 周期驅動下的調(diào)度甘特圖

5 結語

本文研究訂單陸續(xù)到達環(huán)境下虛擬單元的重調(diào)度驅動決策問題。根據(jù)虛擬單元特性，建立了多目標重調(diào)度數(shù)學模型，并設計了一種混合了遺傳操作的離散粒子群優(yōu)化算法用于求解；在周期和事件混合驅動下，提出了一種新的重調(diào)度決策方法，從時間的角度，衡量重調(diào)度的損失和收益，選擇合理的重調(diào)度決策時間點。實例分析表明，在調(diào)度決策目標優(yōu)化的同時，重調(diào)度頻次有明顯的減少。與單獨的周期驅動或事件驅動下的重調(diào)度相比，本文提出的混合驅動下的重調(diào)度，在調(diào)度次數(shù)和完工時間上有明顯的優(yōu)勢。本文提出的重調(diào)度驅動決策方法，加強了生產(chǎn)系統(tǒng)的整體穩(wěn)定性，能夠較好地緩和因頻繁重調(diào)度而引起的生產(chǎn)系統(tǒng)震蕩，可以作為制定重調(diào)度的觸發(fā)開啟時間的依據(jù)。

本文提出的訂單陸續(xù)到達下虛擬單元重調(diào)度驅動決策，是作為重調(diào)度的基礎與前提。在解決了是否進行重調(diào)度的問題之后，后續(xù)的研究工作可關注重調(diào)度方法的進一步改進。為了避免重調(diào)度后虛擬單元產(chǎn)生資源配置混亂的現(xiàn)象，考慮到計劃凍結技術能夠保持計劃的相對穩(wěn)定，可將其引入重調(diào)度之中，在進行驅動決策后，保持部分原有任務的安排不發(fā)生改變，使新調(diào)度方案能夠更好地銜接原方案，更好地提高動態(tài)調(diào)度的穩(wěn)定性。同時，重調(diào)度方法大多基于工件一旦在機器上加工就無法中斷的假設，可進一步研究訂單插入條件下允許加工中斷的調(diào)度模型，使重調(diào)度方案更適合動態(tài)生產(chǎn)環(huán)境的實際情況。

[1] Tambuskar D, Narkhede B, Mahapatra S. A novel algorithm for virtual cellular manufacturing considering real life production factors[J]. International Journal of Services&Operations Management, 2015, 20(2):246.

[2] Ghahve J. Scheduling of virtual manufacturing cells with outsourcing allowed[J]. International Journal of Computer Integrated Manufacturing, 2014,27(12):1079-1089.

[3] 劉鋒, 王建軍, 饒衛(wèi)振. 安裝時間與次序相關的生產(chǎn)調(diào)度干擾管理研究[J]. 中國管理科學,2014,22(1):45-54.

[4] 鄭睿, 呂文元. 考慮故障停機的生產(chǎn)控制與維修計劃聯(lián)合決策模型[J]. 中國管理科學,2016,24(8):116-122.

[5] 劉樂, 周泓. 新工件到達干擾下單機最大延遲時間重調(diào)度[J]. 系統(tǒng)工程學報, 2014, 29(4):494-506.

[6] Yin Yunqiang, Cheng T, Wang Dujuan. Rescheduling on identical parallel machines with machine disruptions to minimize total completion time[J]. European Journal of Operational Research, 2016, 252(3):737-749.

[7] Wang Kai, Choi S H, Qin Hu. An estimation of distribution algorithm for hybrid flow shop scheduling under stochastic processing times[J]. International Journal of Production Research, 2014, 52(24):7360-7376.

[8] 薄洪光, 張鑫, 潘裕韜. 混合無等待流水線干擾管理調(diào)度方法研究[J]. 運籌與管理,2016,25(3):246-254.

[9] Lu M S, Romanowski R. Multicontextual dispatching rules for job shops with dynamic job arrival[J]. The International Journal of Advanced Manufacturing Technology, 2013, 67(1):19-33.

[10] Elnaz N, Amin A. Production planning and worker assignment in a dynamic virtual cellular manufacturing system[J]. International Journal of Management Science & Engineering Management, 2013, 7(2):89-95.

[11] Ouelhadj D, Petrovic S. A survey of dynamic scheduling in manufacturing systems[J]. Journal of Scheduling, 2009, 12(4):417-431.

[12] Adibi M A, Zandieh M, Amiri M. Multi-objective scheduling of dynamic job shop using variable neighborhood search[J]. Expert Systems with Applications, 2010, 37(1):282-287.

[13] Wortmann J. Coordination activities of human planners during rescheduling: case analysis and event handling procedure[J]. International Journal of Production Research, 2011, 49(7):2101-2122.

[14] 張潔, 秦威, 宋代立. 考慮工時不確定的混合流水車間滾動調(diào)度方法[J]. 機械工程學報,2015,51(11):99-108.

[15] 汪雙喜, 張超勇, 劉瓊，等. 不同再調(diào)度周期下的柔性作業(yè)車間動態(tài)調(diào)度[J]. 計算機集成制造系統(tǒng), 2014, 20(10):2470-2478.

[16] Qiao Fei, Wu Qijin, Li Li, et al. A fuzzy Petri net-based reasoning method for rescheduling[J]. Transactions of the Institute of Measurement & Control, 2009, 31(5):435-455.

[17] 劉明周, 張璽, 張銘鑫，等. 基于損益云模型的制造車間重調(diào)度決策方法[J]. 控制與決策,2014,29(8):1458-1464.

[18] Mahdavi I, Amin A, Mohammad M P, et al. Multi-objective cell formation and production planning in dynamic virtual cellular manufacturing systems[J]. International Journal of Production Research, 2011, 49(21):6517-6537.

[19] Rangsaritratsamee R, Ferrell W, Kurz M. Dynamic rescheduling that simultaneously considers efficiency and stability[J]. Computers & Industrial Engineering, 2004, 46(1):1-15.

[20] 宋繼偉, 唐加福. 基于離散粒子群優(yōu)化的軋輥熱處理調(diào)度方法[J]. 管理科學學報, 2010, 13(6):44-53.

[21] 李勁, 李洪, 徐麗麗等. 基于改進遺傳算法的置換裝配線調(diào)度問題研究[J]. 中國管理科學,2016,24(12):63-71.

[22] Jin L, Zhang Chaoyong, Shao Xinyu, et al. A study on the impact of periodic and event-driven rescheduling on a manufacturing system: An integrated process planning and scheduling case[J]. Proceedings of the Institution of Mechanical Engineers Part B Journal of Engineering Manufacture, 2016，(3):1-15.