基于網(wǎng)絡(luò)圖拓?fù)浣Y(jié)構(gòu)的MILP模型求解智能制造系統(tǒng)中的工藝規(guī)劃問題

劉齊浩，李新宇*，高亮

State Key Laboratory of Digital Manufacturing Equipment and Technology, School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China

1. 引言

智能制造包含智能制造技術(shù)和智能制造系統(tǒng)[1-3]。智能工藝規(guī)劃（process planning, PP）屬于重要的智能制造技術(shù)，在智能制造系統(tǒng)中扮演著重要的角色[4,5]。PP能夠有效地縮短生產(chǎn)周期，提高產(chǎn)品質(zhì)量，并進(jìn)一步降低資源和能源的消耗[6]。因此，PP在工業(yè)應(yīng)用與研究中獲得了較多的關(guān)注。然而，因為PP問題內(nèi)部存在著大量的柔性，導(dǎo)致在實際生產(chǎn)場景中很難得到最優(yōu)的工藝規(guī)劃路線[7]。

解決傳統(tǒng)的PP問題通常需要三個步驟：工藝選擇、資源分配和工序排序[5]。通過第一步的工藝選擇來確定不同加工特征所需要的工藝及工序，并基本確定工藝路線的總長度。然后，通過分配機器、刀具等資源，來確定各工序的加工資源分配，預(yù)獲取相關(guān)加工參數(shù)，例如加工時間等。最關(guān)鍵的工序排序一般是最后執(zhí)行，且排序過程必須遵循該工件工藝網(wǎng)絡(luò)圖中的優(yōu)先關(guān)系約束[8]。例如，粗銑工序和粗磨工序必須安排在精銑工序和精磨工序之前執(zhí)行，鏜孔工序必須排在鉆工工序后[9]。

PP問題已經(jīng)被證明是非確定性多項式時間困難（nondeterministic polynomial-time-hard, NP-hard）問題[6,10]，這也意味著僅僅依靠傳統(tǒng)的梯度下降法、圖論法和仿真方法很難實現(xiàn)PP問題的求解。因此，多數(shù)研究者試圖引入元啟發(fā)式算法來求解PP問題[11]。當(dāng)前主要的求解方法包括遺傳算法（genetic algorithm, GA）[7,12]、禁忌搜索算法（tabu search, TS）[13]、粒子群優(yōu)化算法（particle swarm optimization, PSO）[8]、蟻群優(yōu)化算法（ant colony optimization, ACO）[14]和蜜蜂配合優(yōu)化算法（honey-bees mating optimization, HBMO）[10]。這些算法能夠在較短時間內(nèi)獲得近優(yōu)解，更側(cè)重算法的求解效率而不是解的最優(yōu)性。

在此研究背景下，大部分公開PP問題的最優(yōu)解至今還未找到[8,15]。其中一個重要的原因是當(dāng)前研究更多關(guān)注的是如何提高智能算法的性能，而不是去研究問題的數(shù)學(xué)模型，尤其是混合整數(shù)線性規(guī)劃（mixed- integer linear programming, MILP）模型[14]。有效的MILP模型能夠通過數(shù)學(xué)規(guī)劃求解器求解，如CPLEX、Gurobi等，并在一定條件下穩(wěn)定地獲得最優(yōu)解。但是，模型的求解效率與問題的規(guī)模相關(guān)，隨著問題規(guī)模的逐漸增大，模型的求解效率會迅速降低，甚至在相當(dāng)長的計算時間內(nèi)無法獲得可行解[16]。這也是當(dāng)前PP的研究重點不在模型上的重要原因。此外，當(dāng)前PP的MILP研究還處于一種“妥協(xié)”狀態(tài)，即當(dāng)前模型都是基于工藝特征建立的[8,14,17]。這種類型的模型通過將原始工藝圖轉(zhuǎn)換成工藝特征表來簡化表達(dá)，但是這種轉(zhuǎn)化會改變工藝網(wǎng)絡(luò)圖的原始信息，甚至改變原問題的解空間結(jié)構(gòu)而導(dǎo)致最優(yōu)解的丟失（該部分的討論將在第3.3節(jié)展開）。當(dāng)然，也有一些建模方法能夠規(guī)避上述情況的發(fā)生，但它需要復(fù)雜的前序處理操作[18]，而當(dāng)工件的工藝網(wǎng)絡(luò)圖較為復(fù)雜時，這種前序處理操作會非常繁瑣費時。

