基于訂單拆分生產的MTO企業生產調度及算法研究*

姜 康 咸 凱 郝 宇

(合肥工業大學汽車與交通工程學院，安徽 合肥 230009)

隨著工業化進程的不斷加快，消費者的需求不斷變化，企業在激烈的市場競爭中也必須適應消費者需求的變化。但是面對多變的消費需求，企業往往難以安排相應的生產或做出合理的訂貨決策，易出現供需不匹配的現象。在這種情況下，MTO模式由于其具有機動、靈活的特點，且能有效避免企業錯誤估計消費者需求導致供需不匹配的現象，而被越來越多的企業所采用[1]。

在MTO生產模式下，生產調度方案是影響企業利潤的重要因素，引起了國內外學者與企業管理人員的深入研究。初紅艷等人采用多智能體技術建立基于加工單元的制造車間調度系統結構，并采用遺傳算法來確定工件的合理加工工序及各工序所用設備[2]。張鐵男等人研究了生產資源受限情況下的車間調度問題，并提出了優化車間調度的方案[3]。劉紅軍等人研究了車間調度的本質，提出了一種基于GA-SA-TS算法的車間調度方法，三種算法相互結合避免了遺傳算法局部搜索能力差和易早熟的缺點，大大提高了調度模型求解結果的準確性[4]。Chen等人研究了靜態和動態生產環境下訂單排產問題，并建立了求解訂單排產順序的數學模型[5-6]。Oguz等人針對單機環境提出訂單排產的決策模型，設計了求解方法并將求解結果用于車間調度[7]。JC Tay，NB Hod等人指出傳統的派工規則由于考慮不周全導致了企業績效較低，并通過遺傳進化的方法合理安排訂單的加工順序[8]。劉亮等人將APS系統和MES系統進行集成,從軟件系統集成的角度研究了生產計劃和調度方法[9]。雖然目前對車間調度研究較多，但是當前的研究存在以下問題：(1)在研究車間級的調度方案時，研究只著重于產品的工序調度，忽略了訂單排產調度問題；(2)對訂單排產的研究大多是在企業級調度層面，這種企業級的訂單排產調度過于粗放；(3)對訂單排產調度的研究多是基于訂單不可拆分生產的原則進行的。當多個訂單中出現一個訂單量較大的訂單時，傳統的調度方案易導致較小的訂單提前完工或延期交付，從而增大加工成本。因此，針對MTO企業車間調度問題應進行深入研究，建立適應于MTO企業的車間調度方案并設計有效的求解方法。

本文在深入調研MTO企業生產特點的基礎上，提出了包括訂單排產和產品工序調度的MTO企業車間二級調度方案，并科學篩選影響訂單排產的因素，基于訂單可拆分生產的原則，建立了用于車間訂單排產的非線性規劃模型。為了克服遺傳算法容易陷入局部最優解和非線性尋優算法對初始解要求高的缺點，本文運用基于非線性尋優的遺傳算法求解車間訂單排產模型。

1 車間二級調度方案

在綜合考慮MTO企業車間生產特點的基礎上，根據實際情況可將車間的一個計劃期劃分為若干個計劃時段，建立車間二級調度方案——訂單排產調度和產品工序調度：前者負責整個計劃期內的宏觀排產；后者負責各個計劃時段的加工調度。

1.1 車間級訂單排產調度

車間級訂單排產調度是指企業在計劃期開始時，根據各訂單的規模、交貨期以及其它經濟參數安排各訂單的生產計劃，使得企業的整體利潤最大。傳統的訂單生產策略，如：先到先服務(FCFS)策略以及最早交貨期優先(EDD)策略，每個訂單都是連續生產的且訂單一旦投入生產不能中斷訂單生產。在這種情況下，如果存在訂單量較大的訂單時，在綜合排產時往往會出現其他訂單提前完工或延期的現象，從而導致企業的相關成本增大。

基于訂單可拆分的車間級訂單排產調度，會根據車間以及訂單的信息，合理地將訂單安排到計劃期內的各個時段上。在生產過程中可以根據需要將某些訂單拆分生產，且在計劃期內的各計劃時段上可以同時生產多個訂單。基于訂單可拆分生產的車間級訂單排產調度，可以有效減少因個別訂單過大導致其他訂單無法按時交貨的情況，同時降低其他訂單因提前完工而造成的不必要的庫存成本。

1.2 車間級工序調度

車間級工序調度負責將一個計劃時段內的所有工件的工序合理地分配到各設備上，使得在一個計劃時段內的生產時間最短，縮小生產成本，達到增大企業生產利潤的目的。

