基于改進型批決策與調度建模的生產計劃調度系統的研究*

花季偉，李曉婷

(1.天津師范大學計算機與信息工程學院，天津 300074；2.河北省新聞出版廣電監管中心局，河北 石家莊 050031)

基于改進型批決策與調度建模的生產計劃調度系統的研究*

花季偉1，李曉婷2

(1.天津師范大學計算機與信息工程學院，天津 300074；2.河北省新聞出版廣電監管中心局，河北 石家莊 050031)

熱軋型鋼生產工藝復雜，其生產中極易出現由于計劃調度安排不當而產生的交貨期延誤、庫存超負荷等問題。針對以上問題研究設計了MES生產計劃調度系統，改進了批決策調度策略用于數學建模，利用自適應遺傳算法求解生產調度計劃。以此為基礎，為某熱軋企業設計實現了生產計劃調度系統，并通過真實的熱軋型鋼訂單、原料、設備等數據，對模型改進前后的計劃編制方法進行模擬與比較，驗證了利用該改進型批決策與調度模型編制的熱軋型鋼生產調度計劃可節省生產時間、降低設備調度時間，以此來指導熱軋型鋼的生產可切實減少交貨延誤和減少庫存占用率，并提高企業利潤率。

生產計劃與調度；熱軋型鋼；批決策與調度；遺傳算法

1 引言

合理的生產計劃與調度是保證企業長期規劃順利、順暢實施和企業生產能力充分發揮的關鍵所在[1]。制造執行系統MES(Manufacturing Execution System)旨在加強物料需求計劃的執行功能，把物料需求計劃通過執行系統同車間作業現場控制系統聯系起來。生產計劃與調度系統是MES系統的重要組成部分。但是，由于熱軋型鋼的產品規格眾多、生產工藝復雜，以至于國內自主研發的面向熱軋型鋼的MES系統并不多見。并且在實際生產中常常以人工操作進行生產計劃的編制與生產調度操作，由此計劃與調度方案往往難以達到較優水平。本文以某中型鋼鐵企業的實際生產調度為基礎，以提高企業利潤、優化生產方案為目標，研究了面向中型企業的MES生產計劃調度系統，其主要功能包括計劃編制、生產調度與核發等。

現有的熱軋生產與調度計劃建模策略主要有串行和并行兩種。其中，串行建模策略[2]屬于貪婪策略且容易陷入局部最優；并行策略[3]的數學模型模型每運行一次得到多個軋制單元，但是多個軋制單元之間的生產順序無法確定，當對軋制單元排序后容易出現大量鋼坯拖期的現象。針對以上策略的優缺點，文獻[4～6]論述了一種新的并行建模策略，它集成了批決策與調度問題，在組批過程中考慮了軋制單元之間的生產順序以及交貨日期等時間因素。但是，它也有局限性，即計劃編制軋制單元的數量需為固定數值。而目前求解計劃編制問題時通常采用智能優化算法，它們能較好地解決復雜系統中出現的組合爆炸問題，常見的有模擬退火算法、粒子群算法、神經網絡算法、蟻群算法、遺傳算法等等[7]，其中被應用最廣泛的是遺傳算法[8,9]。

2 生產計劃與調度系統設計

2.1 問題描述

生產計劃的求解問題是極其復雜的：解的數量巨大，不易尋求最優解；計劃必須滿足負荷工藝約束條件，具有可行性；評估每一個解的優劣很費時等等。并且，如果編制以單個鋼坯為單位的生產計劃，這個求解的過程將更加復雜。在以往的實際熱軋型鋼生產中，生產計劃的編制為了達到減少更換軋輥次數、降低生產產品的波動性，經常按照班次或者軋輥的最大軋制重量來編制生產單元。為湊滿一個生產單元，經常需要憑借人工經驗來調整生產計劃，這樣編制的計劃很難成為較優的方案。

