考慮準備時間的兩階段裝配流水線訂單接受與調度決策

宋李俊，魯若愚，李孝斌，龔小容,*

（1.重慶理工大學 機械工程學院，重慶 400054；2.重慶大學 機械與運載工程學院，重慶 400044）

0 引言

經濟全球化的大背景下，制造自動化、柔性化、智能化和高度集成化推動全球產業競爭格局發生著重大調整，制造企業間的競爭愈趨激烈。在過去，按訂單生產型（Make To Order,MTO）企業在訂單接受和訂單生產上分別由銷售部門和生產部決策，銷售部門往往只關心訂單接受的數量而不考慮訂單的生產，而生產部門更多考慮生產訂單交期的滿足，對訂單總體效益較少關注。這樣的分開決策往往會導致接受的訂單大大超過生產能力而產生訂單的延遲懲罰成本，從而導致企業效益受損和名譽受損，更嚴重的會導致客戶的流失。為了企業效益提升，MTO企業開始對訂單接受與調度（Order Acceptance and Scheduling,OAS）問題進行集成決策，在訂單接受同時根據訂單特點和要求進行優化調度排產，在滿足訂單交期的前提下盡可能接受更多訂單。

目前，已有一些學者對OAS問題進行了一定的研究。Slotnick和Morton是OAS問題較早的研究者，他們將企業生產環境抽象為一臺機器，加工不允許搶占和中斷，客戶接受一定的交貨期延遲，延期懲罰是與延期天數線性相關的遞增函數，對比結果表明在產能有限的約束下，訂單接受和調度聯合決策比分開決策利潤率更高，證實了OAS問題的研究意義與實用價值[1]。Oguz等進一步擴展了Slotnick和Morton研究的優化決策模型，考慮訂單發布時間和序列生產準備時間帶來的復雜性，提出了一種混合整數線性規劃模型[2]。Back等進一步考慮了有限產能約束，并假設準備時間對釋放時間存在部分依賴關系，提出了一個新的混合整數線性規劃模型[3]。王柏琳等針對多品種混合制造商的不相關并行機訂單拒絕問題，以總成本最小為目標，基于列表拒絕方法和訂單拒絕準則設計了采用單親-傳統雙遺傳算子的協同進化遺傳算法[4]。Wang等人研究了一種不相關并行機OAS決策問題，以總收益與總加權延誤的差額為目標函數，建立了兩個混合整數規劃模型，并提出了一種分枝定界算法[5]。Naderi等針對訂單選擇和相同并行機調度問題，建立了預處理技術、有效不等式和優勢規則等增強策略改進一個混合整數規劃數學模型，并利用分支松弛和檢查（BRC）方法將模型進行了分解[6]。宋李俊等人針對JIT模式下多節點流水線具有訂單交貨延遲懲罰與產品庫存平衡約束的OAS決策問題，建立了總利潤最大化決策模型，并設計了改進型雙層編碼遺傳算法進行求解[7]。

從現有的相關文獻來看，對OAS問題的研究主要集中在單機（單節點）環境[8～10]或并行機環境[11,12]，對于更復雜的多階段加工環境的研究較少。本文以兩階段裝配流水線為研究對象，基于有限產能考慮訂單序列相關準備時間約束，建立以訂單利潤最大為目標的訂單接受與調度模型，并設計一種變鄰域半置換遺傳算法（Semi-permutation-based Genetic Algorithm-Variable Neighborhood Search，SPGA-VNS）進行求解。

1 問題描述與建模

1.1 問題描述

本文提及的兩階段裝配流水線生產流程可以描述為：產品生產分為配套零件加工、裝配兩個階段，第一個階段有M個并行的流水加工單元，不同的加工單元完成不同的零部件加工，本文將M個加工單元簡化為M臺特定的異速并行加工機器；第二個階段有1個裝配單元，當各配套零件加工完成后，裝配單元支持將零件裝配成完整產品，其生產流程模型如圖1所示。

圖1 兩階段裝配流水線生產流程模型