當前對車間級工序調度的研究已經十分深入，并且在MTO企業得到了廣泛應用。大多數研究是在考慮不同影響因素的基礎上，建立工序調度數學模型并通過算法對模型進行求解，最后根據求解結果進行調度。

1.3 調度流程

由圖1可以看出，訂單被安排到車間之后，一方面，車間需要進行相關生產資源的準備；另一方面，需要根據車間接受的各訂單以及車間自身信息，合理地進行排產調度以及工序調度，達到最小化生產成本、提高企業利潤的目的。由于對車間級工序調度的研究十分深入，因此本文著重于研究車間級訂單排產調度。

2 車間級訂單排產調度模型

2.1 因素選取

影響訂單生產調度的因素眾多，因此需要對這些因素加以分析，科學、系統、完善地選取合適的因素進行建模。企業的首要目標是創造利潤，企業的生產能力、生產成本、庫存成本是影響企業獲利的直接因素。但是企業利潤的大小不僅僅取決于企業自身的情況，訂單本身也是影響企業利潤的關鍵因素，例如訂單大小、訂單價格、交貨期、延期懲罰、顧客的潛在價值等[10]。因此可將影響訂單生產調度的因素分為兩個層次共8個指標(見圖2)，在建模的過程中需要從這些因素的角度進行分析和考慮。

2.2 模型假設與問題描述

為了降低建立模型的復雜度，根據車間級訂單排產調度特點，本文進行如下的假設：

(1)企業生產能力固定，每個計劃時段內的產出不能超出企業的生產能力。

(2)訂單可以提前完工，但不能提前交貨。如果訂單提前完工，那么訂單必須在規定的交貨期進行交付；如果訂單沒有提前完工，那么訂單在加工完成后必須立即交付。

(3)客戶只關心訂單能否按期交貨，不關心生產過程中訂單是否拆分生產。

基于訂單可拆分生產原則以及上述假設，車間級訂單排產調度問題可以描述為：

在企業最大生產能力A約束下，將訂單O={O1,O2,O3,…,On}合理分派到計劃期內各計劃時段上；在進行訂單分配的時候，可以根據訂單量和交貨期的需要將訂單拆分生產以獲得更高的利潤。

2.3 模型建立

根據上述假設，基于訂單可拆分生產的原則，建立如下所示的車間訂單排產調度模型。

Li表示訂單i的大小(件)；Mi表示訂單i的單位產品扣除生產成本的利潤(元)；Vi表示訂單i的潛在價值；TDi表示訂單i的延期時間；Di表示訂單i的單位產品延期懲罰系數(元)；Rit表示訂單i在第t計劃時段的庫存占用量；Wi表示訂單i的單位產品庫存成本(元)；φ表示每次調整車間生產任務的成本(元)；Sit表示訂單i在第t時段的狀態，1為生產，0為不生產；TOi表示訂單i的理論交付期；TRi表示訂單i的實際交付期；TEi表示訂單i的完成時間；Ait表示訂單i在Tt時段占用企業的生產能力(件/計劃時段)。

目標函數是考慮在扣除延期懲罰、庫存成本以及由于訂單拆分生產造成的企業設備調整費用之后的企業利潤(包括顧客的潛在價值)；式(1)表示在當前時段所有正在生產的訂單所需要的生產能力之和小于企業的最大生產能力；式(2)表示每個訂單必須在計劃期內完成；式(3)表示訂單i的實際完成時間等于整個計劃期上訂單最后一次生產所在計劃時段；式(4)表示訂單i的延期時間；式(5)表示訂單i的實際交貨期，如果訂單沒有延期，則等于訂單的理論交貨期，否則等于訂單的實際完工時間；式(6)表示訂單i在t時段的庫存量，企業并不是只將提前完工訂單的全部產品放入倉庫，也會將未完成訂單但已完工的產品放入倉庫；式(7)表示顧客的潛在價值，是關于延期時間TDi的減函數；式(8)表示訂單i在第t時段的狀態，1為生產，0為不生產。

2.4 模型分析