為了添補當(dāng)前研究工作的空白，本文提出了一個全新的基于PP網(wǎng)絡(luò)圖拓?fù)浣Y(jié)構(gòu)的MILP數(shù)學(xué)模型，本文的主要貢獻(xiàn)如下：

（1）與現(xiàn)有研究中的模型相比，本文所提的基于網(wǎng)絡(luò)圖OR節(jié)點的MILP模型不需要任何工藝特征轉(zhuǎn)換或前序處理操作。

（2）工序的優(yōu)先關(guān)系在本文中進(jìn)行了詳細(xì)的討論，并提出了三種優(yōu)先關(guān)系模型來分析論述工序的優(yōu)先關(guān)系約束。

（3）通過通用代數(shù)建模系統(tǒng)（general algebraic mode- ling system, GAMS）調(diào)用CPLEX求解器對所提模型進(jìn)行求解，成功得到了現(xiàn)有文獻(xiàn)中大部分開放問題的最優(yōu)解[8,15,16]。

本文的后續(xù)部分組織如下：第2節(jié)介紹相關(guān)的研究；第3節(jié)介紹所提的模型細(xì)節(jié)和上文所提的相關(guān)分析；第4節(jié)是驗證實驗部分，驗證所提模型的優(yōu)越性；第5節(jié)則進(jìn)行了總結(jié)和對未來工作的展望。

2. 相關(guān)理論與研究介紹

關(guān)于PP問題的研究主要可以分為兩類：算法相關(guān)的研究與模型相關(guān)的研究。Xu等[6]和Leo Kumar [4]在PP問題上已經(jīng)做了很全面的綜述工作。智能算法，如GA、模擬退火（simulated annealing, SA）算法、TS算法和PSO算法已經(jīng)在解決PP問題上展現(xiàn)出了足夠的優(yōu)勢，并且已經(jīng)廣泛地應(yīng)用到該問題的求解中。為了求解復(fù)雜棱柱形零件的PP問題，Li等[19]提出了一種由GA和SA組成的混合算法。通過基于Hamming距離的解搜索和選擇策略，該混合算法的局部搜索能力得到了有效的加強。Hua等[20]基于GA提出了一種合成算法來搜索PP問題的最優(yōu)或近優(yōu)解。Li等[15]提出了一種有效的基因編程（genetic programming, GP）算法，來操作工藝網(wǎng)絡(luò)圖中的OR節(jié)點支路。考慮刀具和進(jìn)給速度等制造資源的選擇，Shin等[21]提出了一種共生進(jìn)化算法來優(yōu)化三個目標(biāo)，包括機器負(fù)載平衡、零件移動最小化和換刀次數(shù)最小化。Wang等[22]提出了一種包含兩類局部搜索策略的PSO算法求解PP問題，也取得了不錯的效果。后來，Li等[8]也提出了改進(jìn)的PSO算法來求解考慮工件轉(zhuǎn)運時間的PP問題。Liu等[14]將ACO算法與問題的約束矩陣和狀態(tài)矩陣結(jié)合，并成功應(yīng)用于求解兩類柱狀零件的PP問題。

