考慮優先級的IPPS緊急訂單處理問題研究

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

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

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

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

目前針對訂單不確定問題的研究，通常只考慮一般作業車間調度問題，沒有將工藝規劃和車間調度集成在一起研究。本文針對緊急訂單條件下的IPPS問題，構建訂單優先級評價指標體系，通過灰色關聯度進行評價；基于評價所得的訂單優先級，建立以成本和完工時間的線性加權之和最小為目標的數學模型，并設計遺傳算法進行求解，以保證滿足生產條件下優先級高的訂單按期完工。

1 緊急訂單問題描述

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

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

1.1 灰色關聯分析的訂單優先級確定

灰色關聯方法在解決多目標響應方面具有顯著的優越性[14]。本文采用灰色關聯進行訂單評價時，首先確定理想訂單，然后將未排訂單與其進行比較，關聯程度越高，則對應訂單的重要程度也越高。

根據工藝規劃與車間調度集成生產特性及訂單評價特點，建立訂單優先級評價指標體系，如圖1所示。

圖1 訂單評價指標Fig.1 Order evaluation index system

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

效益型指標的處理方式：

(1)

成本型指標的處理方式：

(2)

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

將所有數據進行歸一化處理后，可以計算灰色關聯系數μa(b)：

(3)

式中：λ為分辨系數，可通過校正λ的值來控制關聯系數的偏差區間，一般λ=0.5；r0b為理想訂單指標所對應的評價參數b的數值。

通過求解關聯系數，得到關聯系數矩陣。為了方便比較，求解關聯系數矩陣的平均值來比較訂單的優先級，該平均值稱為灰色關聯度，可表示為：

(4)

式中：ka為訂單灰色關聯度，其值越高表明對應訂單的優先級越高。

1.2 確定加權灰色關聯度

為了更合理地確定每個訂單的優先級，計算每個訂單的加權灰色關聯度[14]：

(5)

式中：ωa(b)為r0b與rab的關聯系數在指標b點的權重，且：

(6)

加權灰色關聯系數權重確定，定義加權灰色關聯熵H(Ra)：

(7)

式中：pb為每一個比較列的加權灰色關聯系數分布的密度值。

(8)

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

(9)

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

(10)

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

ΓW=b

(11)

式中：

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

W=Γ-1b

(12)

2 考慮訂單優先級的IPPS模型建立

考慮訂單優先級的IPPS問題可以描述為：有多種訂單產品需要在給定交貨期內完成，每種產品可以有多條工藝路線，每道工序可以有多臺可用加工設備。現有新的訂單要安排到生產當中，通過對所有訂單進行重新排產，確定后續各工序的加工順序以及各工序所使用的加工設備，以獲得使目標值最優的加工方案。考慮訂單優先級，對工件的提前完工和拖期完工進行懲罰，以懲罰成本和完工時間的線性加權之和最小為目標函數，建立調度優化模型。

建模參數定義如下：

Jc：表示已有訂單；

Jd：表示緊急訂單；

J：表示所有訂單；

Ji：表示第i個訂單；

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

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

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

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

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

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

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

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

j：表示生產線號，j= 1,2,…,Qi；

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

k：表示設備號，k=1,2,…,m；

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

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

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

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

Yc：表示緊急訂單到達時原訂單的生產時間；

L：表示緊急訂單加工前，原生產計劃所加工的工序數；

Ocjp：表示緊急訂單到達時，工件Jc正在加工的工序數；

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

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

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

Scj1k：表示計劃期初，原始訂單的生產情況；

基于以上參數的定義，考慮訂單的優先級，建立目標函數，如式(13)所示。每個工件何時完工，是否提前和拖期，對企業來講，都會造成資金的損失。式(13)中，θ1和θ2分別表示兩個子目標項權重，表明對兩個子目標的關注程度，例如可設θ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)

式中：α和β分別表示提前和拖期懲罰權重。

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

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

(16)

2) 每個工件的每道工序只能選擇一臺設備進行加工：

(17)

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

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

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

(18)

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

Sijp2kXijZijp2k-Sijp1kXijZijp1k≥

Tijp1kXijZijp1kp1,p2∈[1,Oij]

(19)

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

Cij1k×Xij×Zij1k≥Tij1k×Xij×Zij1k

(20)

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

Cijoijk×Xij×Zijoijk≤Z

(21)

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

Ci=Cijoijk×Xij×Zijoijk

(22)

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

(23)

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

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

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

Sdj1k=0

(24)

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

Scj1k≥0

(25)

當Scj1k= 0時，說明緊急訂單到達時，原生產訂單還未加工；當Scj1k>0時，說明當緊急訂單到達時，原始訂單已經開始加工。

3) 當緊急訂單到達時，原生產訂單已經開始生產，那么原生產訂單已生產的工序數為：

(26)

3 算法求解

IPPS問題本身是一類復雜的NP-hard問題，本文需要考慮插單情況下，將工藝規劃和車間調度問題集成優化[15]，并求出近似最優解，在此設計一種基于多層編碼結構的遺傳算法[16]對該問題進行求解。

1) 編碼

分別對工件、工藝路線、機器和加工時間進行編碼，形成一種多層編碼結構，各層編碼的含義如下。

工件染色體：基因位上的數字表示工件的序號，每個相同基因出現的次數表示工件的工序數。

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

設備染色體：基因位上的數字表示設備編號，基因位上數字要與工件染色體、工藝路線染色體一一對應。

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

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

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

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

2) 適應度函數

本文采用目標函數的倒數作為適應度函數。

3) 選擇操作

采用聯賽選擇和精英選擇相結合的選擇機制。設種群規模為N，聯賽個體選擇總數目為D(D

4) 交叉操作

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

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

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

5) 變異操作

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

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

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

其他鄰域染色體同樣根據上述過程進行變異操作，然后通過評價選擇最優個體，具體算法流程如圖6所示，圖中N為種群規模，G為迭代次數，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 確定訂單優先級

某制造企業在月初接到了3批緊急訂單，考慮到緊急訂單的巨大利潤和企業的產能狀況，決定對其采取接受的態度，在緊急訂單到達之前，企業還有部分訂單有待生產。其中原有訂單為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的可選工藝路線和加工參數分別如圖7和表1所示。圖7中，S、E分別表示開始和結束；①～⑥表示機器號，代表六臺機器。每批訂單包含10個產品，緊急訂單到達時，原訂單尚未進行生產。

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

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

訂單工序編號可選加工設備設備加工時間/min訂單工序編號可選加工設備設備加工時間/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

無量綱化處理后，各個訂單的評價指標值如表2所示。指標值歸一化處理的結果如表3所示。在完成數據歸一化處理后，根據式(3)可計算出訂單的關聯系數，如表4所示。在得出訂單的關聯系數的基礎上，根據式(4)可計算出訂單的灰色關聯度，如表5所示。

表2 訂單的評價指標Tab.2 Evaluating indexes of the orders

表3 歸一化處理數據Tab.3 Normalized processing data

表4 關聯系數表Tab.4 Table of correlation coefficients

表5 訂單灰色關聯度Tab.5 Grey correlation degree of the orders

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

4.2 求解結果及分析

根據建模過程，考慮訂單的優先級，確定每個訂單的生產排產以及每個訂單生產時使用的設備情況，其計算結果可以直觀地通過甘特圖表示。圖8為算法迭代過程圖，圖9為調度結果甘特圖。

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

圖9 調度甘特圖Fig.9 Gantt chart of Scheduling

從調度結果可以看出，訂單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。由結果可知，將工件優先級考慮在調度排產方案內，可以盡可能保證優先級高的工件按期完工。

5 結 論

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

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

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