改進遺傳算法求解面向訂單多目標排產問題

武韶敏，胡曉兵，王江武，徐興偉

（四川大學 制造科學與工程學院，四川 成都 610065）

1 引言

隨著市場經濟的深度發展和生產技術的逐步成熟，我國中小型制造企業也得到了極大的發展，面對競爭日趨激烈的市場和客戶需求的個性化，訂單式生產（Make To Order，MTO）也成為我國絕大多數中小型企業廣泛采用的一種生產模式[1]。生產調度是現代制造系統的一個重要問題，在企業的生產管理和市場競爭力中扮演著十分重要的角色。作業車間調度問題（Job Shop Scheduling Problem，JSSP）方面，文獻[2]采用啟發式倒排算法來求解加工調度問題，文獻[3]提出一種基于自適應遺傳算法的多目標柔性作業車間動態調度算法，文獻[4]針對JSSP問題提出一種基于知識的蟻群算法，但以上研究工作都是針對作業車間的局部排產，沒有從全局多作業車間或多生產單元的高度對訂單進行排產規劃。面向訂單生產方面，文獻[5]提出一種考慮備貨時間靈活性的訂單選擇和排產模型，文獻[6]研究了基于客戶滿意度的訂單排產策略，文獻[7]研究了單任務的多個訂單的接受和排產問題，并給出基于遺傳算法的求解模型，文獻[8]研究了從有限生產能力和產出緩存方面考慮訂單選擇策略，但以上研究大都將單個訂單看成整體進行排產，而實際生產過程中，特別是對于制造企業，每個訂單都由多個生產任務組成。文獻[9]研究了多任務組成訂單的排產，但是基于車間環境的。基于以上研究分析，提出一種更加符合面向訂單生產型企業生產實際的訂單排產思路，從全局的高度出發，將多個訂單拆解后的任務安排在多個生產單元協調生產，綜合考慮訂單的準時交付、企業生產成本和生產平衡多個指標對訂單排產優化。

2 問題描述

所研究的是在一個確定的排產周期T內對訂單進行排產，首先將原始訂單進行拆解，確保拆解后訂單的生產任務只包含一種產品，訂單的工藝過程、交貨日期等屬性完全一致；將拆解后的訂單安排在N個生產單元上，每個生產單元完成產品的部分加工過程，且產品在生產單元的加工工序有先后約束，每個生產單元有最大負荷約束；在滿足工序約束和最大負荷約束的情況下，通過優化排產來最小化排產周期內訂單的延期時間、庫存時間和平衡各生產單元的機器負荷，是一個多目標優化的NP-hard問題。

2.1 問題假設及符號

假設1，訂單在每一個生產單元的生產任務都可以在一個工作日內完成。假設2，訂單在各生產單元的加工時間已知，且在完成在前一個生產單元上的生產任務后才能在下一個生產單元上加工。訂單排產數學模型所使用的符號定義，如表1所示。

表1 符號定義Tab.1 Symbol Definition

2.2 模型建立

訂單的排產周期為T，t為計劃周期的基本單位，在本模型中t代表工作日，每個工作日生產單元i的可用最大載荷為Cmaxit。排產周期內涉及的訂單集合為 O=｛O1，O2，…，Oi，…，On｝，n 為正整數。訂單 k 中產品的工藝流程集合為 Jk=｛Jk1，Jk2，…Jkm｝1≤k≤n，需要說明的是，在本模型中工藝流程是與生產單元一一對應的，即將在工藝流程數量等于訂單從開始加工到完成生產所經過的生產單元的總和。決策變量：

目標函數，結合生產實際，為了能夠最大限度的優化訂單排產效果，從訂單的延期成本、庫存成本和工作單元負荷的平衡三方面指標來衡量排產的優劣。

（1）延期成本：每個訂單都指定的交貨日期，超過訂單交貨日期勢必會給企業帶來一定的損失，且損失與訂單的權重和延期時間長短有關。此外，延期訂單的數量也是一個非常重要的指標。因此，延期成本的計算分為延期訂單的數量和延期時間兩部分：

式中：mk—訂單k的最后一道工藝流程；delayCount—延期訂單數量。

（2）庫存成本：訂單的庫存是指在訂單完成后和交貨日期前停留在倉庫的時間間隔。訂單的庫存成本如式（3）所示：

式中：庫存時間懲罰系數γk是與各訂單中產品數量正相關的。

（3）工作單元的載荷均衡：訂單排產中保證工作單元的負荷均衡，有利于降低機器的損壞，延長使用壽命。載荷均衡見式：

的標準差；v—負載均衡的懲罰系數。