兩階段裝配流水線OAS問題可以描述為：企業初始時刻收到n個生產訂單可供選擇，在滿足兩階段裝配流程生產模式情況下，確定接受哪些訂單以及制定被接受訂單的調度方案，以實現訂單收益最大化。其中，訂單采用柔性交貨期形式進行交付，即若訂單在約定交貨期之后、最遲交貨期之前完成生產，則視為延期交付，將產生延期懲罰；若在約定交貨期前完成生產，則視為按期交貨，無懲罰；若在最遲交貨期之后完成生產，則視為延期懲罰大于訂單收益，訂單將被拒絕。該問題模型需要滿足以下假設：

1）所有參數均為已知和確定的。

2）所有訂單都在初始時刻（設為t=1時刻）可在任何機器上進行加工。

3）機器加工或裝配過程為非搶占式。

4）每個訂單的工藝路線為確定的。

5）每個訂單之間均不存在先后約束。

6）機器持續可用。

7）加工存在訂單序列相關的加工準備時間。

8）任何一個訂單完成第一階段所零件加工后才可開始裝配。

9）兩個生產階段間存在足夠大的緩沖區域。

為了方便建模，本文符號定義如表1所示。

表1 符號定義

1.2 模型建立

根據以上描述建立采用時間索引(Time-indexed formulation,TIF)方法的混合整數線性規劃模型。目標為訂單利潤最大化。數學模型如下：

式(1)表示目標函數為訂單收益與延期懲罰之差；式(2)表示每個訂單只在某個確定時刻在第一階段的機器上開始加工；式(3)表示訂單j在第一階段加工機器i上的加工完成時刻；式(4)表示訂單j在第一階段的加工完成時刻大于或等于其在任意機器i上的加工完成時刻；式(5)表示任何一個時刻機器i上最多只有一個訂單在加工；式(6)表示每個訂單只在第二階段的某個確定時刻在裝配機器上開始裝配；式(7)表示訂單j在第二階段的裝配完工時刻；式(8)表示訂單j必須在完成其第一階段所有加工后才能開始裝配；式(9)表示訂單j在第一階段的加工完成時刻必須小于或等于其裝配開始時刻；式(10)表示任何一個時刻裝配機器上最多只有一個訂單在裝配；式(11)表示訂單j的裝配完工時刻必須小于或等于訂單j的最遲交貨期；式(12)表示訂單j必須在其第一階段加工時間范圍內開始加工；式(13)表示訂單j必須在其第二階段加工時間范圍內開始裝配；式(14)表示訂單j的裝配開始時刻大于其在第一階段機器上的最大加工時間；式(15)表示決策變量的取值范圍。

2 算法設計

同粒子群、蟻群、模擬退火等算法相比，遺傳算法具有操作簡單、迭代時間短、全局尋優能力強、魯棒性好等特點，更適用于求解復雜生產環境下的OAS問題。但遺傳算法存在搜索效率較低和容易過早收斂等不足，因此對遺傳算法進行一定程度的改進或與其他算法混合，是增強其局部搜索能力、加快收斂速度以及提高解質量的有效手段。本文針對兩階段裝配流水線訂單接受與調度問題求解，提出一種變鄰域半置換改進遺傳算法，利用整數矩陣編碼和啟發式規則提升初始種群的質量，設計隨機半置換單點交叉、互換變異等改進遺傳策略提高解的質量，并提出原基因重插入法確保新種群個體均為可行解，結合變鄰域搜索提高算法的局部搜索能力。

2.1 染色體編碼

考慮到加工裝配流水線由m臺異速并行機器和1臺裝配機器組成，本文采用基于訂單順序的整數矩陣對染色體進行編碼。一個完整的個體為一個m+1行、n列的整數編碼矩陣，編碼矩陣中每一行代表一條染色體，如圖2所示。編碼矩陣的前m行表示第一階段的加工機器i上的訂單加工順序，數字表示對應的訂單序號；編碼矩陣的第m+1行表示第二階段的裝配機器上訂單的裝配順序。

圖2 整數矩陣編碼

2.2 種群初始化

初始種群由三個種類，共N個種群個體組成。