雖然智能算法解決PP問題方面取得了一些成果，但由于元啟發(fā)式算法不能保證解的最優(yōu)性，所以在大多數(shù)現(xiàn)有PP實例中，解的質(zhì)量還可以通過數(shù)學(xué)模型進(jìn)一步提高甚至優(yōu)化到最優(yōu)。此外，數(shù)學(xué)模型作為一種問題的表述方法，能夠幫助研究者進(jìn)一步地理解和探索問題[23]。因此，進(jìn)行PP問題的模型相關(guān)研究意義深遠(yuǎn)。Floudas和Lin [24]基于時間表示方法，分析研究了幾種PP的混合整數(shù)規(guī)劃（mixed-integer programming, MIP）模型，并提出了幾種有效的優(yōu)化方法來提高模型的計算效率。著眼于PP與調(diào)度的互補屬性，Li等[25]建立了PP與調(diào)度集成的數(shù)學(xué)模型。Xia等[26]基于工藝特征的思路提出了可重構(gòu)PP問題的數(shù)學(xué)模型。同樣是基于工藝特征的方式，Jin和Zhang [16]建立了考慮機器間轉(zhuǎn)運約束的PP問題的數(shù)學(xué)模型。

據(jù)目前調(diào)研所知，現(xiàn)有的PP問題數(shù)學(xué)模型都是基于工藝特征建立的[8,14,17]。雖然這種表示方法能夠描述大部分類型工件的工藝，但是仍然不可避免地加入一些本來不存在的工序緊前關(guān)系約束[16]。與之相比，本文所提的基于網(wǎng)絡(luò)圖的表示法比基于特征的表示法更能表示原有的工藝信息，而不會添加額外信息。本文提出了一個直接基于工藝網(wǎng)絡(luò)圖拓?fù)浣Y(jié)構(gòu)的MILP模型，該模型能夠描述所有類型的PP制造柔性，而不添加或遺漏任何約束。通過求解所提模型，成功獲得了一些著名數(shù)據(jù)集的新最優(yōu)解。

3. 工藝規(guī)劃MILP數(shù)學(xué)模型

3.1. 問題描述

圖1. 工藝網(wǎng)絡(luò)圖示例。OR1、OR2、JOIN1、JOIN2分別表示1號OR節(jié)點、2號OR節(jié)點、1號JOIN節(jié)點和2號JOIN節(jié)點。

PP問題中包含的柔性類型有工藝柔性、機器選擇柔性和工序序列柔性，常用的表示方法有Petri網(wǎng)絡(luò)[27]、工藝特征表[28]、AND/OR圖和網(wǎng)絡(luò)圖等[29,30]。圖1為某工件的制造柔性通過網(wǎng)絡(luò)圖表示的示例，網(wǎng)絡(luò)圖由5類節(jié)點構(gòu)成：虛擬的開始節(jié)點和終止節(jié)點，表示加工的開始和結(jié)束；表示工序的中間節(jié)點；以及配合起來表示工藝約束的OR節(jié)點和JOIN節(jié)點[15]。中間節(jié)點包含工序序號、可選加工機器號以及對應(yīng)的加工時間三種信息。例如，中間節(jié)點6表示的是工序6能夠在序號為3、7和13的機器上加工，且對應(yīng)的加工時間分別為44、48和49。這里的加工時間單位按照原始數(shù)據(jù)被省去。被箭頭鏈接的兩兩工序之間有著優(yōu)先關(guān)系約束[21]，如圖1中節(jié)點2和3之間的箭頭表示工序2必須在工序3之前加工。而沒有箭頭鏈接的工序之間不存在這種優(yōu)先關(guān)系約束。此外，介于一對OR節(jié)點和JOIN節(jié)點的支路只能有一條被選擇，包含在支路里面的工序配合其他工序組成一條可行的加工路線[29]。以圖1為例，如果節(jié)點OR1和JOIN1之間選擇支路2 → 3，節(jié)點OR2和JOIN2之間選擇工序7，則其中一條可行的加工路線可以是：1 → 2 → 3 → 5 → 6 → 7 → 9 → 10。

3.2. 工序間的優(yōu)先關(guān)系

