苗志鴻，楊明順，王雪峰，李 言

(西安理工大學(xué)機(jī)械與精密儀器工程學(xué)院，陜西西安710048)

工藝規(guī)劃與車間調(diào)度集成(integrated process planning and scheduling,IPPS)是在有多個訂單工件需要加工的情況下，每個工件可以有多條工藝路線，每道工序可以有不止一臺的可用加工設(shè)備，通過對工件工藝路線及工序加工設(shè)備的選擇和工件加工工序的排序，得到符合工序約束、滿足特定優(yōu)化目標(biāo)的調(diào)度方案。實際生產(chǎn)過程中，由于訂單的不確定性，經(jīng)常會出現(xiàn)緊急訂單插單的情況[1]。在考慮緊急訂單情況下，如何制定合理有效的生產(chǎn)計劃和調(diào)度方案，盡可能滿足客戶需求和實際生產(chǎn)條件，就顯得十分關(guān)鍵[2-3]。

文獻(xiàn)[4]引入訂單完成難度系數(shù)的概念，提出基于訂單完成難易程度的兩階段多屬性決策方法，以訂單綜合權(quán)重與影響因素權(quán)重偏差最小為目標(biāo)建立優(yōu)化模型，根據(jù)各待插訂單的綜合權(quán)重向量獲得最優(yōu)插單序列。文獻(xiàn)[5]、[6]分別對緊急訂單的插單決策和重排插單方法進(jìn)行研究，提高了生產(chǎn)計劃的靈活性。文獻(xiàn)[7]、[8]針對緊急訂單問題，分別構(gòu)建了供應(yīng)鏈優(yōu)化模型和緊急訂單接單模型，以滿足客戶的需求。針對交貨期緊急程度不同的訂單，文獻(xiàn)[9]提出了一種訂單動態(tài)產(chǎn)品替補算法，并通過實驗進(jìn)行驗證，在滿足生產(chǎn)實際的條件下獲得最優(yōu)解。文獻(xiàn)[10]考慮緊急訂單擾動因素，以完工時間和交貨懲罰為優(yōu)化目標(biāo)，建立動態(tài)仿真模型，實現(xiàn)了并行流水線的動態(tài)調(diào)度。針對混流裝配線上的緊急訂單插入問題，文獻(xiàn)[11]提出一種動態(tài)調(diào)度策略，通過對未上線產(chǎn)品隊列的重調(diào)度以及在制品隊列的動態(tài)調(diào)度，實現(xiàn)緊急訂單的最大程度優(yōu)先交付和生產(chǎn)目標(biāo)的最優(yōu)化。文獻(xiàn)[12]從訂單緊迫程度、客戶重要程度和訂單交貨期等方面考慮，確定訂單加工優(yōu)先級并進(jìn)行排序，為制造訂單的排產(chǎn)提供重要依據(jù)。

目前針對訂單不確定問題的研究，通常只考慮一般作業(yè)車間調(diào)度問題，沒有將工藝規(guī)劃和車間調(diào)度集成在一起研究。本文針對緊急訂單條件下的IPPS問題，構(gòu)建訂單優(yōu)先級評價指標(biāo)體系，通過灰色關(guān)聯(lián)度進(jìn)行評價；基于評價所得的訂單優(yōu)先級，建立以成本和完工時間的線性加權(quán)之和最小為目標(biāo)的數(shù)學(xué)模型，并設(shè)計遺傳算法進(jìn)行求解，以保證滿足生產(chǎn)條件下優(yōu)先級高的訂單按期完工。

1 緊急訂單問題描述

緊急訂單是正常生產(chǎn)計劃以外的訂單，最顯著的特點表現(xiàn)為時間緊迫[13]。制造企業(yè)面對緊急訂單的巨大利潤誘惑，通常都會對其進(jìn)行選擇性的接受。企業(yè)為了滿足緊急訂單的生產(chǎn)，原生產(chǎn)訂單常常會出現(xiàn)暫停、延期或取消的現(xiàn)象，必定會導(dǎo)致原有訂單不能按照原有的方案進(jìn)行排產(chǎn)，從而可能會延遲原訂單交貨期，同時也會額外增加人力、物力等成本，造成客戶滿意度的降低。對企業(yè)而言，訂單的增加、取消、重排會給企業(yè)的生產(chǎn)部門帶來很多不便，使生產(chǎn)的困難系數(shù)增大，甚至需要否定原有生產(chǎn)調(diào)度方案而重新設(shè)置。