本文所建立的調度模型屬于非線性規劃模型。非線性規劃問題是一個NP-hard問題，目前常用的求解方法有模擬退火方法、遺傳算法、粒子群算法、非線性尋優算法等，這些算法在不同的領域均得到了成功應用。但是它們也存在著自身的缺點：模擬退火算法搜索過程緩慢；遺傳算法雖然搜索速度快，但是容易陷入局部最優解；粒子群算法對離散問題處理不佳，容易陷入局部最優；非線性尋優算法搜索速度慢，對初始解要求高。考慮到在實際的工業生產中，需要快速得到調度結果，因此遺傳算法適合用來解決這個問題。同時，為了解決遺傳算法容易陷入局部最優解的缺點，本文在深入研究非線性規劃問題常用的求解方法的基礎上，將遺傳算法和非線性尋優算法結合起來求解訂單排產調度模型。

3 基于非線性尋優的遺傳算法

3.1 基于非線性尋優的遺傳算法

遺傳算法搜索速度較快，但容易陷入局部最優解，適合在可行解集內進行大范圍搜索；非線性尋優算法搜索速度慢，對初始可行解要求高，但結果較為精確，適合局部尋優[11]。

為解決遺傳算法和非線性尋優算法的缺點，本文采用了一種基于非線性尋優的改進的遺傳算法，首先利用遺傳算法進行全局搜索，當達到進化代數N以及其整數倍時采用非線性尋優算法進行局部搜索，具體流程如圖3所示。該算法結合了非線性尋優和遺傳算法的優點而彌補了其不足，具有搜索速度快、結果精確度高的特點。

3.2 遺傳算法設計

3.2.1 編碼方式與適應度函數

在本算法中設計了一種基于時序的整數編碼方式。圖4是一具有兩個訂單，每個計劃期有5個時段的染色體。因為有2個訂單且每個計劃期有5個時段，所以在染色體中需要10個基因，前5個基因代表第一個訂單，后5個基因代表第二個訂單；每個基因上的數字，表示訂單在相應時段上的生產數量。

本文將模型的目標函數作為遺傳算法的適應度函數。

3.2.2 遺傳算子

選擇：采用比例選擇算子執行選擇操作。

交叉：采用改進的兩點交叉策略：選擇父染色體中相同訂單編號對應的基因，互換位置進行交叉。如圖5所示，P1和P2是具有3個訂單的父染色體，選擇P1和P2中訂單2對應基因，互換位置進行交叉，得到子染色體C1和C2。

3.2.3 遺傳算法參數設置

啟發式遺傳算法作為人工智能領域中用于解決最優化問題的一種搜索算法，其參數的設置至關重要。本文在查閱相關文獻[12-15]的基礎上，結合多次實驗的結果確定了本問題中遺傳算法的最優參數:種群數為50，交叉概率為0.6，變異概率為0.01，采用精英策略。種群每進化N=10代進行一次非線性尋優。

3.3 經典非線性尋優算法

本文非線性尋優算法采用梯度下降法求解，利用目標函數以及約束函數信息，從給定的初始點開始，在滿足約束條件下，沿目標函數梯度下降的方向迭代，逐步收斂到最優解。多維優化問題一般情況下會存在多個局部最優解，所以本文將非線性尋優算法用作局部尋優。

4 調度實例

為了便于直觀分析調度結果，在本調度實例中假設各訂單的單位產品的利潤、單位產品延期懲罰、單位產品庫存成本以及客戶潛在價值均相同。

考慮3個訂單，一個計劃期有7個計劃時段，企業最大生產能力為35單位產品情況下訂單排產調度問題。訂單具體信息如表1所示：訂單1規模較大，交貨期較晚，如果調度不當，容易導致訂單2和訂單3的延期交付或提前完工，造成不必要的延期懲罰以及庫存成本，減少企業利潤。

運用改進的遺傳算法對該問題進行求解，得到遺傳算法進化曲線(見圖7)以及訂單排產結果(見表2)。

如圖7所示，隨著進化代數的增大，種群中最優個體的適應度函數值(即企業利潤)不斷增大；當進化代數達到60代左右時，種群收斂到最優個體。由于種群每隔10代進行一次非線性尋優，所以在第10、20、40代，種群最優個體適應度函數出現階梯式增長，說明了基于非線性尋優的遺傳算法的有效性。

表1 訂單信息表

訂單標號訂單大小/件交貨期/時段單位產品利潤/元單位產品延期懲罰/元單位產品庫存成本/元客戶潛在價值/元訂單1110718737訂單252318737訂單364518737

表2 基于訂單拆分的調度結果

訂單編號第1時段/件第2時段/件第3時段/件第4時段/件第5時段/件第6時段/件第7時段/件利潤/元訂單10003463535訂單2017350000訂單316180129003230

表3 基于EDD的調度結果