根據(jù)模型中0-1二元變量的定義，PP問題的建模方式可以分為三種[31]：

變量θjt會引入比其他兩種類型更多的派生變量和約束，因此現(xiàn)有的PP問題建模研究中鮮少提及。基于位置的變量ρjt描述的是工序在一條序列中的位置序號[16,32,33]，被較多地應(yīng)用在現(xiàn)有的模型相關(guān)研究[24,34,35]中。作為對比，本文所提的MILP模型則是首個基于第三種類型變量qjj′建立的模型。

以圖2中網(wǎng)絡(luò)圖表示的工件為例，其中一條可行的加工路線為：1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9。因為工序1在其他所有工序的前面加工，所以根據(jù)變量q1j′的定義可以得出：q1j′= 1，其中j′ = 2, …, 9。工序2在工序3到工序9前面加工，因此q2j′= 1，其中j′ = 3, …, 9。 以此類推，矩陣Q = [qjj′]中等于1的變量總數(shù)為(n - 1)n/2， 其中n表示工序總數(shù)，同樣也等于該工序序列的總長度。圖3展示了由工序序列生成Q矩陣的過程。

在一條已經(jīng)確定加工順序的序列中，任意兩兩工序之間都存在一個優(yōu)先關(guān)系。因此，可以通過一個n × n矩陣來表示一條工序序列中包含的所有優(yōu)先關(guān)系，即上述的矩陣Q。矩陣Q可以被看作是工序序列優(yōu)先關(guān)系的完全表達(dá)矩陣（completely expressing matrix, CEM），因為它包含了一條序列中所有的優(yōu)先關(guān)系。通過觀察和分析發(fā)現(xiàn)，CEMQ的特征約束可以總結(jié)如下：

（1）CEMQ對角線上的元素都等于0。

（2）關(guān)于對角線對稱的兩元素之和等于1。

圖2. 工藝網(wǎng)絡(luò)圖實例。

（3）任意兩列元素之和互不相等。

式（1）指代的是優(yōu)先關(guān)系只存在于兩個不同工序之間。式（2）指代的是兩工序之間只能存在一種優(yōu)先關(guān)系。CEMQ中的每列元素之和等于該列對應(yīng)工序在序列中所處的位置序號，根據(jù)位置的唯一性推斷出式（3）成立。CEMQ矩陣包含了一條序列的所有優(yōu)先關(guān)系，可以根據(jù)序列的CEMQ來判斷該序列是否滿足網(wǎng)絡(luò)圖中的優(yōu)先關(guān)系約束。

引入符號sjj′來表示圖2中網(wǎng)絡(luò)圖的優(yōu)先約束：

根據(jù)定義，對應(yīng)的矩陣S= [sjj′]如圖4所示，其中S矩陣中的“1”對應(yīng)于網(wǎng)絡(luò)圖中的箭頭，表示優(yōu)先關(guān)系約束。如果一條工序序列滿足工藝網(wǎng)絡(luò)圖中的優(yōu)先約束，則其序列的CEMQ應(yīng)該與矩陣S有如下關(guān)系：

矩陣S可以從網(wǎng)路圖中生成，但是在序列未定前，CEMQ則是未知的。由此，式（4）是用來約束未知的CEMQ的。

圖3. 優(yōu)先關(guān)系矩陣轉(zhuǎn)換示例。

圖4. 網(wǎng)絡(luò)圖中的優(yōu)先約束和對應(yīng)的矩陣S。

CEM中等于“1”的元素數(shù)量為(n- 1)n/2，但是并不意味著定義一條工序序列需要(n- 1)n/2個 “1”。實際上，定義一條序列所需的最小“1”總數(shù)為n- 1個。以序列1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9為例，只需要定義兩兩相鄰的元素之間的優(yōu)先關(guān)系，就可以確定該 序 列，即q12、q23、q34、q45、q56、q67、q78、q89等 于1即可。從這點出發(fā)，定義一個包含等于1的變量數(shù)最少的矩陣V = [vjj′]，有利于簡化工序優(yōu)先關(guān)系的研究。基于上述討論，矩陣可看作是精確表達(dá)矩陣（exactly expressing matrix, EEM），包含定義一條工序序列所需要的最精確和最少的等于“1”的變量。上述工序序列的EEM V如圖5所示。