針對緊急訂單情況，企業(yè)在正式接受緊急訂單時需要事先進(jìn)行預(yù)判斷處理，首先確定緊急訂單的優(yōu)先級別，并做出是否接受訂單的初步?jīng)Q策；若接受訂單，則預(yù)先編制車間生產(chǎn)計劃，并權(quán)衡多方面因素，確定訂單的加工順序和完工時間，通過計算出來的完工時間等參數(shù)最終判斷出訂單是否滿足客戶要求。因此，為了更好地處理緊急訂單，確定訂單優(yōu)先級成為解決緊急訂單問題的關(guān)鍵。本文采用灰色關(guān)聯(lián)方法進(jìn)行訂單優(yōu)先級的評價。

1.1 灰色關(guān)聯(lián)分析的訂單優(yōu)先級確定

灰色關(guān)聯(lián)方法在解決多目標(biāo)響應(yīng)方面具有顯著的優(yōu)越性[14]。本文采用灰色關(guān)聯(lián)進(jìn)行訂單評價時，首先確定理想訂單，然后將未排訂單與其進(jìn)行比較，關(guān)聯(lián)程度越高，則對應(yīng)訂單的重要程度也越高。

根據(jù)工藝規(guī)劃與車間調(diào)度集成生產(chǎn)特性及訂單評價特點，建立訂單優(yōu)先級評價指標(biāo)體系，如圖1所示。

圖1 訂單評價指標(biāo)Fig.1 Order evaluation index system

在指標(biāo)值的處理過程中，由于所有評價指標(biāo)的單位各不相同，為了便于數(shù)據(jù)的整合，需要對其進(jìn)行無量綱處理。

效益型指標(biāo)的處理方式：

(1)

成本型指標(biāo)的處理方式：

(2)

式中：xab為第a個訂單第b個指標(biāo)的評價值，a=1,2,…,f，b=1,2,…,g；maxxb和minxb分別為第b個指標(biāo)的最大值和最小值；f、g分別為待排訂單數(shù)和評價指標(biāo)數(shù)。

將所有數(shù)據(jù)進(jìn)行歸一化處理后，可以計算灰色關(guān)聯(lián)系數(shù)μa(b)：

(3)

式中：λ為分辨系數(shù)，可通過校正λ的值來控制關(guān)聯(lián)系數(shù)的偏差區(qū)間，一般λ=0.5；r0b為理想訂單指標(biāo)所對應(yīng)的評價參數(shù)b的數(shù)值。

通過求解關(guān)聯(lián)系數(shù)，得到關(guān)聯(lián)系數(shù)矩陣。為了方便比較，求解關(guān)聯(lián)系數(shù)矩陣的平均值來比較訂單的優(yōu)先級，該平均值稱為灰色關(guān)聯(lián)度，可表示為：

(4)

式中：ka為訂單灰色關(guān)聯(lián)度，其值越高表明對應(yīng)訂單的優(yōu)先級越高。

1.2 確定加權(quán)灰色關(guān)聯(lián)度

為了更合理地確定每個訂單的優(yōu)先級，計算每個訂單的加權(quán)灰色關(guān)聯(lián)度[14]：

(5)

式中：ωa(b)為r0b與rab的關(guān)聯(lián)系數(shù)在指標(biāo)b點的權(quán)重，且：

(6)

加權(quán)灰色關(guān)聯(lián)系數(shù)權(quán)重確定，定義加權(quán)灰色關(guān)聯(lián)熵H(Ra)：

(7)

式中：pb為每一個比較列的加權(quán)灰色關(guān)聯(lián)系數(shù)分布的密度值。

(8)

運用拉格朗日極值法計算pb，解得：

(9)

針對每一個比較列xa(b)(a=1,2,…,f)，記ωa(b)為ωb，μa(b)為μb，由式(6)和式(9)可得：

(10)