1）第一類種群個體采用隨機策略，共生成0.6N個。首先，隨機排序生成第一階段加工機器1的訂單加工順序，然后采用隨機相鄰半置換策略生成其他機器訂單加工順序，即在保持最先開始加工的訂單序號不變的情況下，其余n-1個訂單的加工順序均采用兩個隨機選擇的相鄰訂單的成對交換2n次生成，最后第二階段裝配機器上的訂單裝配順序采用FIFO規則生成。

2）第二類種群個體采用單位加工時間收益越大優先策略，共生成0.2N個。首先基于訂單Rj/Pj的非升序排列生成第一階段加工機器1上的訂單加工順序，然后采用隨機相鄰半置換策略生成剩余機器上的訂單加工順序，最后第二階段裝配機器上的訂單裝配順序采用FIFO規則生成。

3）第三類種群個體采用單位加工時間延期懲罰越低優先策略，共生成0.2N個。首先基于訂單Wj/Pj的非降序排列生成第一階段加工機器1上的訂單加工順序，然后采用隨機相鄰半置換策略生成剩余機器上的訂單加工順序，最后第二階段裝配機器上的訂單裝配順序采用FIFO規則生成。

2.3 適應度函數

種群中個體的適應度值代表其對環境的適應程度，同時也反映了現有種群每一個體的質量好壞，本文將模型的目標函數作為算法的適應度函數：

2.4 選擇操作

采用錦標賽法作為選擇操作策略，并利用精英保留策略保證種群中的最優個體一定被選中。帶精英保留策略的錦標賽法步驟為：

步驟1：確定每次從父代種群中隨機抽取個體的數量，本文設定數量為0.05N。

步驟2：父代種群個體按照適應度值非增序排列，選擇最優的1%父代個體直接復制進入新種群。

步驟3：從經過精英保留后的種群中隨機抽取0.05N個父代個體，比較每個被抽取個體的適應度值，復制適應度值相對較大的個體作為新的父代保留。

步驟4：重復步驟3的操作，直到新的父代種群規模達到N。

2.5 交叉操作

本文采用整數矩陣編碼，選擇單點交叉作為交叉操作方法，然而并非每個經單點交叉后的個體都是可行解，若新個體的染色體中存在基因重復，將導致新個體成為一個不可行解。因此本文設計了原基因重插入法，以此保證交叉生成的新個體是可行解，其操作步驟為：

步驟1：隨機選擇交叉點，假設交叉點確定為位置4和位置5基因之間處，隨后對兩個父代染色體進行單點交叉操作，互換交叉點后的基因片段后父代Ⅰ產生的子代染色體為6→5→1→4→1→2。從左往右檢查子代染色體，可以發現基因1為重復基因，將較早出現的基因1從染色體中剔除，剔除后的子代染色體變為6→5→4→1→2。

圖3 步驟1

步驟2：將父代Ⅰ的互換基因片段添加到子代染色體的末尾。

圖4 步驟2

步驟3：再次檢查子代染色體，確認基因2為重復基因，將較后出現的重復基因剔除，得到可行解子代染色體為6→5→4→1→2→3。

圖5 步驟3

步驟4：當父代Ⅱ經相同步驟得到子代染色體6→5→4→3→2→1后，交叉操作結束。

2.5 變異操作

采用互換變異對染色體進行變異操作，如圖6所示，隨機選定染色體上的兩個基因（染色體上的第一個基因除外）互換位置產生新的染色體。

圖6 互換變異

2.6 變鄰域搜索

鄰域結構是變鄰域搜索算法的核心部分，將會直接影響算法的搜索質量。根據染色體的編碼機制，設計以下兩種鄰域結構：

1）鄰域結構NS1采用部分逆序反轉策略。該策略對原始染色體進行較大幅度變動，以擴大鄰域搜索空間，能夠更好的跳出局部最優。例如一條染色體的原本基因編碼為6→5→4→1→2→3，隨機選擇兩個基因位置4和6（基因位置1不可選），將兩個之間的基因逆轉，得到新的染色體6→5→4→3→2→1。

2）鄰域結構NS2采用插入策略。該策略隨機選擇兩個基因位置（基因位置1不可選），將靠后位置上的基因插入至靠前位置的基因前，位置2之后的基因則依次后移，得到新的染色體。