因為EEM V包含所有緊鄰工序之間的優(yōu)先關(guān)系約束，所以EEM V同時也能被稱作緊前關(guān)系矩陣。根據(jù)直接緊鄰關(guān)系，可以較為容易地通過依次讀取EEM V中等于1的元素來獲得一條工藝路線，完成矩陣到序列的轉(zhuǎn)化。EEM V的特征約束如下：

（1）EEM V中等于1的元素總數(shù)等于n - 1。

（2）EEM V的行和列中最多只能有1個元素等于1。

圖5. 序列的精確表達(dá)矩陣。

（3）CEM Q與EEM V之間的關(guān)系如下。

EEM V是CEM Q的簡化表達(dá)形式，并且二者都能夠定義一條唯一的工序序列。由于矩陣S中對序列優(yōu)先關(guān)系的不完整表示，使其不能定義一條唯一的工序序列。因此，在本文中矩陣S也可以被稱作優(yōu)先關(guān)系的部分表達(dá)矩陣（partly expressing matrix, PEM）。不難得出，一般情況下不止一條工序序列可以滿足由PEM S表達(dá)的優(yōu)先關(guān)系約束。CEM Q、EEM V、PEM S的對比如圖6所示。

3.3. 關(guān)于工藝特征表示法與工藝網(wǎng)絡(luò)圖表示法的討論

現(xiàn)有文獻(xiàn)[8,16]中關(guān)于PP問題的模型都是基于工藝特征表示法建立的，如圖7（a）中的以工藝特征表表示的算例。實際上，該算例是由文獻(xiàn)[29]中的第18個算例通過轉(zhuǎn)換得到的，如圖7（b）所示。圖7（a）、（b）表達(dá)的是同一件工件的工藝信息。

在特征表[8,16]中，工藝特征F2、F5和F9有著可選的加工工序或加工工序集合，分別與網(wǎng)絡(luò)圖中的三對OR及JOIN節(jié)點相對應(yīng)。然而不同的是，特征表中同一工藝特征下的工序集合會被緊前關(guān)系約束，而這種約束在原始的網(wǎng)絡(luò)圖中卻是不存在的。例如，如果工藝特征F2選擇了通過工序集合O4～O5來實現(xiàn)，那么在生成的工序序列中O5必須在O4完成加工后立刻開始加工。但是，根據(jù)網(wǎng)絡(luò)圖圖7（b）傳達(dá)的工藝信息，是不存在這種立刻開始加工的必要的。這種多余的捆綁可能改變原始的解空間結(jié)構(gòu)，導(dǎo)致失去找到最優(yōu)解的可能；而實際上這個算例就是如此。表1分別展示了通過基于特征的模型和基于網(wǎng)絡(luò)圖的模型所求得的最優(yōu)解工序序列，其中帶數(shù)字下標(biāo)的字母M表示的是工序的加工機器號。

觀察表1，由基于工藝網(wǎng)路圖模型得到的序列可知，工序O4和O5之間不存在緊前關(guān)系約束。此外，基于工藝網(wǎng)絡(luò)圖模型獲得的最優(yōu)解356優(yōu)于基于工藝特征模型獲得的最優(yōu)解357。其實，因為受到了緊前關(guān)系的約束，通過工藝特征構(gòu)建的問題解空間是原始網(wǎng)絡(luò)圖表示的解空間的子集。由此可知，直接根據(jù)工藝網(wǎng)絡(luò)圖建立問題的模型要好于基于工藝特征表的方式。