將式(10)表示為矩陣形式：

ΓW=b

(11)

式中：

反解式(11)，可得權(quán)重向量：

W=Γ-1b

(12)

2 考慮訂單優(yōu)先級的IPPS模型建立

考慮訂單優(yōu)先級的IPPS問題可以描述為：有多種訂單產(chǎn)品需要在給定交貨期內(nèi)完成，每種產(chǎn)品可以有多條工藝路線，每道工序可以有多臺可用加工設(shè)備?，F(xiàn)有新的訂單要安排到生產(chǎn)當(dāng)中，通過對所有訂單進(jìn)行重新排產(chǎn)，確定后續(xù)各工序的加工順序以及各工序所使用的加工設(shè)備，以獲得使目標(biāo)值最優(yōu)的加工方案?？紤]訂單優(yōu)先級，對工件的提前完工和拖期完工進(jìn)行懲罰，以懲罰成本和完工時間的線性加權(quán)之和最小為目標(biāo)函數(shù)，建立調(diào)度優(yōu)化模型。

建模參數(shù)定義如下：

Jc：表示已有訂單；

Jd：表示緊急訂單；

J：表示所有訂單；

Ji：表示第i個訂單；

Ci：表示訂單Ji的完工時間；

di：表示訂單Ji的交貨期；

Qi：表示訂單Ji所有可能的工藝路線的數(shù)量；

Rij：表示訂單Ji的第j條可行的工藝路線；

Oij：表示工藝路線Rij的所有工序數(shù)目；

Oijp：表示訂單Ji的第j條工藝路線的第p道工序；

Cijpk：表示工序Oijp在設(shè)備k上的最早完工時間；

i：表示工件號，i=1,2,…,n；

j：表示生產(chǎn)線號，j= 1,2,…,Qi；

p：表示工序號，p=1,2,…,Oij；

k：表示設(shè)備號，k=1,2,…,m；

Z：表示完工時間和提前拖期懲罰成本歸一化后的線性加權(quán)之和；

T：表示所有訂單的完工時間；

Y：表示考慮優(yōu)先級的所有訂單的提前拖期懲罰成本；

αi：表示訂單Ji提前完工的懲罰成本；

Yc：表示緊急訂單到達(dá)時原訂單的生產(chǎn)時間；

L：表示緊急訂單加工前，原生產(chǎn)計劃所加工的工序數(shù)；

Ocjp：表示緊急訂單到達(dá)時，工件Jc正在加工的工序數(shù)；

Sijpk：表示工序Oijp在設(shè)備k上的開始加工時間；

Tijpk：表示工序Oijp在設(shè)備k上的加工時間；

Sdj1k：表示計劃期初，緊急訂單的加工完成工序數(shù)；

Scj1k：表示計劃期初，原始訂單的生產(chǎn)情況；

基于以上參數(shù)的定義，考慮訂單的優(yōu)先級，建立目標(biāo)函數(shù)，如式(13)所示。每個工件何時完工，是否提前和拖期，對企業(yè)來講，都會造成資金的損失。式(13)中，θ1和θ2分別表示兩個子目標(biāo)項權(quán)重，表明對兩個子目標(biāo)的關(guān)注程度，例如可設(shè)θ1=1，θ2=1.1。

(13)

T=Sijpk+Tijpk×Xij×Zijpk

?i∈[1,n],?j∈[1,Qi],?p∈[1,Oij],

?k∈[1,m]

(14)

(15)

式中：α和β分別表示提前和拖期懲罰權(quán)重。

考慮工件提前完工時，對企業(yè)所造成的主要是庫存成本，而工件拖期完工造成的懲罰成本遠(yuǎn)比庫存成本大，例如，可設(shè)置α=1，β=1.25，即當(dāng)工件提前1 min完工時，提前懲罰成本為1元；當(dāng)工件拖期1 min完工時，拖期懲罰成本為1.25元。工件在加工過程中所要滿足的約束條件為：

1) 每個工件在加工過程中只能選擇一條工藝路線：

(16)

2) 每個工件的每道工序只能選擇一臺設(shè)備進(jìn)行加工：

(17)

3) 同一工件的不同工序不能同時加工，在不同設(shè)備k1、k2上加工時：