通過給訂單延期成本、庫存成本和載荷均衡三個指標賦予不同的權重系數ω1、ω2、ω3形成一個目標函數，如式（5）所示。每個訂單的所有工藝流程都必須分配在某個計劃周期單元t內生產，如式（6）所示。訂單的工藝約束，即單個訂單的工藝流程必須在上一工藝流程結束后才能開始生產，如式（7）所示。生產單元的生產能力約束，即對任意工作日t，安排在生產單元上的任務不能超過生產單元的最大負荷，如式（8）所示。

3 算法求解

結合實際數學模型，采用改進遺傳算法進行求解，優化排產。

3.1 矩陣實數編碼

采用一個N×J的矩陣來表示遺傳算法中的一個個體，即一種訂單排產的解決方案，矩陣采用實數編碼如下所示：

矩陣A的每一行代表一個訂單任務，共有N個訂單任務；矩陣每列對應的一個加工單元，也就是一個工藝流程。矩陣中元素aii的行標i表示第i個訂單，列標j表示第j個工藝流程，aii的取值是［0，T］的整數，表示訂單i的第j個工藝流程在第aii個計劃周期單元進行加工。

3.2 初始種群的產生

初始種群的個體是按行產生的。為了滿足工藝約束式（9），每個訂單從最后一道工藝流程開始隨機產生加工時間aiJ∈［1，T］，接著為倒數第二道工藝流程隨機分配加工時間aiJ-1∈［1，aiJ］，以此類推完成單個訂單的所有工藝流程的排產，進而完成所有訂單的排產。這種方法產生的初始種群個體必然滿足訂單任務的工藝約束（7），但并不一定滿足生產能力約束（8），因此對產生的個體還要進行校驗，是否超過生產單元的最大負荷，如果超過則是不可行解，要按以上步驟重新產生個體，直到滿足生產能力約束（8）。

3.3 交叉算子

算法采用實數矩陣編碼，傳統常用的單點交叉、多點交叉、均勻交叉等適用性有限，為了能使種群個體間交叉更加有效，設計了行交叉和列交叉兩種交叉算子。

3.3.1 行交叉算子

針對N×J階矩陣編碼的個體A，隨機產生一個由0和1組成的N維向量。對于父輩中任意的兩個體An和An+1，若N（i）=1，則對An和An+1的第i行進行交換，若N（i）=0則不進行任何操作。以此類推，種群中的任何兩個體都根據隨機為其產生的N維向量完成行交叉。根據以上的行交叉算子產生的子代CAn和CAn+1都必然滿足訂單產品工藝約束（7），但并不一定滿足生產能力約束（8），因此每次交叉完成后都要對產生的兩個新個體進行校驗，若不滿足，則要采用如圖1修復策略。對于滿足載荷約束的，則采用局部錦標賽法，比較父輩個體和子代個體的適應值，保留適應值較大的個體。

圖1 行交叉算子修復策略流程圖Fig.1 Flow Chart of Row-Based Crossover Operator Repair Strategy

3.3.2 列交叉算子

列交叉算子的設計和行交叉算子的設計思路類似，對于種群的每兩個父代個體都隨機產生一個由0和1組成的維向量作為交叉模板。但不同的是，兩父輩個體列交叉后產生的兩子代個體通常都不滿足訂單產品的工藝順序約束式子（7），因此需要對其進行修復。首先對新產生矩陣個體的每行從小到大重排使其滿足工藝約束，然后對個體進行工作單元最大載荷約束檢驗，若不滿足則舍棄該個體。對于滿足條件的，同樣采用局部錦標賽法保留父輩和子代中適應值較高的個體。

3.4 變異算子

變異算子的設計也有行變異算子和列變異算子兩種。兩種變異算子同樣采用由0和1組成的向量作為變異模板，數值的變異規則如下：

式中：di—第i個訂單的發貨日期；T—整個排產計劃周期。

變異規則（10）的說明：當個體矩陣的第i行最大值小于等于di，即該訂單不會延期時，該行所有元素采用di-aij+1的變異規則，確保了變異后產生的數值同樣在［1，di］范圍內，即仍是不延期訂單，這樣保證在有效變異的同時也保留個體的優良特征。當個體矩陣的第i行最大值大于di，即該訂單為延期訂單，該行所有元素采用T-aij+1的變異規則。

3.5 適應值函數和選擇算子

根據算法模型的目標函數式子（5），設計適應值函數如下：

選擇算子則是根據個體的適應值采用輪盤賭的方法產生子代個體，假設種群規模為，則個體被選擇的概率為：

4 實驗仿真

4.1 參數設置

由于所提出模型不存在標準算例，為了保證數據的合理性。所采用實驗數據是結合某機床廠的真實生產數據產生的，所有訂單的生產任務在相應生產單元的生產時間是的隨機數，單位為分鐘，每個生產單元的單個工作日的最大載荷為1920min。程序運行環境為內存2G、主頻2.67GHz的Win7操作系統的Matlab 2012平臺。算法的參數設置如下：行交叉概率，列交叉概率，行變異概率，列變異概率，權重系數，延期訂單數量的懲罰系數為，所有訂單的延期時間懲罰系數均為，生產單元載荷均衡系數。