圖6. 三類優(yōu)先關(guān)系矩陣。（a）CEM Q；（b）EEM V；（c）PEM S。

圖7. 同一算例的兩種表現(xiàn)形式。（a）工藝特征表；（b）工藝網(wǎng)絡(luò)圖。

表1 工藝特征模型與工藝網(wǎng)絡(luò)圖模型求得的最優(yōu)解

通過工藝特征表表示的PP問題的工藝柔性是通過同一加工特征下可選的工序和工序集合實現(xiàn)的，而工藝網(wǎng)絡(luò)圖表示的PP問題則是通過選擇連接在OR節(jié)點上的支路實現(xiàn)。每條支路對應(yīng)于工藝柔性的一種選擇。如圖8所示，OR節(jié)點與JOIN節(jié)點的序號是自上而下、自左而右的。如果選擇了OR節(jié)點1的支路1，那么工序2、3和4則一定會被選擇，此時無論OR節(jié)點2選擇支路1還是2，工序5、6、7和8都不會被選擇。這是因為，工序5、6、7和8不僅被OR節(jié)點2控制，還被OR節(jié)點1的支路2所控制，而OR節(jié)點1的支路2并沒有被選擇。OR節(jié)點支路選擇有效的前提是該節(jié)點位于的支路被選擇。

引入二進(jìn)制參數(shù)wjrl來描述OR節(jié)點對工序節(jié)點的控制功能，參數(shù)wjrl定義如下：

以圖8為例，對應(yīng)的wjrl參數(shù)值如表2所示。

表2 參數(shù)wjrl值

綜上，可將OR節(jié)點的控制功能歸納如下：當(dāng)且僅當(dāng)控制工序j的所有支路都被選擇，工序j才會被選擇；否則，只要當(dāng)其中一條控制支路未被選擇，工序j就不會被選擇。引入0-1二元變量url來描述OR節(jié)點支路的選擇狀態(tài)，同時引入0-1二元變量xj來描述工序的選擇狀態(tài)。變量url和xj的定義如下：

第3.4節(jié)介紹的模型是基于上述兩種變量url和xj以及參數(shù)wjrl展開的。

3.4. PP問題的數(shù)學(xué)模型

圖8. OR節(jié)點控制功能的討論示例。

本文中MILP模型是基于優(yōu)先關(guān)系和網(wǎng)絡(luò)圖OR節(jié)點的。大部分的工藝優(yōu)化目標(biāo)都是時間相關(guān)[8]或者成本相關(guān)[14,18]的，本文的優(yōu)化目標(biāo)為最小化總生產(chǎn)時間，并且考慮工件在機器間的轉(zhuǎn)運時間約束。模型的集合、下標(biāo)、參數(shù)以及變量展示如表3所示。

表3 PP問題數(shù)學(xué)模型的集合、下標(biāo)、參數(shù)以及變量定義

總生產(chǎn)時間為模型的目標(biāo)函數(shù)：

式（9）右邊的第一部分是工件的總轉(zhuǎn)運時間，第

二部分是工件的總加工時間。模型的約束如下：（1）OR節(jié)點約束。

式（10）表示的是被OR節(jié)點控制的工序不被選擇的前提條件：只要有一條控制工序j的支路未被選擇，工序j就不會被選擇。式（11）表示的則是工序被選擇的前提條件：工序不被任何OR節(jié)點控制；或者，控制該工序的所有支路都被選擇。式（12）表示的則是工藝柔性只能選擇連接在一個OR節(jié)點上的所有支路中的一條。

（2）工序優(yōu)先約束。

式（13）～（18）表示的是工序之前的優(yōu)先約束。與式（1）～（4）不同的是，在這組約束里加入了工序被選擇的前提。式（13）對應(yīng)式（1），式（14）、（15）對應(yīng)式（2），式（16）對應(yīng)式（3）。式（17）表示如果工序j和j′未被選擇，那么qjj?和qj?j都被設(shè)置為0。式（18）則是確保被選中的工序遵循網(wǎng)絡(luò)圖中的優(yōu)先關(guān)系約束。

