新訂單與時(shí)間窗口混合驅(qū)動(dòng)的繼承性虛擬單元重構(gòu)

韓文民，余 義，高龍龍，方錦烽，李正義

(江蘇科技大學(xué) 經(jīng)濟(jì)管理學(xué)院，江蘇 鎮(zhèn)江 212003)

0 引言

隨著市場競爭的加劇，制造企業(yè)面臨著日益頻繁且難以預(yù)測(cè)的市場變化，為保持競爭力，企業(yè)不僅需要高效地生產(chǎn)高質(zhì)量產(chǎn)品，還要能夠及時(shí)響應(yīng)快速變化的市場和消費(fèi)者需求，因此多品種、小批量的訂單式生產(chǎn)(Make-To-Order manufacturing, MTO)成為制造業(yè)發(fā)展的主流。為有效應(yīng)對(duì)這一發(fā)展趨勢(shì)，突破設(shè)備物理位置不能或難以改變的障礙，具有提高生產(chǎn)制造柔性及敏捷性優(yōu)勢(shì)的虛擬單元生產(chǎn)模式應(yīng)運(yùn)而生[1]。虛擬單元生產(chǎn)系統(tǒng)(簡稱虛擬單元)主要根據(jù)工件工藝相似性將工件聚類為工件族，并將生產(chǎn)資源在邏輯上分配給相應(yīng)的工件族進(jìn)行調(diào)度生產(chǎn)，加工任務(wù)結(jié)束后虛擬單元中的設(shè)備會(huì)自動(dòng)釋放，以供其他虛擬單元使用。在虛擬單元生產(chǎn)過程中，隨著新訂單的陸續(xù)隨機(jī)到達(dá)，原有的虛擬單元結(jié)構(gòu)可能不適應(yīng)后期的加工需求，因此虛擬單元重構(gòu)頻繁發(fā)生。

目前，有關(guān)驅(qū)動(dòng)單元重構(gòu)或重調(diào)度方式的研究得到了國內(nèi)外學(xué)者的廣泛關(guān)注。Gürel等[2]研究了設(shè)備故障等事件驅(qū)動(dòng)下的重調(diào)度問題，構(gòu)建了考慮壓縮工件加工時(shí)間帶來的額外成本，以及干擾造成的未按時(shí)完工的工件數(shù)最小化雙目標(biāo)模型；Shen等[3]考慮常規(guī)訂單、急件訂單等事件驅(qū)動(dòng)下的重調(diào)度問題，提出求解該問題的多目標(biāo)演化算法；Zhang等[4]研究了急件、任務(wù)取消等事件驅(qū)動(dòng)下的重調(diào)度問題，提出多代理和蟻群算法混合的處理方法；Rezazadeh等[5]研究了考慮周期的虛擬單元構(gòu)建問題，提出解決該問題的粒子群和模擬退火混合算法；Mahdavi等[6]研究了時(shí)間周期驅(qū)動(dòng)的多目標(biāo)虛擬單元構(gòu)建問題，并利用模糊目標(biāo)規(guī)劃進(jìn)行求解；Paydar等[7]討論了帶模糊參數(shù)的、時(shí)間周期驅(qū)動(dòng)的多目標(biāo)虛擬單元構(gòu)建問題，并使用修訂多重選擇目標(biāo)規(guī)劃方法求解問題；Moradgholi等[8]研究了在時(shí)間周期驅(qū)動(dòng)下的雙目標(biāo)模糊規(guī)劃模型，并使用遺傳算法進(jìn)行求解。應(yīng)該看到，單純事件驅(qū)動(dòng)可能因頻繁變動(dòng)導(dǎo)致生產(chǎn)計(jì)劃的“神經(jīng)質(zhì)現(xiàn)象”，單純周期驅(qū)動(dòng)則容易導(dǎo)致生產(chǎn)系統(tǒng)不能及時(shí)響應(yīng)生產(chǎn)系統(tǒng)內(nèi)外條件的動(dòng)態(tài)變化，雖然有些文獻(xiàn)考慮了事件—周期的混合驅(qū)動(dòng)，但大多為單一驅(qū)動(dòng)方式的簡單疊加，導(dǎo)致單元重構(gòu)及調(diào)度更加頻繁[9-10]。

