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

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

1 引言

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

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

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

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

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

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

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

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

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

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

圖1 重調(diào)度驅(qū)動(dòng)決策方法

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

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

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

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

符號(hào)說(shuō)明：

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

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

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

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

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

pm,h表示設(shè)備m上加工的第h個(gè)任務(wù)；

參數(shù)：

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

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

Dm,k——表示工件從設(shè)備m到設(shè)備k之間的運(yùn)輸距離；

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

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

決策變量：

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

Yj,i,m——當(dāng)工序oj,i被分配至設(shè)備m上加工時(shí)為1，否則為0；

Zj,i,m,h——當(dāng)工序oj,i被分配在設(shè)備m上第h個(gè)加工時(shí)為1，否則為0；

STj,i——表示工序oj,i的開(kāi)始加工時(shí)間；

SMm,h——表示任務(wù)pm,h的開(kāi)始時(shí)間。

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

目標(biāo)函數(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)

模型的目標(biāo)函數(shù)為最大完工時(shí)間和總運(yùn)輸距離加權(quán)最小。式(1)中，第一項(xiàng)表示加權(quán)后的最大完工時(shí)間指標(biāo)，第二項(xiàng)表示加權(quán)后的所有工件總運(yùn)輸距離指標(biāo)。

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

2.2 混合離散粒子群算法

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

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

圖2 粒子編碼示意圖

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

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

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

(12)

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

(13)

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

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

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

(14)

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

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

3 重調(diào)度驅(qū)動(dòng)決策

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

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

圖4 基于滾動(dòng)窗口的任務(wù)集劃分

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

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

從周期與事件混合策略生成的重調(diào)度時(shí)刻集合中進(jìn)行重調(diào)度驅(qū)動(dòng)決策，可以結(jié)合兩者優(yōu)勢(shì)，保證用于決策的時(shí)刻更為有效。因此將混合策略生成的重調(diào)度時(shí)刻集合作為驅(qū)動(dòng)決策與篩選的來(lái)源。

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

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

(15)

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

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

3.2 重調(diào)度收益

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

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

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

(16)

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

(17)

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

3.3 重調(diào)度損失

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

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

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

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

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

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

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

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

(18)

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

3.4 決策方法

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

本文將從重調(diào)度帶來(lái)?yè)p失與收益的角度，提出混合驅(qū)動(dòng)下的重調(diào)度驅(qū)動(dòng)決策。該混合驅(qū)動(dòng)決策方法，不是在生產(chǎn)加工開(kāi)始前的一次性的全局判斷，而是在每個(gè)重調(diào)度點(diǎn)，基于當(dāng)前實(shí)際工況，進(jìn)行一次在線決策。

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

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

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

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

4 實(shí)例分析

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

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

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

表1 設(shè)備信息

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

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

表2 設(shè)備間運(yùn)輸距離(單位：米)

表3 訂單加工任務(wù)信息

表4 新到達(dá)訂單信息

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

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

工件加工設(shè)備(工序開(kāi)始時(shí)間-結(jié)束時(shí)間)工序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 結(jié)果分析

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

下面將結(jié)合案例，詳細(xì)闡述本文所提出的重調(diào)度驅(qū)動(dòng)方式，說(shuō)明其具體步驟。

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

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

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

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

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

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

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

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

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

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

圖7 混合驅(qū)動(dòng)決策后的調(diào)度甘特圖

4.3 對(duì)比分析

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

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

表10 三種驅(qū)動(dòng)方式結(jié)果比較

圖8 事件驅(qū)動(dòng)下的調(diào)度甘特圖

圖9 周期驅(qū)動(dòng)下的調(diào)度甘特圖

5 結(jié)語(yǔ)

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

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

[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)振. 安裝時(shí)間與次序相關(guān)的生產(chǎn)調(diào)度干擾管理研究[J]. 中國(guó)管理科學(xué),2014,22(1):45-54.

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

[5] 劉樂(lè), 周泓. 新工件到達(dá)干擾下單機(jī)最大延遲時(shí)間重調(diào)度[J]. 系統(tǒng)工程學(xué)報(bào), 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] 薄洪光, 張?chǎng)? 潘裕韜. 混合無(wú)等待流水線干擾管理調(diào)度方法研究[J]. 運(yùn)籌與管理,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] 張潔, 秦威, 宋代立. 考慮工時(shí)不確定的混合流水車間滾動(dòng)調(diào)度方法[J]. 機(jī)械工程學(xué)報(bào),2015,51(11):99-108.

[15] 汪雙喜, 張超勇, 劉瓊，等. 不同再調(diào)度周期下的柔性作業(yè)車間動(dòng)態(tài)調(diào)度[J]. 計(jì)算機(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]. 管理科學(xué)學(xué)報(bào), 2010, 13(6):44-53.

[21] 李勁, 李洪, 徐麗麗等. 基于改進(jìn)遺傳算法的置換裝配線調(diào)度問(wèn)題研究[J]. 中國(guó)管理科學(xué),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.