（3）EEM V與CEM Q約束。

因為矩陣V只包含兩相鄰工序的優(yōu)先關(guān)系，工件相鄰工序的轉(zhuǎn)運時間可以借此計算。式（19）～（22）描述的是矩陣V的自身屬性，及矩陣V和Q之間的關(guān)系。

（4）機器選擇約束。

式（23）表示的是被選工序只能選擇一臺機器執(zhí)行加工，且未被選擇的工序無須分配機器加工。

（5）轉(zhuǎn)運時間約束。

式（24）和（25）表述了工序j從當(dāng)前處理機器到下一個機器的轉(zhuǎn)運時間。

4. 實驗與討論

通過5組由著名數(shù)據(jù)集組成的數(shù)字實驗來驗證MILP模型，所得結(jié)果直接與文獻(xiàn)報道的其他方法所得的結(jié)果比對。實驗平臺配置3.7 GHZ和16 GB 隨機存取存儲器（RAM）的個人計算機，模型通過GAMS編碼并調(diào)用CPLEX進(jìn)行求解。引入Gap值（%）來評價模型所求解的質(zhì)量，該值表示所得解的相對偏差，定義為(BF - BP)/BP，其中BF為目標(biāo)值的當(dāng)前最好解，BP為當(dāng)前下界。Gap值越小，表示當(dāng)前解越接近理論下界，即質(zhì)量越好。求解時間設(shè)置為3600 s，如果在該時間內(nèi)未搜索到最優(yōu)解，計算進(jìn)程就會被中止，并且當(dāng)前解會被輸出。實驗1、2、4和5中機器間的轉(zhuǎn)運時間數(shù)據(jù)來自文獻(xiàn)[8,18]，如表4所示。

表4 機器間的轉(zhuǎn)運時間矩陣[8,18]

4.1. 實驗1

實驗1中的3個算例來自Jin和Zhang [16]，他們提出類似動態(tài)規(guī)劃（DP）-like的啟發(fā)式算法。本文中MILP模型獲得的結(jié)果與DP-like啟發(fā)式算法所得結(jié)果對比如表 5所示。第一個對比算例中MILP模型獲得的解目標(biāo)值為357，好于DP-like啟發(fā)式算法獲得的解目標(biāo)值360。此外，MILP模型能夠獲得并證明全部3個算例的最優(yōu)解。

表5 實驗1的結(jié)果對比

4.2. 實驗2

實驗2的4個算例來自不同的文獻(xiàn)：算例1來自Zhang和Lee [36]，算例2～4來自Li和McMahon [37]。算例的詳細(xì)數(shù)據(jù)可見原文獻(xiàn)。算例的對比結(jié)果為Li等[8]提出的改進(jìn)PSO算法是當(dāng)前求解此類組合優(yōu)化問題最有效的算法之一。對比結(jié)果如表6所示，MILP模型能夠獲得目標(biāo)值更好的解，并且以較短的計算時間（小于1 s）獲得了算例2～4的最優(yōu)解。

表6 實驗2的結(jié)果對比

4.3. 實驗3

本組實驗的兩個算例來自Li等[15]提出的GP算法，機器轉(zhuǎn)運時間矩陣如表7所示。兩個算例唯一的區(qū)別是算例2中的機器2被移除。實驗對比結(jié)果如表8所示，GP算法和MILP算法都能找到兩個算例的最優(yōu)解。

表7 機器間的轉(zhuǎn)運時間矩陣

表8 實驗3的結(jié)果對比

4.4. 實驗4