繼承性虛擬單元重構(gòu)指在單元重構(gòu)時(shí)，不僅要使重構(gòu)單元的生產(chǎn)高效運(yùn)行，還要考慮穩(wěn)定性的重要指標(biāo)，即盡可能地繼承原有虛擬單元的配置形式，減少頻繁調(diào)整對(duì)生產(chǎn)系統(tǒng)帶來的沖擊。目前，在虛擬單元重構(gòu)文獻(xiàn)中，大多以時(shí)間(最長完工時(shí)間、平均延誤時(shí)間、平均流程時(shí)間等)或成本作為重構(gòu)評(píng)價(jià)標(biāo)準(zhǔn)[6-7,11-13]，沒有考慮重構(gòu)的繼承性指標(biāo)，而將單元結(jié)構(gòu)進(jìn)行全局調(diào)整。頻繁大規(guī)模變動(dòng)的重構(gòu)會(huì)使生產(chǎn)調(diào)度更為復(fù)雜，從而造成物流紊亂，進(jìn)而帶來更多的重置成本和物料搬運(yùn)成本，增加工人的生產(chǎn)壓力，同時(shí)還會(huì)給生產(chǎn)的過程控制和質(zhì)量控制帶來很多隱患[14-15]。因此，如何兼顧重構(gòu)后單元生產(chǎn)的高效性與穩(wěn)定性，即繼承性的單元重構(gòu)，具有重要的意義。Wu等[16]研究了機(jī)器故障下的重構(gòu)問題，其所考慮的繼承性指標(biāo)為工序開始時(shí)間及工序順序的變化，Vieira等[17]提出制造系統(tǒng)的重構(gòu)框架模型，明確了穩(wěn)定性是系統(tǒng)重構(gòu)的重要評(píng)價(jià)標(biāo)準(zhǔn)；Li等[18]研究了新訂單到達(dá)后的虛擬單元重調(diào)度問題，以重構(gòu)前后單元內(nèi)設(shè)備數(shù)量的改變作為繼承性指標(biāo)。

在企業(yè)實(shí)際生產(chǎn)過程中，需要根據(jù)未來多個(gè)計(jì)劃期的市場需求構(gòu)建多期虛擬單元方案。然而，在實(shí)施虛擬單元生產(chǎn)過程中，新訂單會(huì)隨機(jī)到達(dá)生產(chǎn)車間[10]。針對(duì)這種擾動(dòng)，為保證生產(chǎn)過程組織的穩(wěn)定性，本文在新訂單與時(shí)間窗口相結(jié)合的混合驅(qū)動(dòng)方式下，對(duì)虛擬單元進(jìn)行重構(gòu)。若單元的剩余加工能力能夠滿足新訂單的生產(chǎn)需求，則采用訂單驅(qū)動(dòng)的重構(gòu)方式，在當(dāng)期利用剩余設(shè)備能力僅按照高效性指標(biāo)進(jìn)行虛擬單元構(gòu)建；若單元內(nèi)剩余設(shè)備加工能力不能滿足新訂單的生產(chǎn)需求，則在當(dāng)期利用剩余設(shè)備能力將可以完成的任務(wù)僅按高效性指標(biāo)進(jìn)行虛擬單元構(gòu)建，不能完成部分當(dāng)期采用時(shí)間窗口凍結(jié)技術(shù)將新訂單未完成部分進(jìn)行凍結(jié)，到本期生產(chǎn)結(jié)束后，再將新訂單加入后期虛擬單元進(jìn)行生產(chǎn)。后期的虛擬單元重構(gòu)不僅要使后續(xù)虛擬單元生產(chǎn)高效運(yùn)行，還應(yīng)最大程度地繼承原有虛擬單元的配置形式，減少單元頻繁重構(gòu)對(duì)生產(chǎn)的沖擊。為此，本文在現(xiàn)有研究基礎(chǔ)上，提出繼承性的虛擬單虛擬單元重構(gòu)方案。該重構(gòu)方法綜合考慮了虛擬單元重構(gòu)的高效性與穩(wěn)定性特征(高效性包括產(chǎn)品工藝相似性、跨單元次數(shù)、設(shè)備利用率、物流成本因素，穩(wěn)定性包括單元內(nèi)設(shè)備數(shù)量及類型的變動(dòng)因素)，構(gòu)建了非線性多目標(biāo)整數(shù)規(guī)劃模型，為了有效地求解模型，在相關(guān)算法研究基礎(chǔ)上[5,6,19,20]設(shè)計(jì)了基于動(dòng)態(tài)層次分析的多目標(biāo)遺傳優(yōu)化算法，該算法通過隨機(jī)搜索Pareto優(yōu)化解集實(shí)現(xiàn)了對(duì)模型的有效求解。

1 新訂單下的繼承性虛擬單元重構(gòu)

1.1 新訂單下的繼承性虛擬單元重構(gòu)問題及假設(shè)