生產計劃的編制受到眾多條件的制約，例如在軋制生產線上如何調度各個生產環節設備的使用，最大化地利用設備產能，而又要考慮到設備的檢修維護，以確保設備的使用壽命和產品的質量；在不同鋼種、規格和交貨期需求下訂單的組批，既要保證不能延誤交貨期，又要盡量減少庫存的積壓；如何調度鋼坯的使用以縮短生產周期、確保生產的順利進行等等。生產計劃編制完成，執行生產計劃的過程中依然充滿了干擾因素。如緊急訂單的加入、設備故障、原料鋼坯不到位等，當面對此類事件時計劃的調整、實際生產的配合調度就需要及時發揮作用。生產計劃的及時調整，既要滿足訂單的生產需要，又要保證整體計劃實施的穩定性。生產調度既要保證原材料鋼坯的及時調度到位，又要考慮熱軋前加熱爐的充分使用與不同加熱爐之間的配合。所以，建立一個高效準確、可靈活應對突發事件而做出調整的計劃自動編制系統具有重要意義。

2.2 系統設計及功能描述

本系統設計以可靠性、實用性、易維護性和行業特殊性為原則，從河北某熱軋型鋼企業的特點出發，如產品品種繁多、型號規格復雜、訂單數目大、訂貨噸位少、軋鋼軋輥需根據成品種類變換等等，并且還兼顧此行業的通用性，避免同行業重復開發造成浪費。該MES生產調度系統采用瀏覽器/服務器模式，簡稱B/S模式(Brower/Server)，它可以大大簡化客戶端電腦的載荷，減少系統升級和維護的工作量，以降低總體成本。生產調度系統的功能模塊如圖1所示。

Figure 1 Function modules圖1 系統功能模塊設計

生產計劃與調度系統主要模塊的功能如下：

(1)銷售訂單轉換：銷售訂單指客戶對軋鋼企業購買成品下達的訂單，包括交易金額、數量、交貨日期等信息；生產訂單指包括了原料、鋼種、規格等生產參數的用于車間作業的指導性文件。兩者的轉換加上系統讀取的原料、設備等基礎數據，進行原料損耗的計算，使得生產更加精確。

(2)生產計劃編制：根據訂單要求以及生產約束等信息編制生產計劃。

(3)生產計劃修改與調整：有緊急訂單、設備故障、鋼坯等原料不到位等擾動出現時，則需要對生產計劃執行時間、優先級等參數進行調整，調整完畢后系統自動重新編制新的生產計劃。如即將執行的計劃，正常情況下數據庫中的狀態位為0，當鋼坯供應未到位時狀態位為1，此時就會觸發生產計劃與調度系統的擾動處理程序，臨時調用其他計劃下已就位的鋼坯。若無鋼坯可調用，系統自動修改該計劃的優先級狀態位，重新編制未完成的訂單的生產順序；同時系統界面對工作人員進行預警提示，工作人員可隨時停止或者調整計劃的實施。

(4)生產計劃核發與調度：調度原料與設備的使用，核實調度情況，確認開始生產。

3 生產計劃與調度模型與遺傳算法

3.1 難點分析

熱軋型鋼生產計劃與調度的最主要對象為原材料鋼坯，它的使用狀況、調度狀態直接影響著生產能否順利進行。鋼坯調度原則是優先清庫存，并且當鋼坯還未鑄造完成時，在計劃中將產生一個虛擬的鋼坯號以表示未入庫的鋼坯。計劃的編制過程需要從可選用的鋼坯中選出訂單要求的數量，依據工藝約束等信息將其編制為若干個軋制單元。在傳統生產中，生產計劃的編制為了達到減少更換軋輥次數、降低生產產品的波動性，經常按照班次或者軋輥的最大軋制重量來編制軋制單元。為湊滿一個軋制單元，經常需要憑借人工經驗來調整生產計劃，這樣編制的計劃很難成為較優的方案，并且人工的計劃與調度經常造成生產不能按時完成，以至于合同交貨期的延誤，又如不合理的生產計劃易導致成品不合理地長期占用庫存等問題。

3.2 改進型批決策與調度模型

批決策與調度是一種新的并行策略，在組批過程中同時考慮到了軋制單元之間的生產順序以及交貨期等時間因素。批調度就是要確定軋制單元之間的生產順序和時間表，進而確定各軋制單元中鋼坯的生產順序。

