改進(jìn)遺傳算法求解面向訂單多目標(biāo)排產(chǎn)問(wèn)題

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

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

1 引言

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

2 問(wèn)題描述

所研究的是在一個(gè)確定的排產(chǎn)周期T內(nèi)對(duì)訂單進(jìn)行排產(chǎn)，首先將原始訂單進(jìn)行拆解，確保拆解后訂單的生產(chǎn)任務(wù)只包含一種產(chǎn)品，訂單的工藝過(guò)程、交貨日期等屬性完全一致；將拆解后的訂單安排在N個(gè)生產(chǎn)單元上，每個(gè)生產(chǎn)單元完成產(chǎn)品的部分加工過(guò)程，且產(chǎn)品在生產(chǎn)單元的加工工序有先后約束，每個(gè)生產(chǎn)單元有最大負(fù)荷約束；在滿足工序約束和最大負(fù)荷約束的情況下，通過(guò)優(yōu)化排產(chǎn)來(lái)最小化排產(chǎn)周期內(nèi)訂單的延期時(shí)間、庫(kù)存時(shí)間和平衡各生產(chǎn)單元的機(jī)器負(fù)荷，是一個(gè)多目標(biāo)優(yōu)化的NP-hard問(wèn)題。

2.1 問(wèn)題假設(shè)及符號(hào)

假設(shè)1，訂單在每一個(gè)生產(chǎn)單元的生產(chǎn)任務(wù)都可以在一個(gè)工作日內(nèi)完成。假設(shè)2，訂單在各生產(chǎn)單元的加工時(shí)間已知，且在完成在前一個(gè)生產(chǎn)單元上的生產(chǎn)任務(wù)后才能在下一個(gè)生產(chǎn)單元上加工。訂單排產(chǎn)數(shù)學(xué)模型所使用的符號(hào)定義，如表1所示。

表1 符號(hào)定義Tab.1 Symbol Definition

2.2 模型建立

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

目標(biāo)函數(shù)，結(jié)合生產(chǎn)實(shí)際，為了能夠最大限度的優(yōu)化訂單排產(chǎn)效果，從訂單的延期成本、庫(kù)存成本和工作單元負(fù)荷的平衡三方面指標(biāo)來(lái)衡量排產(chǎn)的優(yōu)劣。

（1）延期成本：每個(gè)訂單都指定的交貨日期，超過(guò)訂單交貨日期勢(shì)必會(huì)給企業(yè)帶來(lái)一定的損失，且損失與訂單的權(quán)重和延期時(shí)間長(zhǎng)短有關(guān)。此外，延期訂單的數(shù)量也是一個(gè)非常重要的指標(biāo)。因此，延期成本的計(jì)算分為延期訂單的數(shù)量和延期時(shí)間兩部分：

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

（2）庫(kù)存成本：訂單的庫(kù)存是指在訂單完成后和交貨日期前停留在倉(cāng)庫(kù)的時(shí)間間隔。訂單的庫(kù)存成本如式（3）所示：

式中：庫(kù)存時(shí)間懲罰系數(shù)γk是與各訂單中產(chǎn)品數(shù)量正相關(guān)的。

（3）工作單元的載荷均衡：訂單排產(chǎn)中保證工作單元的負(fù)荷均衡，有利于降低機(jī)器的損壞，延長(zhǎng)使用壽命。載荷均衡見(jiàn)式：

的標(biāo)準(zhǔn)差；v—負(fù)載均衡的懲罰系數(shù)。

通過(guò)給訂單延期成本、庫(kù)存成本和載荷均衡三個(gè)指標(biāo)賦予不同的權(quán)重系數(shù)ω1、ω2、ω3形成一個(gè)目標(biāo)函數(shù)，如式（5）所示。每個(gè)訂單的所有工藝流程都必須分配在某個(gè)計(jì)劃周期單元t內(nèi)生產(chǎn)，如式（6）所示。訂單的工藝約束，即單個(gè)訂單的工藝流程必須在上一工藝流程結(jié)束后才能開(kāi)始生產(chǎn)，如式（7）所示。生產(chǎn)單元的生產(chǎn)能力約束，即對(duì)任意工作日t，安排在生產(chǎn)單元上的任務(wù)不能超過(guò)生產(chǎn)單元的最大負(fù)荷，如式（8）所示。

3 算法求解

結(jié)合實(shí)際數(shù)學(xué)模型，采用改進(jìn)遺傳算法進(jìn)行求解，優(yōu)化排產(chǎn)。

3.1 矩陣實(shí)數(shù)編碼

采用一個(gè)N×J的矩陣來(lái)表示遺傳算法中的一個(gè)個(gè)體，即一種訂單排產(chǎn)的解決方案，矩陣采用實(shí)數(shù)編碼如下所示：