本文對構造鄰域進行動態構建，交替使用兩種鄰域結構，避免單一鄰域結構導致搜索效率降低。

2.7 訂單拒絕操作

當初始種群經過迭代，滿足遺傳算法終止條件時，計算新種群中每一個體適應度值，定義適應度值最大的個體為最優個體，其適應度值f(N)即為當前種群的最大目標函數值。若該個體中存在延期訂單，則進入訂單拒絕操作：新種群中每一個體隨機去掉一個訂單。

假如某種群個體的第一條染色體為5→4→1→2→3，隨機去除一個訂單（假設為1號訂單）后，表示1號訂單被拒絕，2、3、4、5號訂單被接受。

被接受的訂單將根據種群初始化策略，產生新的初始種群。

2.8 SPGA-VNS算法流程

變鄰域半置換遺傳算法（SPGA-VNS）求解流程如圖7所示：

圖7 SPGA-VNS算法流程圖

3 案例分析

3.1 環境設置

由于目前針對兩階段裝配流水線的訂單接受與調度問題研究方面尚未有標準算例提出，為了測試所提出的SPGA-VNS性能，本文參考已有的文獻生成測試算例，具體生成方案如下：

第一階段加工機器數量有m=2、4、6三種不同數量，訂單數量規模分為小規模、中規模和大規模三種不同數量規模，分別對應n=10、20、30，n=50、75、100以及n=150、200。針對不同規模的算例，每一種機器數量與訂單數量的組合都采用隨機的方式，生成10個算例。

每臺機器上的加工或裝配時間由[1,10]之間的離散均勻分布隨機產生，即U[1,10]。訂單的單位延期懲罰同樣由U[1,10]隨機生成。第一階段加工機器上的準備時間由U[1,5]隨機產生。由于本文所研究問題的交貨期為柔性交貨期，所以定義訂單的松弛時間DTj由U[1,β.PTi]隨機生成，其中PTi=Σpij，松弛程度β可從集合{0.25，0.50，0.75}中選擇。每個訂單的交貨期Dj=maxi{DTj+Sijk+Pij+Pj}，訂單的收益Rj服從U[1,20]。

算法參數具體設定為：種群規模N=100、迭代次數Gen=1、最大迭代次數maxGen=100、交叉概率CP=0.8、變異概率MP=0.2。

對比算法如下：

1）遺傳算法(GA)：與SPGA-VNS相比，該遺傳算法在種群初始化、交叉操作方面與SPGA-VNS不同，且未對變異產生的新種群進行鄰域搜索，其他操作都與所提出的SPGA-VNS方法類似。

2）半置換遺傳算法（SPGA）：與SPGA-VNS相比，SPGA在種群初始化、交叉、變異、訂單拒絕等方面均無區別，唯一不同是未采用鄰域搜索算法對種群進行鄰域搜索。

SPGA-VNS、SPGA、GA以及CPLEX均在Intel Core i7 CPU、16GB RAM、Windows10操作系統和Python3.7環境下進行編譯。

3.2 結果分析

本文通過不同規模算例優化解數量B-number、對偶間隙Gap以及CPU計算時間Time(s)來衡量SPGA-VNS算法的性能。備注：CPLEX在3600秒內能找到優化解，則記可行解為數量1；在3600秒以外才能找到可行解，則記可行解數量為0，CPLEX在運行時長7200秒以內無法找到可行解，則記錄該算例CPLEX的可行解數量為NA。SPGA-VNS算法在3600秒內可以找到目標值大于或等于CPLEX的可行解，則記非劣解數量為1，否則為0。

從表2可以看出，CPLEX雖在小規模算例中解得127個可行解，但隨著機器數量的增加，可行解數量也在減少。由于訂單數量更多的中規模算例中，CPLEX已難以在規定時間內求得可行解，因此不再給出大規模算例下CPLEX可行解和算法非劣解數量。SPGA-VNS算法在小規模算例中求得了96個非劣解，多于SPGA算法的75個和GA算法的42個。雖然訂單和機器數量的不斷增加，使得三種算法的非劣解數量雖然都逐漸變少，但SPGA-VNS和SPGA算法的求解性能優勢逐漸明顯，找到的非劣解數量均遠多于GA算法。與此同時，β的增大使得算例的求解難度在不斷上升，CPLEX和三種算法的求解表現均與β呈現出了負相關的變化趨勢。