首先對數學模型中的參數和變量進行說明：n為訂單總數；x若為j訂單不拆分且在i訂單之后生產，則xij為1，否則為0；tij為i訂單之后生產j訂單的時間，且j訂單不拆分，若i訂單和j訂單為不同品種則其中包括換軋輥的時間；m為j訂單拆分為m個部分生產；當j訂單的第k部分在i訂單之后生產，則yij為1，否則為0；tijk為在i訂單之后生產j訂單的第k部分，若i訂單和j訂單為不同品種則其中包括換軋輥的時間；t為換輥時間、換軋輥導衛時間、設備檢修時間等余量時間總和；Tj為j訂單的交貨時間；τs為當前系統時間；g為相鄰兩次換軋輥之間的訂單的原料重量；G為軋輥最大軋制重量；τz為所需鋼坯的連鑄完成時間；τr為鋼坯經過加熱爐到達軋機的時間；τi為i訂單開始生產的時間；τΔ為前一個訂單生產完和后一個訂單開始生產之間的時間差；Pmin為相鄰兩次換軋輥之間軋制的最小鋼坯數；p為相鄰兩次換軋輥之間軋制的鋼坯數；Pmax為相鄰兩次換軋輥之間軋制的最大鋼坯數；gt為存放在成品庫里的成品重量；Gc為最大庫存量。

傳統批決策與調度的數學模型可描述為：

目標函數為：

(1)

約束條件為：

(2)

(3)

(4)

其中，目標函數式(1)表示盡量使總生產時間最短；約束條件式(2)表示合同交貨期窗口約束，生產計劃盡量使合同拖期總懲罰最小，即滿足交貨時間Tj；約束條件式(3)表示鋼坯的重量約束，軋制完成一定重量的鋼坯后，軋輥軋制能力已大幅度下降，需要更換軋輥；約束條件式(4)表示時間窗約束，即生產訂單的開始生產時間τi應保證在鋼坯連鑄完成時間τz之后，或者滿足鋼坯庫中可以直接調用的鋼坯經過加熱爐后到達軋機的時間τr。

為了適應熱軋型鋼的品種規格多、生產數量靈活、軋制工藝復雜等特點，對現有的批決策與調度模型進行改進。即以生產一個訂單所需的一批鋼坯為組批單元來編制生產計劃，且完全放開軋制單元的數量限制，也可稱為可拆分訂單的計劃編制模型。就是一個生產訂單可以以約束條件為基礎拆分成若干部分，它們與其他生產訂單或其他訂單的某些部分，混合編制生產計劃，如圖2所示。

Figure 2 Split production order圖2 生產訂單的拆分

熱軋生產調度計劃需要在不同鋼種、規格和交貨期需求下訂單的組批，既要保證不能延誤交貨期，又要盡量減少庫存的積壓；在軋制生產線上如何調度各個生產環節設備的使用，最大化地利用各個設備的產能，而又要考慮到設備的維護。計劃的編制要盡量減少總的生產時間，以確保真正地降低成本。

該問題的數學模型可描述為：

目標函數為：

(5)

約束條件為：

(6)

(7)

(8)

(9)

(10)

(11)

(12)

目標函數式(5)表示盡量使總生產時間最短，跟傳統模型相比，由于加入了拆分訂單的因素，所以目標函數式也變為由不拆分的和拆分的訂單的生產時間相加。約束條件式(6)～式(8)同傳統模型相同。根據熱軋型鋼企業的生產特點，如不同品種型鋼需要不同的軋輥軋制等，約束條件式新增了：(1)約束條件式(9)表示同品種合并生產約束，在一個生產訂單生產完畢后，如果軋輥還未達到軋制限制量并且和下一生產訂單的最遲生產時間之間有余量，可以將同品種的訂單提前一部分合并生產；(2)約束條件式(10)表示相鄰兩次換軋輥之間的軋制鋼坯數必須達到計劃人員規定的上下限；(3)約束條件式(11)表示鋼坯調度約束，保證一塊鋼坯只出現在一個軋制單元中，保證鋼坯處理的唯一性；(4)約束條件式(12)表示庫存約束，編制計劃時應考慮提前完成訂單時庫中是否有能力存入此批成品，并且盡量減少成品庫存的占用。