新訂單到達(dá)時(shí)的虛擬單元重構(gòu)問題可描述為：車間內(nèi)的原有虛擬單元數(shù)為c(c=1,2,…,C)個(gè)，可供加工的設(shè)備數(shù)為m(m=1,2,…,M)臺(tái)，原加工工件數(shù)為i(i=1,2,…,I)件，這里各工件包括j(j=1,2,…,Ji)道工序。在t時(shí)刻，新訂單i′(i′=1,2,…,I′，I′表示到達(dá)新工件的總數(shù))到達(dá)車間，則車間工件數(shù)量為I+1,I+2,…,I+I′。

為更好地構(gòu)建模型，現(xiàn)對(duì)虛擬單元制造系統(tǒng)作如下假設(shè)：①各工件的各期需求量已知；②各工件需要不同類型的機(jī)床對(duì)其進(jìn)行多道工序加工，且工藝順序與加工時(shí)間已知；③每臺(tái)機(jī)床在同一時(shí)間內(nèi)只能加工一道工序；④同一工件的同一工序只能在一臺(tái)機(jī)床上加工完成；⑤新訂單到達(dá)時(shí)，若現(xiàn)有設(shè)備的剩余加工能力不能滿足其生產(chǎn)需求，則只對(duì)尚未加工工件的工序進(jìn)行虛擬單元重構(gòu)，即在某機(jī)床上正在加工的工件工序也不受影響，直至加工完成，已加工完成的工件工序也不受影響，重構(gòu)時(shí)不予考慮；⑥不考慮機(jī)床故障。

1.2 新訂單下的繼承性虛擬單元重構(gòu)模型

1.2.1 參數(shù)定義

c為第c個(gè)虛擬單元，c=1,2,…,C；

t為第t個(gè)虛擬單元生產(chǎn)計(jì)劃期，t=1,2,…,T；

i為第i個(gè)加工工件，i=1,2,…,I；

j為加工工件的第j道工序，j=1,2,…,Ji；

m,k為第m或k臺(tái)設(shè)備，m,k∈1,2,…,M，m≠k；

βij為工件i的工序j的單位移動(dòng)成本；

d(mi,j→mi,j+1)為加工工件i的工序j和工序j+1的設(shè)備之間的距離；

Dit為工件i在計(jì)劃期t的需求量；

Bi為工件i的生產(chǎn)批量；

Oik為單位生產(chǎn)批量工件i在設(shè)備k上的加工時(shí)間；

Ack為重構(gòu)前設(shè)備所屬的虛擬單元狀態(tài)，Ack=1表示設(shè)備k屬于單元c，Ack=0表示設(shè)備k不屬于單元c；

Ztcij為重構(gòu)前工件i中工序j所屬的單元狀態(tài)，Ztcij=1表示計(jì)劃期t內(nèi)工件i的第個(gè)j工序在虛擬單元c中加工，否則Ztcij=0；

DLi為工件i的交貨期；

Stemin為所有重構(gòu)方案中的最少跨單元次數(shù)；

Fi為工件i所需的加工流程時(shí)間；

Ej為工序j的完成時(shí)間；

Sj為工序j的開工時(shí)間；

Ocm為設(shè)備m在虛擬單元c中某時(shí)刻加工的工序數(shù)；

Nim為工件i在設(shè)備m上加工的工序數(shù)。

1.2.2 決策變量

為虛擬單元方案調(diào)整前與調(diào)整后包含虛擬單元總數(shù)的較小值，此處單元調(diào)整后虛擬單元數(shù)量的增加或減少不算對(duì)原虛擬單元結(jié)構(gòu)的調(diào)整。

1.2.3 模型構(gòu)建

(1)工藝相似性指標(biāo) 工藝相似性是虛擬單元構(gòu)建的基礎(chǔ)，且將相似產(chǎn)品聚類為待加工工件族進(jìn)行連續(xù)生產(chǎn)后可減少生產(chǎn)準(zhǔn)備時(shí)間，增加工人熟練程度，從而提高效率，保障產(chǎn)品質(zhì)量，因此該指標(biāo)是實(shí)現(xiàn)虛擬單元生產(chǎn)高效性的重要基礎(chǔ)之一。工藝相似性指標(biāo)

(1)

(2)物流成本指標(biāo) 考慮虛擬單元具有不改變?cè)O(shè)備的物理布局而形成邏輯上相互關(guān)聯(lián)的虛擬動(dòng)態(tài)實(shí)體進(jìn)行工件加工的特性，生產(chǎn)計(jì)劃的變更可能導(dǎo)致待加工工件在制造設(shè)備間流轉(zhuǎn)頻繁，進(jìn)而造成物流紊亂和物流成本增加。因此，在高效性指標(biāo)方面要充分考慮物流成本指標(biāo)f2，

(2)