表2 小規模和中規模算例可行解和非劣解結果表

以上結果說明，利用SPGA-VNS算求解小規模和中規模算例是可行的，且隨機半置換策略在規模越大的算例中，對求解效果的提升作用越明顯。

對偶間隙能夠反映出解在目標值層面的相對優劣，對表3中的對偶間隙Gap定義如下：

從表3可以看出，小規模算例中，在只有2個加工機器時，CPLEX能找到目標值不低于其他算法的可行解，當加工機器數量增至4個時，SPGA-VNS等三種算法均能找到目標值不小于CPLEX的非劣解，且對偶間隙隨著訂單數量的增大和β值的上升開始出現負數，這表明算法在機器數量較多時，求解質量優于CPLEX。在所有中等規模算例中，采用了隨機半置換策略的SPGA-VNS和SPGA算法都能找到比CPLEX可行解的平均目標值更大的優化解，并且算例規模越大，SPGA-VNS和SPGA算法的求解優勢越明顯。

表3 小規模和中規模算例平均對偶間隙結果表

此外，橫向對比三種算法，在小規模算例中，SPGA-VNS算法的平均對偶間隙為-2.12%，略優于SPGA和GA算法，但在中規模算例中，SPGA-VNS算法的求解質量表現出了更明顯的優勢，平均對偶間隙較之SPGA和GA算法分別提升了19.60%和5.38%。

在表4中，重新定義對偶間隙為SPGA-VNS和SPGA算法的優化解與GA算法的優化解在目標值方面的差距，具體計算公式如式(18)所示：

表4 大規模算例平均對偶間隙結果表

從表4可以看出，相對于GA算法，SPGA-VNS和SPGA算法在大規模算例中，優化解的平均目標值都有較大幅度的提升。

CPU計算時間結果如表5所示，SPGA-VNS和SPGA算法的求解速度較之GA算法均有著一定幅度的領先，且隨著算例規模逐漸增大，優勢更加明顯。在大規模算例中，采用隨機半置換策略的SPGA算法求解速度提升了17.52%，同樣采用隨機半置換策略并結合變鄰域搜索的SPGA-VNS則是進一步將求解速度提升了25.39%。

表5 大規模算例CPU計算時間結果表

表6給出了4×10規模算例下，采用分開決策、聯合決策的計算結果。通過訂單利潤、延期懲罰、以及訂單延期三個方面的對比，可以看出，對訂單接受和生產調度進行聯合決策可以在訂單利潤目標方面比分開決策取得更好的效果，且SPGA-VNS算法可以有效地求解復雜環境下的OAS問題。

表6 4×10規模算例分開決策與聯合決策結果表

圖8給出了規模為4×10的小規模算例在迭代100次時的算法收斂曲線?？梢钥闯?，SPGA-VNS和SPGA算法能夠得到較大的適應度值，這說明隨機半置換策略能夠有效提高算法求解質量；另外，SPGA-VNS算法能在迭代30次左右找到最優解，先于SPGA和GA算法，說明變鄰域搜索策略有效的加快了算法收斂速度。以上結果表明，本文提出的SPGA-VNS算法就具有良好的求解質量和收斂性。

圖8 小規模算例算法收斂曲線

4 結語

本文針對兩階段裝配流水線的訂單接受與調度問題，在考慮具有訂單序列相關準備時間約束基礎上，建立了以訂單利潤最大化為目標的TIF-MILP模型，提出了一種采用整數矩陣編碼、啟發式規則改進初始種群生成策略、隨機半置換單點交叉、互換變異等改進策略的改進遺傳算法SPGA-VNS，并采用原基因重插入法保證新種群個體均為可行解，結合變鄰域搜索提高算法的局部搜索能力。最后，通過不同規模的隨機算例測試結果表明，SPGA-VNS算法相較于SPGA、GA算法，可以在合理的時間內更快找到目標值更大的優化解，具有良好的求解質量和收斂性。