3.3 遺傳算法求解

遺傳算法將問題的求解表示成“染色體”的適者生存過程，通過“染色體”群的一代代不斷進化，最終收斂到“最適應環境”的個體，從而求得問題的最優解或滿意解。相比其他算法，遺傳算法的編碼技術和遺傳操作比較簡單，算法進行全空間并行搜索，從而能夠提高效率且不易陷入局部極小[8,9]。為了求解改進型批決策與調度的生產調度計劃編制模型，系統采用了自適應遺傳算法[10]。傳統遺傳算法中交叉概率和變異概率是固定的，為了提高遺傳算法的收斂速度，將其設置改為自適應遺傳算法的交差概率pc和變異概率pm，計算公式如下：

該遺傳算法的具體實施步驟如下：

步驟1模型初始化。在算法初始時進行模型轉換及約束處理，根據生產工藝流程和相關參數的模型初始化，并施加相關約束。

步驟2初始化種群。對生產訂單進行編碼，每個個體中包含表示訂單、重量、拆分標識等信息的基因。設定種群數量為50，隨機生成初始個體100個，通過計算其適應值來選出較優的50個個體作為初始種群。

步驟3求各個組合方案最優解。由于編制生產計劃時訂單數量的不確定性，在此為使計算簡化，直接將模型中的目標函數轉化為適應度函數。該目標函數為最小化問題，設定適應度函數為：

Figure 3 Interface of plan圖3 計劃編制界面

步驟4遺傳操作。選擇操作采用適應度比例方法即輪盤賭選擇法，且為了避免輪盤賭選擇法容易引起的早熟收斂和搜索遲鈍問題，在此采用有條件的最優保留策略進行輔助。對于交叉操作，使用由Reeves[10]提出的專門為調度問題設計的改進型單點交叉算子和部分映射交叉算子。為了滿足生產計劃調度的實際需要，即保證訂單的唯一性，改進型單點交叉流程在進行了傳統單點交叉操作之后，還需要進行對非交換位置基因的變換操作。為了提高遺傳算法的收斂速度，本文采用了自適應遺傳算法[11]的交差概率pc和變異概率pm。

步驟5重復步驟3和步驟4，直到達到預定迭代次數而終止，并輸出末代最優個體對應的問題解。

3.4 算例比較與分析

分別隨機取該熱軋鋼鐵企業的20個、50個不同實際銷售合同的數據作為第一組和第二組實驗數據。這些銷售合同包括多種成品種類，如方鋼、圓鋼、角鋼、工字鋼、乙字鋼等，并且有多種重量要求，如500噸、700噸、1 000噸、2 000噸等。按照成品種類的不同，銷售合同可以分解成若干生產訂單。生產中更換生產的成品種類或達到軋輥軋制噸數極限時必須更換軋輥，軋制噸數均設定為1 000噸，換輥時間設定為2小時。設定設備檢修日歷：每周一次小型檢修4小時，每兩周一次大型檢修15小時，檢修可與更換軋輥同時進行。在此熱軋型鋼MES項目中，利用ASP.NET技術制作了B/S模式的生產計劃與調度系統，并且選用了適合大型企業的Oracle數據庫作為支持。生產計劃調度系統的計劃編制界面如圖3所示。

以實際的生產計劃調度系統為運行環境，采用數據庫的數據庫語言對四種生產計劃排序方法進行編程：

方法一按照銷售合同中要求的交貨日期順序編制生產調度計劃。

方法二按照約束條件調整生產訂單的順序，如盡量滿足合同交貨期、滿足軋輥對鋼坯重量的限制等，且生產訂單不拆分。建立如式(1)～式(5)的傳統批決策與調度模型，以簡單的串行搜索算法進行求解。

方法三按照約束條件調整生產訂單的順序，如盡量滿足合同交貨期、滿足軋輥對鋼坯重量的限制等，且生產訂單不拆分。建立如式(1)～式(5)的傳統批決策與調度模型，以自適應遺傳算法進行求解。