式(2)表示各計(jì)劃期中所有待加工工件按加工工序順序選中的設(shè)備距離與該工序單位移動(dòng)成本之積。

(3)跨單元次數(shù)指標(biāo) 實(shí)際生產(chǎn)過程中，工件跨單元加工會(huì)影響生產(chǎn)的連續(xù)性，增加設(shè)備與工裝的調(diào)整時(shí)間和費(fèi)用以及管理工作量，從而降低了虛擬單元生產(chǎn)效能。因此，高效性指標(biāo)中要考慮工件跨單元移動(dòng)次數(shù)指標(biāo)f3，

f3=∑Tt=1∑Cc=1∑Ii=1DitBi∑Jij=2Yjict(1-Yj-1,ict)。

(3)

式(3)表示各計(jì)劃期內(nèi)構(gòu)建的虛擬單元中各加工工件的所有加工工序是否都在該單元內(nèi)部完成。式中·表示取小于內(nèi)部值的最大整數(shù)。

(4)設(shè)備利用率指標(biāo) 研究表明，較低的設(shè)備利用率將導(dǎo)致設(shè)備投資費(fèi)用增加、人員費(fèi)用增加、資產(chǎn)回報(bào)率低。用最小化設(shè)備負(fù)載與最大設(shè)備能力間的比值表述設(shè)備利用率：

(4)

因此，在新訂單到達(dá)情況下的生產(chǎn)高效性指標(biāo)表述為

f={f1,f2,f3,f4}。

(5)

式中：工藝相似性指標(biāo)f1取最大值,以使相似工件盡可能在同一單元內(nèi)完成加工，從而減少調(diào)整時(shí)間；f2取最小值,以降低工件加工過程中的物流成本；f3取最小值,以減少調(diào)度的復(fù)雜性；f4取最大值,以提升設(shè)備利用率，降低加工成本。

在新訂單到達(dá)的情況下，生產(chǎn)高效性指標(biāo)越高，表示單元的生產(chǎn)效率越高，其表達(dá)式為

F1=maxf。

(6)

式中雖然各目標(biāo)選取的極值不同，但是應(yīng)保持整體最大，以保證系統(tǒng)整體最優(yōu)。

穩(wěn)定性指標(biāo)是繼承性虛擬單元重構(gòu)與非繼承性虛擬單元重構(gòu)的主要區(qū)別。優(yōu)化調(diào)整后的虛擬單元與原有虛擬單元間的差別，即單元內(nèi)部設(shè)備變動(dòng)越小，該方案的穩(wěn)定性越高。其表達(dá)式為

(7)

因此，針對(duì)新訂單到達(dá)的虛擬單元重構(gòu)的多目標(biāo)規(guī)劃模型如下：

目標(biāo)函數(shù)為

F={F1,F2}。

(8)

s.t.

j=1,2,…,Ji,i=1,2,…,I,c=1,2,…,C,

m∈1,2,…,M;

(9)

Mcm={0，1}，

c=1,2,…,C,m∈1,2,…,M;

(10)

Ej≤Sj+1，j=1,2,…,Ji;

(11)

(12)

Xkc≤Nkc，c=1,2,…,C,k∈1,2,…,M;

(13)

(14)

(15)

i=1,2,…,I,j=1,2,…,Ji;

(16)

Xjim，Xjicm，Yjict為0-1變量。

(17)

其中：式(9)表示所有工件的一道加工工序只能被分配到一個(gè)虛擬單元內(nèi)的一臺(tái)設(shè)備上加工；式(10)表示每臺(tái)設(shè)備在某時(shí)刻只能屬于一個(gè)虛擬單元,且每次最多只能分配到一道工序；式(11)表示只有上道工序完工,下道工序才能開始；式(12)限制了所構(gòu)建虛擬單元總數(shù)不超過規(guī)定的上限；式(13)限制了虛擬單元內(nèi)加工設(shè)備數(shù)量不超過規(guī)定的上限；式(14)～式(16)表示決策變量的非負(fù)整數(shù)約束；(17)表示0-1變量約束。

該模型屬于非線性多目標(biāo)整數(shù)規(guī)劃模型，因?yàn)槟Ｐ蜑槎嗄繕?biāo)且物流成本指標(biāo)、跨單元次數(shù)指標(biāo)具有非線性的特征，數(shù)學(xué)規(guī)劃算法難以有效求解模型，所以本文設(shè)計(jì)智能算法求解模型。

2 算法設(shè)計(jì)