Sijpk1XijZijpk1-Sij(p-1)k2XijZij(p-1)k2≥

Tij(p-1)k2XijZij(p-1)k2k1,k2∈[1,m]

(18)

4) 當(dāng)工件Ji的工序Oijp1在Oijp2之前加工，要使同一機(jī)器在同一時刻只能加工一道工序，則應(yīng)滿足：

Sijp2kXijZijp2k-Sijp1kXijZijp1k≥

Tijp1kXijZijp1kp1,p2∈[1,Oij]

(19)

5) 針對工件Ji的第j條工藝路線的第一道工序，即當(dāng)工序p=1時：

Cij1k×Xij×Zij1k≥Tij1k×Xij×Zij1k

(20)

6) 針對工件Ji的第j條工藝路線的最后一道工序，即當(dāng)工序p=Oij：

Cijoijk×Xij×Zijoijk≤Z

(21)

7) 每個工件的完工時間：

Ci=Cijoijk×Xij×Zijoijk

(22)

8) 所有工序的加工時間均大于等于0：

(23)

式(16)表示工件Ji只能選擇一條柔性工藝路線進(jìn)行加工；式(17)為機(jī)器約束，每道工序只能選擇一臺設(shè)備進(jìn)行加工；式(18)為工件工序約束，即同一時刻只能加工給定工件的一道工序；式(19)表示各個工件每道工序之間只能有一種優(yōu)先級，而且一臺設(shè)備同一時刻只能加工一道工序；式(20)和(21)表示各個工件必須按指定工序順序進(jìn)行加工；式(22)表示每個工件的完工時間；式(23)為加工時間約束，每個工件的開始加工時間、加工時間以及完工時間都必須大于等于零。

訂單在加工過程中除了滿足上述約束條件外，當(dāng)有新訂單投入生產(chǎn)時，還需滿足以下約束條件：

1) 在計劃期初緊急訂單的加工完成工序數(shù)為0：

Sdj1k=0

(24)

2) 用于判斷在計劃期初，原始訂單的生產(chǎn)情況：

Scj1k≥0

(25)

當(dāng)Scj1k= 0時，說明緊急訂單到達(dá)時，原生產(chǎn)訂單還未加工；當(dāng)Scj1k>0時，說明當(dāng)緊急訂單到達(dá)時，原始訂單已經(jīng)開始加工。

3) 當(dāng)緊急訂單到達(dá)時，原生產(chǎn)訂單已經(jīng)開始生產(chǎn)，那么原生產(chǎn)訂單已生產(chǎn)的工序數(shù)為：

(26)

3 算法求解

IPPS問題本身是一類復(fù)雜的NP-hard問題，本文需要考慮插單情況下，將工藝規(guī)劃和車間調(diào)度問題集成優(yōu)化[15]，并求出近似最優(yōu)解，在此設(shè)計一種基于多層編碼結(jié)構(gòu)的遺傳算法[16]對該問題進(jìn)行求解。

1) 編碼

分別對工件、工藝路線、機(jī)器和加工時間進(jìn)行編碼，形成一種多層編碼結(jié)構(gòu)，各層編碼的含義如下。

工件染色體：基因位上的數(shù)字表示工件的序號，每個相同基因出現(xiàn)的次數(shù)表示工件的工序數(shù)。

工藝路線染色體：基因位上的數(shù)字表示工件所選擇的加工工藝路線，遺傳變異過程中，同一工件所選擇的工藝路線相同，且每個工件只能選擇一條可行工藝路線進(jìn)行加工。

設(shè)備染色體：基因位上的數(shù)字表示設(shè)備編號，基因位上數(shù)字要與工件染色體、工藝路線染色體一一對應(yīng)。

加工時間的染色體：基因位上的數(shù)值表示某一工件在特定加工工藝路線下某道工序所用的加工時間。

例如，對于A、B、C3個工件，共有6條工藝路線和4臺加工設(shè)備，則其多層編碼如圖2所示。

圖2 編碼后的染色體Fig.2 Encoded chromosomes