方法四以改進型的批決策與調度策略建立模型，即加入訂單可拆分形式，并且以實際生產的特點擴充約束條件，如拆分合并約束條件。以自適應遺傳算法進行求解。

采用以上四種方法分別對第一組20個合同、第二組50個合同進行生產計劃編制的對比數據如表1和表2所示，其中第三種和第四種方法分別反復進行100次，取平均值。

Table1 Data comparison of 20 contracts’production planning for four methods表1 四種方法分別對20個合同的生產計劃編制數據對比

Table2 Data comparison of 50 contracts’production planning for four methods表2 四種方法分別對50個合同的生產計劃編制數據對比

由表1和表2中的數據可明顯看出，以改進型的批決策與調度策略模型為基礎的計劃，無論是20個合同還是50個合同的生產總時間、需要的檢修總時間，相較于簡單的按交貨時間順序排序、不拆分訂單的串行搜索排序所需要的時間都要短。特別是相較于普通批決策與調度模型得出的生產計劃調度方案，當合同數量較多時，改進的模型體現出了較大優勢。換輥次數的減少也對節約時間、降低能源消耗、減少勞力消耗、降低企業成本起到了很大作用。特別是新模型編制出的熱軋生產計劃調度方案，基本解決了延誤合同約定交貨期的問題，沒有了合同違約金，企業的利潤將有很大程度的提高。隨著合同數量的增加，最大庫存占用率越來越高，在50個合同的生產計劃編制數據中，方法一的庫存占用率已經超過了100%，已經無法滿足生產需要。而新模型的應用可以大大減少庫存占用率，對于企業在一定時期內合同數量的增加或者接大訂單生產有著重要的意義。

雖然改進型的批決策與調度模型在求解過程中更加復雜，使得解的種類大大提升。圖4所示為普通批決策與調度策略模型和改進后的模型的求解過程收斂圖，可明顯看出，改進型模型目標函數的收斂速度雖然相較于普通模型的收斂速度慢，但是改進型模型求得的解更優于普通模型的解，即節約了生產總時間。

Figure 4 Curve convergence of solution procedures圖4 求解過程收斂對比圖

4 結束語

本文以熱軋型鋼企業的項目為依托，研究設計了MES生產計劃與調度系統的各功能模塊。以批決策與調度和訂單排序的基本理論為基礎，改進了批決策與調度模型，并對實際鋼鐵企業的熱軋生產調度計劃的編制問題進行了求解。通過與普通模型求解計劃的橫向比較，以及不同數目、不同鋼種的訂單組合的縱向比較，驗證了改進的新模型求得的解可節約生產時間、提高產能，如此編制出的生產計劃調度方案可以大大降低熱軋型鋼企業的生產成本。

[1] Huang Xiao-ling, Chai Tian-you. Application of planning and sheduling cascade model of complex system processing to mineral processing MES system [J]. Acta Automatica Sinica, 2011,37(9):1130-1139.(in Chinese)

[2] Gao Zhi-xin, Li Tie-ke, Su Zhi-xiong. Application of memetic algorithm on slab sequencing[J]. Computer Engineering and Applications,2009,45 (19):192-194.(in Chinese)

[3] Chen Hao, Du Bin, Huang Ke-wei. PESAII algorithm for hot milling batch planning problem based on PCVRP[J].Control Engineering of China, 2012,18(S),86-88.(in Chinese)

[4] Xu Rui, Chen Hua-ping, Shao Hao, et al. Two kinds of ant colony algorithms to minimize the total completion time for batch scheduling problem [J]. Computer Integrated Manufacturing Systems, 2010,16(6):1255-1264.(in Chinese)

[5] Li Xue-bing. Development and application of assembly production management system with small batch and multi-items[J]. Modern Manufacturing Engineering, 2011(3):23-27.(in Chinese)

[6] Han Wen-min,Zeng Li-yi,Wei Yun-de,et al. Study on dynamic reconfiguration approach of manufacturing cell for make-to-order[J]. Process Automation Instrumentation, 2011, 32(3):29-35.(in Chinese)

[7] Gao Yang, Jiang Zi-bin. Using HGA to solve production planning in VE [J]. Control and Decision, 2007,22(8):931-934.(in Chinese)