本文構(gòu)建的模型為非線性多目標(biāo)整數(shù)規(guī)劃模型，隨著訂單數(shù)、設(shè)備、虛擬單元個(gè)數(shù)、計(jì)劃期數(shù)的增加，模型的求解將變得非常復(fù)雜困難。因此，設(shè)計(jì)基于遺傳算法的多目標(biāo)優(yōu)化算法來求解模型。

2.1 編碼與解碼

染色體的編碼是實(shí)現(xiàn)多目標(biāo)遺傳算法的基礎(chǔ)，根據(jù)模型約束條件(每個(gè)工件的工序加工順序確定等)和決策變量要求，文中采用分段編碼的方法進(jìn)行編碼，染色體由單元分配(設(shè)備)、單元分配(工件)、工序機(jī)器選擇和工件排序4部分組成?？紤]以工件數(shù)I、每個(gè)工件加工工序J、設(shè)備類型M、單元數(shù)C等參數(shù)進(jìn)行編碼，圖1所示為總工件數(shù)I=3，每個(gè)工件加工工序J=3，設(shè)備類型M=5，單元數(shù)C=3的編碼過程。

圖1中，單元分配部分的數(shù)字為機(jī)器(工件)所屬的單元號(hào)，例如機(jī)器M1的單元分配號(hào)為3，表示將它分配到單元3中；工序機(jī)器選擇部分的數(shù)字為該工序可選機(jī)器集中對(duì)應(yīng)的機(jī)器編號(hào)，例如工件1工序1的機(jī)器選擇數(shù)字為3,則該工序在可選機(jī)器集中選擇對(duì)應(yīng)的機(jī)器M4進(jìn)行加工；工件排序部分的數(shù)字為工件的編號(hào)，例如第1個(gè)“1”表示工件1的工序1第1個(gè)開始加工，第2個(gè)“1”表示工件1的工序2排在第3個(gè)加工。

2.2 選擇操作

選擇操作是為了保證解的質(zhì)量而進(jìn)行優(yōu)勝劣汰，使優(yōu)秀且擁擠密度比較小的個(gè)體參與下一代進(jìn)化。為了避免算法在目標(biāo)空間一個(gè)固定點(diǎn)的區(qū)域采樣，本文算法采用隨機(jī)權(quán)重在整個(gè)Pareto前沿面均勻采樣。同時(shí)，為有效引導(dǎo)選擇出滿意的優(yōu)良基因，采用一致矩陣法對(duì)各目標(biāo)函數(shù)進(jìn)行罰函數(shù)處理，從而為不同個(gè)體賦予不同的選擇概率，以保證每次迭代所選擇的解的優(yōu)越性，從而加快收斂速度[21]。多目標(biāo)模型的隨機(jī)權(quán)重和目標(biāo)可表示為：

(18)

(19)

(20)

式中α表示敏感因子，根據(jù)實(shí)際情況取值為0，1，2，3。

最后，通過式(21)對(duì)第i個(gè)待評(píng)價(jià)方案進(jìn)行綜合評(píng)價(jià)，并得到懲罰系數(shù)θi。

(21)

2.3 交叉與變異操作

為使更新的種群在滿足模型約束的基礎(chǔ)上具有更好的遺傳父代有利基因的能力，采用基于工序編碼的優(yōu)先交叉操作(Precedence Operation Crossover，POX)。首先，選定需要交叉的兩條染色體，并隨機(jī)選中一個(gè)工件的編號(hào);然后，將第2條染色體中該編號(hào)的基因位置記錄下來插入第1條染色體的對(duì)應(yīng)位置;最后，將第1條染色體中的剩余基因依次放入剩下的基因位置。由此，便實(shí)現(xiàn)了交叉操作,具體的交叉過程如圖2所示。

為保持群體的多樣性，采用插入變異的方式，即隨機(jī)選取某一基因或基因片段，插入另一個(gè)不同的隨機(jī)位置。

3 實(shí)例分析

以某船廠機(jī)加工車間的實(shí)際生產(chǎn)訂單為例進(jìn)行實(shí)例分析。新訂單出現(xiàn)后，首先需要對(duì)現(xiàn)有剩余設(shè)備的加工能力進(jìn)行衡量，當(dāng)剩余設(shè)備加工能力滿足新訂單生產(chǎn)時(shí)，虛擬單元的構(gòu)建過程較為簡單，實(shí)例分析不展開討論。本實(shí)例主要在剩余設(shè)備不足以滿足新訂單生產(chǎn)的情況下，對(duì)原虛擬單元進(jìn)行繼承性重構(gòu)分析?？晒┘庸さ脑O(shè)備信息、生產(chǎn)車間所需加工工件的工序信息及設(shè)備之間的物流距離信息分別如表1～表3所示。

表1 設(shè)備的相關(guān)信息

表2 加工工件的工序信息