對于工件層而言，C出現(xiàn)三次，分別表示工件C的第一道、第二道和第三道工序；對應(yīng)其他編碼層，分別表示工件C選擇第5條工藝路線，第1道工序用設(shè)備2加工，其加工時間為5。

2) 適應(yīng)度函數(shù)

本文采用目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)。

3) 選擇操作

采用聯(lián)賽選擇和精英選擇相結(jié)合的選擇機(jī)制。設(shè)種群規(guī)模為N，聯(lián)賽個體選擇總數(shù)目為D(D

4) 交叉操作

為避免產(chǎn)生非法解，采用一種優(yōu)先交叉策略對個體進(jìn)行交叉。以工件層中的工件C為例進(jìn)行說明，工藝路線層、設(shè)備層和加工時間層隨工件層變化，同時發(fā)生交叉操作，如圖3所示。

需要指出的是，由于不同工件選擇的工藝路線不同，不同工藝路線對應(yīng)的工序數(shù)目也不同，父代染色體交叉操作后，子代染色體的長度、基因位數(shù)可能會發(fā)生變化。

圖3 染色體交叉Fig.3 Chromosomes overlapping

5) 變異操作

采用基于鄰域搜索的變異操作。以工件染色體為例，從父代染色體中選擇u個基因且每個基因必須為不同的值。取u=3，并選擇基因位置1、2、5，然后對所有鄰域染色體適應(yīng)度進(jìn)行評價，選擇最優(yōu)個體作為子代染色體，如圖4所示。

圖4 染色體變異Fig.4 Chromosome variation

工件層發(fā)生變異時，工藝路線、加工時間和設(shè)備染色體(機(jī)器層)也發(fā)生相應(yīng)的改變，從而可能導(dǎo)致不合理解的產(chǎn)生。在此情況下，對不合理工件進(jìn)行重新分配，使其擁有合理的工藝路線、機(jī)器和時間。例如，對第一條鄰域染色體而言，將其父代染色體工件C所在的列提取出來，并復(fù)制到鄰域染色體中工件C所在的位置上，為工件C匹配正確的加工時間。父代染色體編碼如圖5(a)所示，變異后第一條鄰域染色體編碼如圖5(b)所示，修正后的鄰域染色體編碼如圖5(c)所示。同理，從機(jī)器層中隨機(jī)產(chǎn)生變異位置，假設(shè)該變異發(fā)生在位置6上，然后對其匹配正確的加工時間，則可得到新的子代，其變異結(jié)果如圖5(d)所示。

其他鄰域染色體同樣根據(jù)上述過程進(jìn)行變異操作，然后通過評價選擇最優(yōu)個體，具體算法流程如圖6所示，圖中N為種群規(guī)模，G為迭代次數(shù)，Pc為個體交叉概率Pc∈(0,1)，Pm為個體變異概率Pm∈(0,1)。

圖5 各層染色體變異過程Fig.5 Chromosomal variation in each layer

圖6 遺傳算法流程圖Fig.6 Genetic algorithm flow chart

4 實例驗證

4.1 確定訂單優(yōu)先級

某制造企業(yè)在月初接到了3批緊急訂單，考慮到緊急訂單的巨大利潤和企業(yè)的產(chǎn)能狀況，決定對其采取接受的態(tài)度，在緊急訂單到達(dá)之前，企業(yè)還有部分訂單有待生產(chǎn)。其中原有訂單為1、2、3，緊急訂單為4、5、6。訂單1、2、3、4、5、6的交貨期分別為140 min、155 min、105 min、120 min、100 min、110 min，訂單1、2、3、4、5、6的可選工藝路線和加工參數(shù)分別如圖7和表1所示。圖7中，S、E分別表示開始和結(jié)束；①～⑥表示機(jī)器號，代表六臺機(jī)器。每批訂單包含10個產(chǎn)品，緊急訂單到達(dá)時，原訂單尚未進(jìn)行生產(chǎn)。

圖7 各訂單可選工藝路線Fig.7 Optional process route for each order

表1 訂單各道工序可選機(jī)器及其加工時間
Tab.1 Order optional machine and machining time for each process