本組實驗的17個算例來自著名的Kim數(shù)據(jù)集[29]，由18個工件組成，其對比的算法和結(jié)果來自文獻(xiàn)[8]。由于文獻(xiàn)[8]中工件4的算例數(shù)據(jù)有問題，因此在本組實驗中不予展示。MILP模型與改進(jìn)的PSO算法、GA和SA算法的對比結(jié)果如表9所示。在可接受計算時間內(nèi)，MILP模型能夠找到本組17個算例中的13個最優(yōu)解。對于未找到最優(yōu)解的算例，模型所得解的質(zhì)量也好于對比算法解的質(zhì)量，如算例3、6、12和15。

表9 實驗4的結(jié)果對比

4.5. 實驗5

實驗5的11個算例來自另一組有名的Shin數(shù)據(jù)集[21]，其對比計算結(jié)果同樣來自Li等[8]。因為同樣的數(shù)據(jù)問題，略去了工件9、10、12、13、15、17和18的對比。MILP模型與改進(jìn)的PSO算法、GA和SA算法的對比結(jié)果如表10所示。在可接受計算時間內(nèi)，MILP模型能夠找到本組11個算例中的9個最優(yōu)解。對于未找到最優(yōu)解的算例，模型所得解的質(zhì)量也好于對比算法解的質(zhì)量，如算例3。

4.6. 實驗討論與分析

通過本節(jié)實驗發(fā)現(xiàn)，MILP模型能夠在可接受計算時間內(nèi)，求得總計37個算例中28個算例的最優(yōu)解。與現(xiàn)有高性能的啟發(fā)式[16]和元啟發(fā)式算法[8,15]對比，所提模型能夠獲得質(zhì)量更好的解。第4組和第5組實驗是在廣泛使用的著名數(shù)據(jù)集[21,29]上驗證的，實驗結(jié)果表明了所提模型的優(yōu)越性。

如表11所示，所提模型包含了4種類型的下標(biāo)，即工 序（operation）、機 器（machine）、OR節(jié) 點（OR node）和支路（link）；而文獻(xiàn)[16]中的模型包含6種下標(biāo)，即工藝特征（feature）、工序集合（operation set）、工序（operation）、機器（machine）、位序（position）和位置（place）。所提出的模型中較少的下標(biāo)使得模型的求解比文獻(xiàn)[16]中的模型更有效率。此外，基于OR節(jié)點的建模方法使得所提模型具有更強的通用性。這也解釋了所提模型能夠獲得Kim [29]和Shin [21]數(shù)據(jù)集大部分最優(yōu)解的原因。

表11 模型下標(biāo)

5. 結(jié)論及未來工作展望

從工藝網(wǎng)絡(luò)圖的拓?fù)浣Y(jié)構(gòu)出發(fā)，本文為PP問題提出了一種基于OR節(jié)點的MILP數(shù)學(xué)模型。首先，提出了三種優(yōu)先矩陣來討論工序間的優(yōu)先關(guān)系，然后引入了符號wjrl、url和xj來描述OR節(jié)點的選擇機制以拓展模型的通用性，最后將模型編碼并調(diào)用CPLEX求解器在公開數(shù)據(jù)集上進(jìn)行驗證。實驗比較結(jié)果驗證了所提模型的正確性和優(yōu)越性。

本研究首次提出了基于OR節(jié)點的建模方法，為PP問題研究展示了新的思路。本文對三個優(yōu)先矩陣的分析也揭示了工序排序子問題的本質(zhì)，有利于進(jìn)一步理解PP問題。然而，PP模型的相關(guān)研究仍存在一些局限性，即少數(shù)情況下無法找到最優(yōu)解，且計算效率有時也不盡如人意。這意味著本文所提出的方法還可以進(jìn)一步改進(jìn)，模型的簡化和加速方法是未來研究工作的重點之一。

致謝

本工作得到了國家自然科學(xué)基金（51825502、51775216）以及華中科技大學(xué)學(xué)術(shù)前沿青年團(tuán)隊計劃（2017QYTD04）的支持。

Compliance with ethics guidelines

Qihao Liu, Xinyu Li, and Liang Gao declare that they have no conflict of interest or financial conflicts to disclose.