基于訂單拆分生產(chǎn)的MTO企業(yè)生產(chǎn)調(diào)度及算法研究*

姜 康 咸 凱 郝 宇

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

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

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

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

1 車間二級調(diào)度方案

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

1.1 車間級訂單排產(chǎn)調(diào)度

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

基于訂單可拆分的車間級訂單排產(chǎn)調(diào)度，會根據(jù)車間以及訂單的信息，合理地將訂單安排到計劃期內(nèi)的各個時段上。在生產(chǎn)過程中可以根據(jù)需要將某些訂單拆分生產(chǎn)，且在計劃期內(nèi)的各計劃時段上可以同時生產(chǎn)多個訂單?；谟唵慰刹鸱稚a(chǎn)的車間級訂單排產(chǎn)調(diào)度，可以有效減少因個別訂單過大導(dǎo)致其他訂單無法按時交貨的情況，同時降低其他訂單因提前完工而造成的不必要的庫存成本。

1.2 車間級工序調(diào)度

車間級工序調(diào)度負(fù)責(zé)將一個計劃時段內(nèi)的所有工件的工序合理地分配到各設(shè)備上，使得在一個計劃時段內(nèi)的生產(chǎn)時間最短，縮小生產(chǎn)成本，達(dá)到增大企業(yè)生產(chǎn)利潤的目的。

當(dāng)前對車間級工序調(diào)度的研究已經(jīng)十分深入，并且在MTO企業(yè)得到了廣泛應(yīng)用。大多數(shù)研究是在考慮不同影響因素的基礎(chǔ)上，建立工序調(diào)度數(shù)學(xué)模型并通過算法對模型進(jìn)行求解，最后根據(jù)求解結(jié)果進(jìn)行調(diào)度。

1.3 調(diào)度流程

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

2 車間級訂單排產(chǎn)調(diào)度模型

2.1 因素選取

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

2.2 模型假設(shè)與問題描述

為了降低建立模型的復(fù)雜度，根據(jù)車間級訂單排產(chǎn)調(diào)度特點(diǎn)，本文進(jìn)行如下的假設(shè)：

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

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

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

基于訂單可拆分生產(chǎn)原則以及上述假設(shè)，車間級訂單排產(chǎn)調(diào)度問題可以描述為：

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

2.3 模型建立

根據(jù)上述假設(shè)，基于訂單可拆分生產(chǎn)的原則，建立如下所示的車間訂單排產(chǎn)調(diào)度模型。

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

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

2.4 模型分析

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

3 基于非線性尋優(yōu)的遺傳算法

3.1 基于非線性尋優(yōu)的遺傳算法

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

為解決遺傳算法和非線性尋優(yōu)算法的缺點(diǎn)，本文采用了一種基于非線性尋優(yōu)的改進(jìn)的遺傳算法，首先利用遺傳算法進(jìn)行全局搜索，當(dāng)達(dá)到進(jìn)化代數(shù)N以及其整數(shù)倍時采用非線性尋優(yōu)算法進(jìn)行局部搜索，具體流程如圖3所示。該算法結(jié)合了非線性尋優(yōu)和遺傳算法的優(yōu)點(diǎn)而彌補(bǔ)了其不足，具有搜索速度快、結(jié)果精確度高的特點(diǎn)。

3.2 遺傳算法設(shè)計

3.2.1 編碼方式與適應(yīng)度函數(shù)

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

本文將模型的目標(biāo)函數(shù)作為遺傳算法的適應(yīng)度函數(shù)。

3.2.2 遺傳算子

選擇：采用比例選擇算子執(zhí)行選擇操作。

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

3.2.3 遺傳算法參數(shù)設(shè)置

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

3.3 經(jīng)典非線性尋優(yōu)算法

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

4 調(diào)度實例

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

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

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

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

表1 訂單信息表

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

表2 基于訂單拆分的調(diào)度結(jié)果

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

表3 基于EDD的調(diào)度結(jié)果

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

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

根據(jù)EDD原則進(jìn)行車間級訂單排產(chǎn)調(diào)度，調(diào)度結(jié)果見表3。由表3可知，由于訂單不可拆分生產(chǎn)，導(dǎo)致了訂單2和訂單3的提前完工，增大了庫存成本，進(jìn)而導(dǎo)致了整體利潤的降低。

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

5 總結(jié)與展望

針對MTO企業(yè)生產(chǎn)調(diào)度問題，本研究做了大量工作：

(1)本文在深入研究MTO企業(yè)車間調(diào)度特點(diǎn)的基礎(chǔ)上，設(shè)計了MTO企業(yè)車間二級調(diào)度方案。

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

(3)將非線性尋優(yōu)算法和遺傳算法相互結(jié)合來改進(jìn)遺傳算法，將改進(jìn)的算法應(yīng)用于求解車間訂單排產(chǎn)調(diào)度模型，并通過算例驗證了該算法的有效性。

當(dāng)前對MTO企業(yè)調(diào)度的研究僅從車間調(diào)度的角度出發(fā)考慮問題，今后應(yīng)當(dāng)將訂單接受與訂單調(diào)度聯(lián)合考慮，使企業(yè)訂單接受決策和車間制造有機(jī)結(jié)合以提高企業(yè)利潤。

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

[2]初紅艷, 曹全軍, 費(fèi)仁元. 基于加工單元的制造車間的生產(chǎn)調(diào)度研究[J]. 北京工業(yè)大學(xué)學(xué)報, 2006, 32(8):730-736.

[3]張鐵男, 韓兵, 于渤. 生產(chǎn)能力約束條件下的柔性作業(yè)車間調(diào)度優(yōu)化[J]. 系統(tǒng)工程理論與實踐, 2011, 31(3):505-511.

[4]劉紅軍, 趙帥, 趙雷. 一種基于GA-SA-TS算法的車間調(diào)度方法的研究[J]. 制造技術(shù)與機(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集成的車間生產(chǎn)計劃和調(diào)度方法研究[J]. 制造技術(shù)與機(jī)床, 2006(9):24-28.

[10]唐麗春, 蔡曉毅. 供應(yīng)鏈環(huán)境下訂單優(yōu)先權(quán)確定[J]. 系統(tǒng)工程理論與實踐, 2009, 29(9):41-46.

[11]史峰. MATLAB智能算法30個案例分析[M].北京：北京航空航天大學(xué)出版社, 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]何大闊, 王福利, 賈明興. 遺傳算法初始種群與操作參數(shù)的均勻設(shè)計[J]. 東北大學(xué)學(xué)報:自然科學(xué)版, 2005, 26(9):828-831.

[14]劉克剛, 朱福喜, 朱碧穎,等. 遺傳算法參數(shù)的動態(tài)優(yōu)化方案[J]. 小型微型計算機(jī)系統(tǒng), 2015(4):768-772.

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