續(xù)表2

注：“可加工設(shè)備”列表明了能加工對(duì)應(yīng)工序的所有設(shè)備，工件工序在相應(yīng)設(shè)備上的加工時(shí)間為工件加工數(shù)量與對(duì)應(yīng)工序單個(gè)工件在設(shè)備上的加工時(shí)間的乘積。

表3 各設(shè)備之間的物流距離信息 m

注：表中距離為曼哈頓距離。

本文采用MATLAB 2017a實(shí)現(xiàn)了虛擬單元繼承性重構(gòu)的算法求解。首先，在初始階段根據(jù)待加工工件和工藝信息構(gòu)建初始虛擬單元。本文多目標(biāo)遺傳算法的參數(shù)設(shè)置如下：種群數(shù)目為50，迭代次數(shù)為500，交叉概率為0.01，變異概率為0.8[22]。在構(gòu)建初始虛擬單元時(shí)，考慮到各高效性指標(biāo)中，跨單元次數(shù)和設(shè)備利用率在虛擬單元構(gòu)建中均起輔助作用，因此給定各高效性指標(biāo)權(quán)重分別為f1=0.4 ，f2=-0.3 ，f3=-0.15 ，f4=0.15。在計(jì)劃期2中，采用繼承性虛擬單元重構(gòu)方案進(jìn)行重構(gòu)，得出的初始虛擬單元構(gòu)建方案如表4所示，算法的收斂效果如圖3和圖4所示。

表4 初始虛擬單元構(gòu)建方案

續(xù)表4

由表4可知，針對(duì)待加工工件和工藝信息計(jì)劃期1與計(jì)劃期2分別生成了3個(gè)虛擬單元，且3個(gè)虛擬單元均存在設(shè)備共享使用的情況，因此可以有效降低工件跨單元加工的次數(shù)，保證工件盡可能在相應(yīng)的虛擬單元內(nèi)完成生產(chǎn)。同時(shí)，因?yàn)樵谟?jì)劃期2中采用繼承性虛擬單元重構(gòu)方案，所選方案基本保持計(jì)劃期1中虛擬單元的配置形式，所以可以實(shí)現(xiàn)虛擬單元生產(chǎn)的持續(xù)性，避免重構(gòu)幅度較大而導(dǎo)致的生產(chǎn)中斷、準(zhǔn)備成本過高、工人熟練度下降等問題。在計(jì)劃期1的虛擬單元生產(chǎn)過程中出現(xiàn)新訂單P10，P11插入的情況，此時(shí)應(yīng)用計(jì)劃期窗口凍結(jié)技術(shù)對(duì)計(jì)劃期2中原有的虛擬單元進(jìn)行快速繼承性重構(gòu)，以滿足新訂單加入下的生產(chǎn)需求。新訂單P10，P11的工序信息如表5所示。

表5 新訂單的工序信息

顯然剩余生產(chǎn)設(shè)備不能夠滿足新訂單的生產(chǎn)要求，因此在第1期加工任務(wù)完成后將新訂單插入第2期，采用本文提出的包含生產(chǎn)高效性和生產(chǎn)穩(wěn)定性的繼承性虛擬單元重構(gòu)方法進(jìn)行虛擬單元重構(gòu)，得到的虛擬單元構(gòu)建方案如表6所示。

表6 虛擬單元繼承性重構(gòu)方案

根據(jù)重構(gòu)后的虛擬單元可知，新訂單P10，P11被共同分配至虛擬單元1對(duì)應(yīng)的工件族，同時(shí)在虛擬單元1內(nèi)增加了設(shè)備以同時(shí)滿足原始訂單和新訂單的生產(chǎn)需求。將新訂單采用文獻(xiàn)[10]的方法進(jìn)行重構(gòu)，所得的方案及其對(duì)比如表7和表8所示，收斂圖如圖5和圖6所示。

表7 虛擬單元模塊化重構(gòu)方案

表8 虛擬單元重構(gòu)方案對(duì)比

將繼承性虛擬單元重構(gòu)方案與模塊化虛擬單元重構(gòu)方案的結(jié)果，對(duì)比其跨單元次數(shù)、物流成本、設(shè)備利用率、穩(wěn)定性指標(biāo)和完工時(shí)間，對(duì)比結(jié)果如表8所示。其中，完工時(shí)間采用文獻(xiàn)[23]的方法進(jìn)行計(jì)算。