矩陣A的每一行代表一個(gè)訂單任務(wù)，共有N個(gè)訂單任務(wù)；矩陣每列對(duì)應(yīng)的一個(gè)加工單元，也就是一個(gè)工藝流程。矩陣中元素aii的行標(biāo)i表示第i個(gè)訂單，列標(biāo)j表示第j個(gè)工藝流程，aii的取值是［0，T］的整數(shù)，表示訂單i的第j個(gè)工藝流程在第aii個(gè)計(jì)劃周期單元進(jìn)行加工。

3.2 初始種群的產(chǎn)生

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

3.3 交叉算子

算法采用實(shí)數(shù)矩陣編碼，傳統(tǒng)常用的單點(diǎn)交叉、多點(diǎn)交叉、均勻交叉等適用性有限，為了能使種群個(gè)體間交叉更加有效，設(shè)計(jì)了行交叉和列交叉兩種交叉算子。

3.3.1 行交叉算子

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

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

3.3.2 列交叉算子

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

3.4 變異算子

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

式中：di—第i個(gè)訂單的發(fā)貨日期；T—整個(gè)排產(chǎn)計(jì)劃周期。

變異規(guī)則（10）的說(shuō)明：當(dāng)個(gè)體矩陣的第i行最大值小于等于di，即該訂單不會(huì)延期時(shí)，該行所有元素采用di-aij+1的變異規(guī)則，確保了變異后產(chǎn)生的數(shù)值同樣在［1，di］范圍內(nèi)，即仍是不延期訂單，這樣保證在有效變異的同時(shí)也保留個(gè)體的優(yōu)良特征。當(dāng)個(gè)體矩陣的第i行最大值大于di，即該訂單為延期訂單，該行所有元素采用T-aij+1的變異規(guī)則。

3.5 適應(yīng)值函數(shù)和選擇算子

根據(jù)算法模型的目標(biāo)函數(shù)式子（5），設(shè)計(jì)適應(yīng)值函數(shù)如下：

選擇算子則是根據(jù)個(gè)體的適應(yīng)值采用輪盤(pán)賭的方法產(chǎn)生子代個(gè)體，假設(shè)種群規(guī)模為，則個(gè)體被選擇的概率為：

4 實(shí)驗(yàn)仿真

4.1 參數(shù)設(shè)置

由于所提出模型不存在標(biāo)準(zhǔn)算例，為了保證數(shù)據(jù)的合理性。所采用實(shí)驗(yàn)數(shù)據(jù)是結(jié)合某機(jī)床廠的真實(shí)生產(chǎn)數(shù)據(jù)產(chǎn)生的，所有訂單的生產(chǎn)任務(wù)在相應(yīng)生產(chǎn)單元的生產(chǎn)時(shí)間是的隨機(jī)數(shù)，單位為分鐘，每個(gè)生產(chǎn)單元的單個(gè)工作日的最大載荷為1920min。程序運(yùn)行環(huán)境為內(nèi)存2G、主頻2.67GHz的Win7操作系統(tǒng)的Matlab 2012平臺(tái)。算法的參數(shù)設(shè)置如下：行交叉概率，列交叉概率，行變異概率，列變異概率，權(quán)重系數(shù)，延期訂單數(shù)量的懲罰系數(shù)為，所有訂單的延期時(shí)間懲罰系數(shù)均為，生產(chǎn)單元載荷均衡系數(shù)。

4.2 算法對(duì)比

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

表2 算法性能對(duì)比Tab.2 Algorithm Performance Comparison

圖2 種群目標(biāo)函數(shù)值Fig.2 Objective Function Value of the Populations

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

圖4 生產(chǎn)單元載荷標(biāo)準(zhǔn)差Fig.4 Standard Deviation of Production Unit Load

5 結(jié)語(yǔ)

結(jié)合企業(yè)生產(chǎn)實(shí)際提出一種面向多目標(biāo)排產(chǎn)優(yōu)化的方法，綜合考慮訂單的延期成本、庫(kù)存成本和生產(chǎn)單元的負(fù)載均衡三個(gè)優(yōu)化指標(biāo)，構(gòu)建了排產(chǎn)優(yōu)化的數(shù)學(xué)模型。設(shè)計(jì)了基于矩陣編碼的改進(jìn)遺傳算法求解上述數(shù)學(xué)模型，通過(guò)對(duì)算法對(duì)比，驗(yàn)證了改進(jìn)GA算法的有效性和優(yōu)越性。

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

［2］趙芳，姜莉莉，習(xí)小英.基于啟發(fā)式倒排算法加工調(diào)度研究［J］.機(jī)械設(shè)計(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］劉愛(ài)軍，楊育，邢青松.柔性作業(yè)車間多目標(biāo)動(dòng)態(tài)調(diào)度［J］.計(jì)算機(jī)集成制造系統(tǒng)，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］.西安電子科技大學(xué)學(xué)報(bào)，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］張欣，馬士華.基于有限生產(chǎn)能力和產(chǎn)出緩存的訂單接受策略［J］.工業(yè)工程與管理，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，F(xiàn)ANG 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.