訂單工序編號可選加工設(shè)備設(shè)備加工時間/min訂單工序編號可選加工設(shè)備設(shè)備加工時間/min111,2,52,1,221,3,52,3,232,5,62,3,341,43,3.553,52.5,262,34,3411,2,52.5,3,321,3,52,3,232,5,63,2,341,42,3.553,52,3211,2,53,2.5,321,41.5,233,52.5,441,42.5,252,5,64,3,563,56,4511,2,53,2.5,221,42.5,2.533,52.5,441,42.5,255,64,361,3,53,6,5311,2,54,4.5,321,44.5,532,34,642,62,456,43,3.5611,2,53,4.5,321,2,44.5,3,532,34,341,2,62,2,456,45,3.5

無量綱化處理后，各個訂單的評價指標(biāo)值如表2所示。指標(biāo)值歸一化處理的結(jié)果如表3所示。在完成數(shù)據(jù)歸一化處理后，根據(jù)式(3)可計算出訂單的關(guān)聯(lián)系數(shù)，如表4所示。在得出訂單的關(guān)聯(lián)系數(shù)的基礎(chǔ)上，根據(jù)式(4)可計算出訂單的灰色關(guān)聯(lián)度，如表5所示。

表2 訂單的評價指標(biāo)Tab.2 Evaluating indexes of the orders

表3 歸一化處理數(shù)據(jù)Tab.3 Normalized processing data

表4 關(guān)聯(lián)系數(shù)表Tab.4 Table of correlation coefficients

表5 訂單灰色關(guān)聯(lián)度Tab.5 Grey correlation degree of the orders

根據(jù)表5中求解出的訂單灰色關(guān)聯(lián)度的大小關(guān)系，即k5>k4>k6>k3>k1>k2，可以確定訂單優(yōu)先級順序依次為5、4、6、3、1、2，據(jù)此考慮對所有緊急訂單都采取接受的態(tài)度。

4.2 求解結(jié)果及分析

根據(jù)建模過程，考慮訂單的優(yōu)先級，確定每個訂單的生產(chǎn)排產(chǎn)以及每個訂單生產(chǎn)時使用的設(shè)備情況，其計算結(jié)果可以直觀地通過甘特圖表示。圖8為算法迭代過程圖，圖9為調(diào)度結(jié)果甘特圖。

圖8 算法迭代圖Fig.8 Iterative graph

圖9 調(diào)度甘特圖Fig.9 Gantt chart of Scheduling

從調(diào)度結(jié)果可以看出，訂單1、2、3、4、5、6的完工時間分別為150 min、150 min、115 min、120 min、100 min、110 min，所有訂單的最大完工時間為150 min。其中緊急訂單都按期完工，訂單1、3拖期完工，兩者都拖期10 min，訂單2提前完工5 min。由結(jié)果可知，將工件優(yōu)先級考慮在調(diào)度排產(chǎn)方案內(nèi)，可以盡可能保證優(yōu)先級高的工件按期完工。

5 結(jié) 論

1) 分析了IPPS環(huán)境下的插單問題，給出了一種基于訂單優(yōu)先級的處理策略，考慮訂單評價的客戶重要性、訂單收入、原材料的可替代性、工藝復(fù)雜程度等7個指標(biāo)，建立了指標(biāo)體系，并利用加權(quán)灰色關(guān)聯(lián)度進(jìn)行訂單優(yōu)先級的評定。

2) 以訂單提前或超期引起的懲罰成本和完工時間的線性加權(quán)之和最小為目標(biāo)函數(shù)，考慮設(shè)備約束、工序約束等條件，建立了考慮訂單優(yōu)先級的IPPS模型；針對模型求解的復(fù)雜性，設(shè)計了一種包含工件層、工藝路線層、設(shè)備層和加工時間層的多層編碼結(jié)構(gòu)的遺傳算法，并對算法中的各個模塊進(jìn)行了詳細(xì)設(shè)計。

3) 通過實例驗證了所建模型的正確性和求解算法的有效性。結(jié)果表明，將訂單優(yōu)先級考慮到IPPS問題當(dāng)中，可以盡可能保證訂單優(yōu)先級高的訂單按期完工，因此將灰色關(guān)聯(lián)方法和遺傳算法結(jié)合，可以很好地解決考慮訂單優(yōu)先級的IPPS問題。