訂單編號第1時段/件第2時段/件第3時段/件第4時段/件第5時段/件第6時段/件第7時段/件利潤/元訂單100024353516訂單2351700000訂單301835110002890

如表2所示，由于訂單1規模較大且交貨期較晚，所以在第1時段至第3時段并未安排生產，第4至7時段大量生產；由于訂單2規模較小且交貨期較早，所以訂單2在第2、3時段大量生產；由于整個計劃期的前半部分大量生產訂單2，后半部分大量生產訂單1，所以訂單3根據實際情況進行了拆分生產。

根據EDD原則進行車間級訂單排產調度，調度結果見表3。由表3可知，由于訂單不可拆分生產，導致了訂單2和訂單3的提前完工，增大了庫存成本，進而導致了整體利潤的降低。

通過對車間級訂單排產調度進行仿真以及其與傳統調度方法的對比可以發現：基于訂單可拆分生產的調度方案，由于其可以根據訂單以及車間信息對訂單的生產順序進行合理規劃，因此可以有效減少各訂單的提前期或延期時間，從而減少生產成本，增大企業利潤；傳統的EDD調度方案由于訂單不可拆分，訂單一旦投入生產，在生產過程中不得中斷訂單的生產，易增大訂單的庫存成本或延期懲罰，從而降低企業利潤。

5 總結與展望

針對MTO企業生產調度問題，本研究做了大量工作：

(1)本文在深入研究MTO企業車間調度特點的基礎上，設計了MTO企業車間二級調度方案。

(2)通過科學選取影響訂單排產調度的變量，基于訂單可拆分生產的原則，本研究建立了車間級訂單排產調度模型。

(3)將非線性尋優算法和遺傳算法相互結合來改進遺傳算法，將改進的算法應用于求解車間訂單排產調度模型，并通過算例驗證了該算法的有效性。

當前對MTO企業調度的研究僅從車間調度的角度出發考慮問題，今后應當將訂單接受與訂單調度聯合考慮，使企業訂單接受決策和車間制造有機結合以提高企業利潤。

[1]范麗繁. 基于收益管理的MTS和MTO企業的供需管理研究[D].成都：電子科技大學, 2012.

[2]初紅艷, 曹全軍, 費仁元. 基于加工單元的制造車間的生產調度研究[J]. 北京工業大學學報, 2006, 32(8):730-736.

[3]張鐵男, 韓兵, 于渤. 生產能力約束條件下的柔性作業車間調度優化[J]. 系統工程理論與實踐, 2011, 31(3):505-511.

[4]劉紅軍, 趙帥, 趙雷. 一種基于GA-SA-TS算法的車間調度方法的研究[J]. 制造技術與機床, 2012(3):120-123.

[5]Kejia Chen, Ping Ji. A mixed integer programming model for advanced planning and scheduling(APS)[J]European Journal of Operational Research, 2007,181(1):515-522.

[6]KJ Chen, P Ji. A genetic algorithm for dynamic advanced planning and scheduling (DAPS) with a frozen interval[J].Expert Systems With Applications, 2007,33(4):1004-1010.

[7]OgUz C, Salman F S, Yal?n Z B. Order acceptance and scheduling decisions in make-to-order systems[J]. International Journal of Production Economics, 2010, 125(1):200-211.

[8]Tay J C, Ho N B. Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems[J]. Computers & Industrial Engineering, 2008, 54(3):453-473.

[9]劉亮, 齊二石. 基于APS與MES集成的車間生產計劃和調度方法研究[J]. 制造技術與機床, 2006(9):24-28.

[10]唐麗春, 蔡曉毅. 供應鏈環境下訂單優先權確定[J]. 系統工程理論與實踐, 2009, 29(9):41-46.

[11]史峰. MATLAB智能算法30個案例分析[M].北京：北京航空航天大學出版社, 2011:17-26.

[12]Wu C, Chang C, Chu T. The optimization of parameters for target tracking filter by genetic algorithm and taguchi method [J]. Pakistan Journal of Statistics, 2012, 28(1):167-176.

[13]何大闊, 王福利, 賈明興. 遺傳算法初始種群與操作參數的均勻設計[J]. 東北大學學報:自然科學版, 2005, 26(9):828-831.

[14]劉克剛, 朱福喜, 朱碧穎,等. 遺傳算法參數的動態優化方案[J]. 小型微型計算機系統, 2015(4):768-772.

[15]何大闊, 王福利, 賈明興. 遺傳算法初始種群與操作參數的均勻設計[J]. 東北大學學報:自然科學版, 2005, 26(9):828-831.