本文將所得結(jié)果與文獻(xiàn)[24]所提方法的運(yùn)算結(jié)果進(jìn)行對(duì)比。由表8可見，文獻(xiàn)[24]方法旨在有效減少跨單元物流次數(shù)，實(shí)現(xiàn)虛擬單元的敏捷性重構(gòu)，與本文提出的繼承性虛擬單元重構(gòu)方案相比，其跨單元次數(shù)較少。但是，繼承性虛擬單元重構(gòu)方案減少了虛擬單元數(shù)、完工時(shí)間和物流成本，提高了設(shè)備利用率，更好地實(shí)現(xiàn)了設(shè)備共享。

同時(shí)與模塊化虛擬單元重構(gòu)方案相比，繼承性的虛擬單元重構(gòu)方案在穩(wěn)定性指標(biāo)方面有明顯的優(yōu)勢(shì)，這將大大降低虛擬單元生產(chǎn)計(jì)劃的變動(dòng)幅度，減少單元內(nèi)設(shè)備和任務(wù)的變動(dòng)，避免因單元生產(chǎn)中物流紊亂、重置成本高昂，以及工人熟練度降低且產(chǎn)生消極情緒，而導(dǎo)致的生產(chǎn)效率降低等問題。另外，單元生產(chǎn)變動(dòng)幅度小還有利于提高單元重構(gòu)的速度和系統(tǒng)的敏捷性。

4 結(jié)束語

本文研究了新訂單隨機(jī)到達(dá)情況下，訂單與時(shí)間窗口混合驅(qū)動(dòng)的繼承性虛擬單元重構(gòu)。在虛擬單元重構(gòu)中，采用了訂單與時(shí)間窗口相結(jié)合的驅(qū)動(dòng)方法，并考慮了虛擬單元重構(gòu)的繼承性指標(biāo)，一方面提高了企業(yè)應(yīng)對(duì)新訂單隨機(jī)到達(dá)所產(chǎn)生的擾動(dòng)的響應(yīng)能力，另一方面在維持虛擬單元高效生產(chǎn)的同時(shí)，保持了原有虛擬單元配置的穩(wěn)定性。為此，本文構(gòu)建了一個(gè)非線性多目標(biāo)整數(shù)規(guī)劃模型，并設(shè)計(jì)了基于動(dòng)態(tài)層次分析的多目標(biāo)遺傳優(yōu)化算法以求解模型，通過隨機(jī)搜索Pareto優(yōu)化解集，尋求繼承性虛擬單元重構(gòu)方案。實(shí)例分析表明，與非繼承性虛擬單元重構(gòu)相比，繼承性虛擬單元重構(gòu)在減少跨單元生產(chǎn)次數(shù)和完工時(shí)間、提高設(shè)備利用率及降低單元生產(chǎn)物流成本等方面具有明顯優(yōu)勢(shì)。

為更好地反映生產(chǎn)實(shí)際情況，未來可研究新訂單中帶有緊急訂單、出現(xiàn)設(shè)備故障，以及訂單的加工時(shí)間和交貨期不確定等情況下的繼承性虛擬單元重構(gòu)問題，同時(shí)在繼承性虛擬單元重構(gòu)中集成單元生產(chǎn)調(diào)度，進(jìn)行虛擬單元重構(gòu)與生產(chǎn)調(diào)度集成的全局優(yōu)化決策。

參考文獻(xiàn):

[1] HAN Wenmin, GAO Longlong, WENG Hongbing, et al. Research on virtual cell scheduling of pipe processing in ship building based on theory of blocking flow[J].Shipbuilding of China,2016,57(3):164-175(in Chinese).[韓文民,高龍龍,翁紅兵,等.基于阻塞流理論的船舶建造中管件加工虛擬單元調(diào)度問題研究[J].中國造船,2016,57(3):164-175.]

[2] GUREL S, CINCIOGLU D. Rescheduling with controllable processing times for number of disrupted jobs and manufacturing cost objectives[J]. International Journal of Production Research,2015,53(9):2751-2770.

[3] SHEN Xiaoning,YAO Xin. Mathematical modeling and multi-objective evolutionary algorithms applied to dynamic flexible job shop scheduling problems[J]. Information Sciences,2015,298:198-224.

[4] ZHANG Sicheng, WONG T N. Flexible job-shop scheduling/rescheduling in dynamic environment:a hybrid MAS/ACO approach[J]. International Journal of Production Research,2017,55(11):3173-3196.

[5] REZAZADEH H, MAHINI R, ZAREI M. Solving a dynamic virtual cell formation problem by linear programming embedded particle swarm optimization algorithm[J]. Applied Soft Computing,2011,11(3):3160-3169.

[6] MAHDAVI I, AALAEI A, PAYDAR M M, 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.

[7] PAYDAR M M, SAIDI-MEHRABAD M. Revised multi-cho-