4.2 算法對比

現有文獻中文獻[10]的問題模型與建立模型最接近，都是多任務訂單排產問題，且同樣是針對最大載荷已知的多個生產單元進行排產，不同的是其排產過程中考慮到庫存的影響。因此，下面同時采用文獻[10]中的改進粒子群算法和提出的改進遺傳算法解決提出的訂單排產問題模型，并對解的結果進行對比分析。遺傳算法的種群規模取100，進化代數取200，其他參數設置取4.1中的值。不同問題規模下兩種算法的求解結果和求解時間比較，每組數據計算10次，是10次運算的所有結果中目標函數最小值，是10次運算目標函數最小值的平均值，是算法運行時間的平均值，單位為s，如表2所示。從表2可以看出，設計的改進遺傳算法在優化結果和運算時間上都要優于參考文獻中的改進粒子群算法。在（20×7）情況時，采用改進GA算法種群優化目標函數的平均值和最優值在整個進化過程中變化趨勢，如圖2所示。種群平均延期訂單數、平均延期時間、平均庫存時間及平均生產單元載荷標準差的變化情況，如圖3和圖4所示。從三圖可以看出無論是總體目標還是各個指標的優化都非常顯著。

表2 算法性能對比Tab.2 Algorithm Performance Comparison

圖2 種群目標函數值Fig.2 Objective Function Value of the Populations

圖3 延期訂單數、延期時間及庫存時間平均值Fig.3 Average Value of the Delayed Orders，Delay Time and Stock Time

圖4 生產單元載荷標準差Fig.4 Standard Deviation of Production Unit Load

5 結語

結合企業生產實際提出一種面向多目標排產優化的方法，綜合考慮訂單的延期成本、庫存成本和生產單元的負載均衡三個優化指標，構建了排產優化的數學模型。設計了基于矩陣編碼的改進遺傳算法求解上述數學模型，通過對算法對比，驗證了改進GA算法的有效性和優越性。

［1］鄧毅.基于MTO的中小型制造企業訂單排產優化研究［D］.廣州：廣東工業大學，2011.（DengYi.Orderproductionschedulingoptimizationresearchbasedonsmall and medium-sized manufacturing enterprise of MTO［R］.Guangzhou：Guangdong University of Technology，2011.）

［2］趙芳，姜莉莉，習小英.基于啟發式倒排算法加工調度研究［J］.機械設計與制造，2010（12）：52-54（Zhao Fang，Jiang Li-li，Xi xiao-ying.Job shop scheduling problem of matching machine based on bacjward herisitic scheduling algorithm［J］.Machinery&Manufacture，2010（12）：52-54.）

［3］劉愛軍，楊育，邢青松.柔性作業車間多目標動態調度［J］.計算機集成制造系統，2011，17（12）：2629-2637.（Liu Ai-jun，Yang Yu，Xing Qing-song.Dynamic scheduling on multiobjective flexible Job Shop［J］.Computer Integrated Manufacturing Systems，2011，17（12）：2629-2637.）

［4］Xing L N，Chen Y W，Wang P.A knowledge-based ant colony optimization for flexible job shop scheduling problems［J］.Applied Soft Computing，2010，10（3）：888-896.

［5］Ch K，G P M，K P.Order selection and scheduling with leadtime flexibility［J］.IIE Transactions，2004，36（7）：697-707.

［6］郭源生.基于顧客滿意度的客戶訂單選擇［J］.西安電子科技大學學報，2007，17（6）：36-40.（Guo Yuan-sheng.Options of customer orders based on customer satisfaction［J］.Journal of Xidian University，2007，17（6）：36-40.）

［7］Rom W O，Slotnick S A.Order acceptance using genetic algorithm［J］.Computers&Operations Research，2009，36（6）：1758-1767

［8］張欣，馬士華.基于有限生產能力和產出緩存的訂單接受策略［J］.工業工程與管理，2008（2）：35-40.（Zhang Xin，Ma Shi-hua.Order acceptance with limited capacity and finite output buffers in MTO environment［J］.Industrial Engineering and Management，2008（2）：35-40.）

［9］Siddharth M，Purushothaman D，CHEN C S.A branch and price solution approach for order acceptance and capacity planning in make-to-order operations［J］.European Journal of Operational Research，2011，211（3）：480-495.

［10］ZHANG T，ZHENG Q，FANG Y.Multi-level inventory matching and order planning under the hybrid Make-To-Order/Make-To-Stock production environment for steel plants via Particle Swarm Optimization［J］.Computers&Industrial Engineering，2015（87）：238-249.