1 引言

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

2 問題描述

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

2.1 問題假設(shè)及符號

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

表1 符號定義
Tab.1 Symbol Definition

符號 描述n訂單總數(shù)k客戶訂單編號T訂單排產(chǎn)周期h訂單排產(chǎn)的計(jì)劃周期長度mk 訂單k中產(chǎn)品工藝流程數(shù)量tki 訂單k的第i個工藝流程所需時間Cmaxit 第i個生產(chǎn)單元在計(jì)劃周期t內(nèi)的最大載荷dk 訂單k的交貨時間α延期訂單數(shù)量的懲罰系數(shù)βk 訂單延期時間的懲罰系數(shù)γk 庫存時間的懲罰系數(shù)ν負(fù)載平衡的懲罰系數(shù)

2.2 模型建立

訂單的排產(chǎn)周期為T，t為計(jì)劃周期的基本單位，在本模型中t代表工作日，每個工作日生產(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，需要說明的是，在本模型中工藝流程是與生產(chǎn)單元一一對應(yīng)的，即將在工藝流程數(shù)量等于訂單從開始加工到完成生產(chǎn)所經(jīng)過的生產(chǎn)單元的總和。決策變量：

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

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

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

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

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

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

式中）—計(jì)劃周期T內(nèi)所有工作日工作單元負(fù)荷

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

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

3 算法求解

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

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

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

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

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

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

3.3 交叉算子

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

3.3.1 行交叉算子

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

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

3.3.2 列交叉算子

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

3.4 變異算子

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

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

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

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

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

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

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)時間是的隨機(jī)數(shù)，單位為分鐘，每個生產(chǎn)單元的單個工作日的最大載荷為1920min。程序運(yùn)行環(huán)境為內(nèi)存2G、主頻2.67GHz的Win7操作系統(tǒng)的Matlab 2012平臺。算法的參數(shù)設(shè)置如下：行交叉概率，列交叉概率，行變異概率，列變異概率，權(quán)重系數(shù)，延期訂單數(shù)量的懲罰系數(shù)為，所有訂單的延期時間懲罰系數(shù)均為，生產(chǎn)單元載荷均衡系數(shù)。

4.2 算法對比

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

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

問題規(guī)模（訂單數(shù)×拆解任務(wù)數(shù)）改進(jìn)GA算法 改進(jìn)PSO算法fmin fmin.avf Tavg fmin fmin.avf Tavg 10×5 30.32 34.56 57.16 42.20 47.31 72.13 10×7 55.41 57.32 62.58 61.34 65.22 76.34 10×9 66.51 67.74 69.34 66.67 72.21 84.21 20×7 133.19 130.23 83.54 125.13 140.12 102.18 20×10 175.07 179.34 87.28 182.30 186.80 124.56 20×16 287.59 292.23 88.40 285.37 288.21 153.95 30×8 333.04 337.21 107.64 350.25 359.71 198.18 30×15 360.74 363.80 112.02 371.34 380.23 232.12 30×20 382.23 387.26 119.02 385.21 397.56 257.80

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

圖3 延期訂單數(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é)語

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

參考文獻(xiàn)

［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］劉愛軍，楊育，邢青松.柔性作業(yè)車間多目標(biāo)動態(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é)報，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.