ice goal programming for integrated supply chain design and dynamic virtual cell formation with fuzzy parameters[J]. International Journal of Computer Integrated Manufacturing,2015,28(3):251-265.

[8] MORADGHOLI M, PAYDAR M M, MAHDAVI I, et al. A genetic algorithm for a bi-objective mathematical model for dynamic virtual cell formation problem[J]. Journal of Industrial Engineering International,2016,12(3):343-359.

[9] ADIBI M, 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.

[10] JIN Liangliang,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,2017,231(3):490-504.

[11] REZAZADEH H, GHAZANFARI M, SADJADI S J, et al. Linear programming embedded particle swarm optimization for solving an extended model of dynamic virtual cellular manufacturing systems[J]. Journal of Applied Research and Technology,2009,7(1):83-108.

[12] NIKOOFARID E, AALAEI A. Production planning and worker assignment in a dynamic virtual cellular manufacturing system[J]. International Journal of Management Science and Engineering Management,2012,7(2):89-95.

[13] AALAE A, DAVOUDPOUR H. Revised multi-choice goal programming for incorporated dynamic virtual cellular manufacturing into supply chain management:a case study[J]. Engineering Applications of Artificial Intelligence,2016,47:3-15.

[14] GIANGRECO A, PECCEI R. The nature and antecedents of middle manager resistance to change:evidence from an Italian context[J]. The international journal of human resource management,2005,16(10):1812-1829.

[15] LINES B C, SULLIVAN K T, SMITHWICK J B, et al. Overcoming resistance to change in engineering and construction:change management factors for owner organizations[J]. International Journal of Project Management,2015,33(5):1170-1179.

[16] WU S D, STORER R H, CHANG P C. One-machine rescheduling heuristics with efficiency and stability as criteria[J].Computers & Operations Research,1993,20(1):1-14.

[17] VIEIRA G E, HERRMANN J W, LIN E. Rescheduling manufacturing systems:a framework of strategies,policies, and methods[J].Journal of Scheduling,2003,6(1):39-62.

[18] LI Jingsheng,WANG Aimin,TANG Chengtong. Production planning in virtual cell of reconfiguration manufacturing system using genetic algorithm[J]. International Journal of Advanced Manufacturing Technology,2014,74(1/2/3/4):47-64.

[19] BAI Junjie, GONG Yiguang, WANG Ningsheng, et al. Methodology of virtual manufacturing cell formation in reconfigurable manufacturing system for make-to-order manufacturing[J]. Computer Integrated Manufacturing Systems,2009,15(2):313-320(in Chinese).[白俊杰,龔毅光,王寧生,等.面向訂單制造的可重構(gòu)制造系統(tǒng)中虛擬制造單元構(gòu)建技術(shù)[J].計(jì)算機(jī)集成制造系統(tǒng),2009,15(2):313-320.]

[20] LIAN Kunlei,ZHANG Chaoyong,GAO Liang, et al. Integrated process planning and scheduling using an imperialist competitive algorithm[J]. International Journal of Production Research,2012,50(15):4326-4343.

[21] WANG Xiaoqing, TANG Jiafu, GONG Jun, et al. Formation of multi-objective dynamic cells using random weight multi-objective genetic algorithm[J]. Chinese Journal of Management,2008,5(4):516-521(in Chinese).[王曉晴,唐加福,宮 俊,等.基于隨機(jī)權(quán)重多目標(biāo)遺傳算法的多目標(biāo)動(dòng)態(tài)單元構(gòu)建方法[J].管理學(xué)報(bào),2008,5(4):516-521.]

[22] MOHAMMADI M, FORGHANI K. A hybrid method based on genetic algorithm and dynamic programming for solving a bi-objective cell formation problem considering alternative process routings and machine duplication[J].Applied Soft Computing,2017,53:97-110.

[23] GE Xianlong, WANG Xu, XING Lebin. Multi-vehicle scheduling problems and cloud GA based on the dynamic needs[J].Journal of System Engineering,2012,27(6):823-832(in Chinese).[葛顯龍,王 旭,邢樂斌.動(dòng)態(tài)需求的多車型車輛調(diào)度問題及云遺傳算法[J].系統(tǒng)工程學(xué)報(bào),2012,27(6):823-832.]

[24] JIA Guozhu, LUAN Shichao, CHEN Liang, et al. Cell formation problem for virtual cellar manufacturing based on the process modularization[J].Systems Engineering—Theory & Practice,2012,32(10):2111-2118(in Chinese).[賈國柱,欒世超,陳 亮,等.基于流程模塊化的虛擬制造單元構(gòu)建方法[J].系統(tǒng)工程理論與實(shí)踐,2012,32(10):2111-2118.]