[8] Cui Xue-li. Job shop schedule scheme based on hybrid genetic algorithm[J]. Computer Engineering and Design, 2011,32(7):2467-2471.(in Chinese)

[9] Pezzella F, Morganti G, Ciaschetti G.A genetic algorithm for the flexible job-shop scheduling problem [J]. Computers & Operations Research,2008,35(10):3202-3212.

[10] Srinivas M, Patnaik L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE Transactions on Systems, Man, and Cybernetics,1994,24(4):656-667.

附中文參考文獻：

[1] 黃肖玲,柴天佑. 復雜生產過程計劃調度級聯模型在選礦MES中的應用研究[J]. 自動化學報, 2011,37(9):1130-1139.

[2] 高知新,李鐵克,蘇志雄.Memetic算法在板坯排序中的應用[J].計算機工程與應用,2009,45(19),192-194.

[3] 陳浩,杜斌,黃可為. PESAII算法求解基于PCVRP的熱軋批量計劃問題[J].控制工程,2012,18(S):86-88.

[4] 許瑞,陳華平,邵浩,等. 極小化總完工時間批調度問題的兩種蟻群算法[J]. 計算機集成制造系統, 2010,16(6):1255-1264.

[5] 李學兵.小批量多品種裝配生產管理系統的開發與應用[J]. 現代制造工程, 2011(3):23-27.

[6] 韓文民,曾里義,魏允德.面向訂單生產的制造單元動態重構方法研究[J]. 自動化儀表, 2011, 32(3):29-35.

[7] 高陽,江資斌. 用混合遺傳算法求解虛擬企業生產計劃[J]. 控制與決策, 2007,22(8):931-934.

[8] 崔雪麗.基于混合遺傳算法的車間生產計劃調度[J].計算機工程與設計,2011,32(7):2467-2471.

HuaJi-wei,born in 1978,PhD,lecturer,CCF member(E200027582M),his research interests include computer software, and computer application.

李曉婷(1986-),女，河北石家莊人，碩士，研究方向為計算機控制與工程應用。E-mail:176307200@qq.com

LiXiao-ting,born in 1986,MS，her research interests include computer control and engineering application.

Studyofproductionplanningandschedulingsystembasedonbatchdecision-makingandschedulingmodel

HUA Ji-wei1,LI Xiao-ting2

(1.College of Computer and Information Engineering,Tianjin Normal University,Tianjin 300074；2.Hebei Press Publication Radio Film and Television Bureau,Supervision Center,Shijiazhuang 050031,China)

Due to the complexity of the hot rolled section steel production process, some problems such as delivery delay and overload inventory appear easily, which are induced by improper planning and scheduling. Aiming at these problems, the MES production planning and scheduling system is studied and designed. A mathematical model is formulated based on the improved batch decision-making and scheduling strategy. And the production scheduling plan is solved with self-adaptive genetic algorithm. Based on these theories, a production planning and scheduling system for a hot-rolled enterprise is designed and implemented. Through the real hot rolled steel’s orders data, raw materials data, equipment data and so on, the planning methods of using new batch decision-making and scheduling strategy model and old ones are simulated and compared. It is improved that the solution of batch decision-making and scheduling model is able to save production time, reduce the times of equipment scheduling. Using this plan to direct production activities can reduce the times of delay in delivery, reduce inventory occupancy rate and improve enterprise profit margin.

production planning and scheduling;hot rolling section steel;batch decision-making and batch scheduling;genetic algorithm

2012-07-21;

：2012-11-23

河北省基礎研究重點項目(09963536D);天津市高等學校科技發展基金計劃項目(20120814);天津師范大學博士基金資助項目(52XB1001，52X09013)

1007-130X(2014)02-0347-07

TP391

：A

10.3969/j.issn.1007-130X.2014.02.025

花季偉(1978-),男,天津人，博士，講師，CCF會員(E200027582M)，研究方向為計算機軟件及計算機應用。E-mail:huajiwei@yeah.net

通信地址：300074 天津市天津師范大學計算機與信息工程學院Address:College of Computer and Information Engineering,Tianjin Normal University,Tianjin 300074,P.R.China