卷煙生產計劃排產模型建立與優化

金 劍，金 釗，祁躍東 JIN Jian,JIN Zhao,QIYuedong

1.紅塔集團玉溪卷煙廠，云南 玉溪 653100

2.云南大學 信息學院，昆明 650091

1.Hongta Group Yuxi Cigarette Factory,Yuxi,Yunnan 653100,China

2.School of Information Science,Yunnan University,Kunming 650091,China

1 引言

盡管很多卷煙企業采用了ERP軟件的排產調度模塊，但核心算法與軟件受制于人，卷煙詳細排產主要采用人工根據經驗進行各卷煙牌號的排產，排產方案的優劣取決于人工經驗，ERP的模塊更多是作為一種生排程優化功能。隨著卷煙“一點控制、多點生產”的協同制造格局快速形成，產品需求小批量、多牌號發展及各種生產工藝約束限制，這種模式影響卷煙生產排產效率和快速反應能力的提高，難以對制造資源進行全面優化配置，妨礙了對生產運作過程的優化[1-3]。

由于生產排程問題本身屬于NP難問題，尋求最優解比較困難[3]。卷煙生產排產不僅要處理錯綜復雜的約束條件，還要從“無窮”多種滿足約束的可行方案中找到優化排程方案，這是ERP計劃模塊面對的真正瓶頸問題，其中的關鍵在于算法。因此，迫切需要開展卷煙生產排產調度優化技術研究。

圖1 卷煙生產流程

卷煙生產包括了離散式模型，如卷包機組排產，主要是解決多機組，多資源的優化調度問題；流程式模型，如制絲線生產，主要是解決順序優化問題；多點生產組是解決成本優化問題[2-3]。因此需要建立各環節的排產數學模型，開發煙草行業高級計劃排程算法，在給定約束：設備資源、生產任務訂單、工藝要求、生產成本、運輸成本等約束條件下，快速對卷煙生產計劃進行優化，實現各種優化目標如：總生產成本最低、庫存最少、完工時間最短、換牌次數最少、提高設備運行效率、平衡設備負荷，以達到產能均衡的目的；以實現敏捷制造、精益化生產[4-7]。

2 卷煙生產排產優化流程分析與設計

2.1 卷煙生產簡介

香煙的生產是一個復雜的工藝流程，其生產線包括了諸多環節。從工藝上，可以將整個生產線抽象為兩個相對獨立的環節：制絲和卷接。它們中間存在一個緩存區，即儲柜，用來存儲半成品煙絲，制絲通過加絲機對卷包進行煙絲供應。生產出的卷煙封箱后存入成品高架庫，供銷售發貨。某生產點基本生產流程如圖1所示。

其余各點生產流程基本類似，區別在于卷包設備機型、數量存在差異；同時各生產點生產成本、運輸成本存在差異。

2.2 卷煙排產遞階優化流程設計

為適應市場對產品需求的快速變化，根據實際卷煙生產計劃業務，采用分層遞階設計相應的優化流程。通過市場定單需求與銷售預測，形成月度銷售進度計劃；根據月度銷售計劃制定周滾動生產計劃，經過優化分解處理為各個生產點生產計劃；各生產點利用詳細排產模型自動生成生產進度計劃。在構建排產模型時，從上至下地考慮各個層次的目標函數和約束條件，較高層次的任務分配模型優化結果作為下一層各生產點的約束。同時，較低層次各生產點的實際生產情況實時反饋給上一層，用以調整上層計劃。以此更好地預測和指導生產，響應市場需求。根據上述步驟，把整個生產計劃優化模型分成兩個層次。詳細流程如圖2所示。

（1）需求分配模型：根據集團銷售計劃部門制定的月總生產計劃，分解為周滾動計劃，考慮各生產點生產能力、生產運輸成本、工藝約束，進行成本的優化。對總生產計劃進行分解，利用生產點需求分配模型自動將周計劃分解為各生產點的任務列表-各牌號的卷煙計劃箱數。

（2）各生產點的生產排程模型：根據上一層模型分配到每個生產點的需求計劃，考慮各點的設備資源，工藝約束，對卷接環節進行排產，優化出每日生產進度計劃，即每天各加絲機上生產某種品牌香煙的箱數，再通過加絲機與間接機組的配置關系，把加絲機任務按機組能力進行分解，得到每個機組的派工單。

制絲環節優化模型：根據卷接環節優化結果和儲絲柜調度計劃，在滿足卷包環節銜接需求的約束下，根據卷煙加絲機計劃，對多條制絲線進行批次任務分配、排序優化，給出絲線各工序段的排產工單。

流程需要考慮的方面如下：

（1）為了更好適應市場需求變化，企業需要制定靈敏度更高的生產計劃，在月度計劃的基礎上制定周滾動生產計劃，周滾動計劃可以根據當前周計劃的執行情況和銷售需求的變化來修正下周的計劃，并逐期向前移動。通過周滾動計劃動態編制方法，將銷售需求、生產執行反饋隨時間的變化納入到計劃的動態調整中，在保留計劃應有的嚴肅性的同時增加了計劃的靈活性[2]。

（2）在生產點詳細排產中，不同生產點存在不同的卷包機型，其性能工藝要求各不相同，需要保證設備任務負荷的均衡性、生產的連續性，盡快完成訂單生產任務，避免拖期損失等。

（3）多點任務分配與各點詳細排產銜接：由于成本考慮、工藝要求、質量追溯，卷煙生產采用了批量投產，每臺卷接設備必須連續生產一定批量卷煙，才能進行換牌號或結束，也就是按批次生產。因此需要把上層優化后的任務列表進行批次轉化，把各牌號的卷煙需求箱數除以投產批量轉化為批數，超出計劃的部分作為在制品。

（4）生產優化約束：生產計劃的約束是多方面的，對卷煙企業來說，制定生產計劃時要考慮的制約因素主要包括：周滾動需求計劃、生產能力、庫存水平、工藝限制。而生產原料、輔料供應，通常不成為制約因素。在進行卷煙生產計劃的優化時，必須對各種約束進行考慮，方案必滿足各種實際生產限制。

圖2 卷煙多點生產排產優化總體流程

3 卷煙生產優化建模

在考慮資源約束時，可以選擇各個環節的瓶頸資源作為約束條件，這樣就能使整個建模過程得到合理的簡化。在構建和求解模型中，對總體流程的多點任務分配和生產點詳細排產環節分別建立排產數學模型。

3.1 卷煙多點生產任務分配模型

多點任務分配模型主要是根據對周滾動計劃任務進行分解，生成各個生產點生產計劃，即已知n個品種香煙在一個周期內的需求計劃，現在有m個生產點分別能生產n種香煙中的某些品種，其生產、運輸成本各不相同，在滿足各生產點生產能力限制的前提下，將總的計劃合理分配到各個生產點。根據企業的實際需求，在構建模型時考慮了以下因素：（1）優化目標：使總的生產成本最低、庫存最小。（2）約束條件：①各生產點每天的總生產量不能超過該生產點當天的力限制；②任何品種在所有生產點的產量總和，要能滿足周期內該品種的需求。用數學語言描述如下：

xij生產點i生產品種j香煙的數量，單位：箱。 f(xij)生產點i生產品種j香煙的生產成本函數，若i生產點不能生產品種j，則為∞，單位：元。nli生產點i在周期內的生產能力上限，單位：箱。xqj品種j香煙在周期內的需求量，單位：箱。ci第i個生產點的運輸成本系數，單位：元。 yij生產點i品種j的在制品庫存，單位：箱。

圖3 卷煙生產短期成本函數曲線

四個生產點的產量成本函數 f(xij)，如圖3所示，橫軸為產量，縱軸為生產成本，即短期總成本隨產量變化的關系。曲線的形狀取決于生產要素的邊際報酬。

由于四個廠的生產設備、工藝、管理水平存在差異，因此成本函數各異；同時各卷煙牌號生產成本系數也各不相同。因此需要根據各個生產點生產不同品種香煙的生產成本函數、卷煙綜合運輸成本進行優化，同時要考慮牌號生產點的限制。

3.2 加絲機詳細排程模型

根據卷煙生產流程，生產點詳細排產模式可以描述為：有m臺加絲機，要加工n個批次的卷煙。每個批次可以在某些加絲機上生產，用一道工序加工完成；每個牌號卷煙在不同加絲機上的加工時間一定，且各不相同。詳細排產目標是把n個批次的卷煙安排到特定時間段、特定機組資源組合上，使最大完工時間最短。該問題在Makespan指標下已被證明是NP完全問題，所有分配方案為mn種[8]。令t(k,i,j)為第k個牌號第i批卷煙在機器 j上的加工時間，假設牌號k的批次i在機器 j上加工，則 x(k，i，j)=1，否則x(k，i，j)=0，則可定義廣義加工時間為 x(k，i，j)t(k，i，j)。同時考慮同一臺加絲機上加工不同牌號之間的換牌時間和首批準備時間，則機器 j的Makespan指標取決于該機器加工批次的數量、加工時間和換牌次數。為減少換牌次數，同牌號批次在加絲機上連續生產。機器 j上的完工時間為：

其中t(k-1，k，j)為牌號k在機器 j的換牌時間，p為卷煙的牌號數量，ts為機器 j首次生產準備時間，y(k，j)=1表示牌號k在 j上加工。進而整個加工過程的最大完工時間和相應的調度指標分別為：

4 解決方案（兩階段優化）

由于模型目標函數非線性，約束條件多，解空間巨大，經典常規算法不能獲得滿意的解，因此需要采用智能算法來求解。遺傳算法GA是一種模擬生物進化過程的隨機搜索算法，將問題的求解表示成一群“染色體”，并將它們置于問題的環境中，根據“適者生存”的原則，從中選擇適應環境的“染色體”進行復制，通過交叉、變異等操作產生新一代更適應環境的“染色體”群，通過不斷進化，最后收斂到一個最適應環境的個體上，即為問題的最優解。適合于大規模復雜的生產任務分配問題[8-9]。

4.1 多點任務分配遺傳混合算法設計

針對多點非線性成本優化問題的特點，業界普遍采用遺傳算法進行求解[5-9]，遺傳算法具有快速隨機的全局搜索能力，能夠在短時間內為優化問題提供近優解，且毋需太多的問題域知識，并自然地適合并行實現，其自適應性和自學習性特別適合于求解現實中具有大規模狀態空間的優化問題。但其存在迭代停滯的問題，當迭代到一定代次，即達到近優解時往往會做無用的冗余迭代，無法到達最優解。換句話說，遺傳算法容易陷入到次優解[10-11]。

因此，單獨使用遺傳算法難以滿足多點非線性成本最優的要求。而模式搜索具有很強的細搜索能力[10-11]，易于發現局部最優解，但是其全局搜索結果的最優性在很大程度上依賴于初始點的選擇。遺傳算法強于全局近優搜索而弱于局部細搜索，模式搜索強于局部細搜索而弱于選擇接近最優的初始點。本文采用遺傳算法“投放”模式搜索到近優點，而模式搜索從近優點開始細搜索最優點的想法。提出了一種混合遺傳算法-模式搜索的最優化方法：該方法是首先通過GA算法進行全局范圍的優化，在此基礎上使用局部尋優精度好的模式搜索法。GA進化后得到全局近優個體，模式搜索以此遺傳近優個體作為初始值，進行快速局部最優搜索，改善遺傳算法局部尋優精度較差的固有缺陷，兩種算法取長補短。該算法流程如圖4所示。

綜合算法的基本步驟是：

圖4 GA+PS混合算法流程

（1）設定算法各項控制參數，問題的解顯然取決于生產點i生產品種j香煙的數量xij的取值，只要確定了每個基因xij，即由公式（1）計算分配方案的成本性能指標，作為進化搜索的驅動力。直接采用n×m矩陣實數編碼表示分配方案，基于矩陣進行算子操作。這種編碼解直觀、易于操作。隨機生成初始分配種群。

（2）根據適應度評價種群。根據式（1）～式（3）計算種群中每種分配的目標函數值和適應度值。

（3）遺傳算子操作。通過選擇、交叉、變異和替換等操作生成新的種群。

（4）判斷條件：滿足遺傳進化停止條件，從最終的種群中挑出最優解，轉到（5），否則轉入（2）。

（5）把最優個體作為模式搜索的起始點，進行迭代運算，初始點R0=GA最優解。

（6）根據模式確定搜索方向，計算出網格Rn，計算目標函數 f(Rn)。

（7）對網格進行表決，f(Rn)＜f(R0)網格點的目標函數值小于當前點的函數值，表決成功，該點作為下次迭代的當前點R0=Rn，同時增大網格尺寸。否則當前點保持不變，收縮網格尺寸。

（8）然后繼續迭代，判斷網格尺寸δ＜ε截止誤差容限，如是，則停止搜索。

（9）判斷是否再繼續遺傳算法，如繼續，則把模式搜索最優解加入GA種群。

4.2 加絲機詳細排產遺傳算法策略

針對生產點詳細卷煙排產，進行如下轉換設置：（1）獲取優化后的生產點卷煙生產箱數計劃，按卷煙牌號進行批次拆分，得到不同牌號卷煙的對應批次任務；（2）根據卷包機組生產能力及配置關系，計算出加絲機的整體能力；（3）對卷煙牌號的生產機型限制、牌號優先級進行設定。

該并行機器調度問題的GA算法主要策略如下：

（1）編碼：問題的解顯然取決于 x(k，i，j)的取值，由于矩陣編碼涉及的基因太多，存在大量的冗余信息，不便于遺傳操作的設計，因此采用自然數編碼來解決這個問題。即由n個取值為[1，m]之間整數的基因kj構成染色體[k1k2…kn]，記為X，每個基因代表該批次加工的加絲機號。進而由公式（4）～（6）計算染色體調度方案的Makespan性能。

（2）遺傳算子操作：將最大流程時間的倒數作為適應度函數；采用輪盤賭進行選擇；采用次序交叉；變異采用翻轉變異。為了實現GA算法在保持種群多樣性的同時，保證算法的收斂性。在進化后期，采用自適應算法，使交叉與變異隨適應度自動改變。

（3）規則約束：由于卷煙生產存在著許多的規則要求和工藝限制，在排產時必須予以考慮：①加工的品牌盡量由高到低，即同一臺加絲機上品牌高的優先生產；②某規格必須嚴格限定在某些加絲機上。因此需要在遺傳算法設計中考慮各種規則和限制。首先在編碼時對受限的牌號的編碼取值范圍進行限定，排除不能生產該牌號的加絲機編碼；然后在個體解碼過程中，對加絲機分配任務進行優先級排序。保證進化操作過程中不出現非法染色體。

5 卷煙排產實例分析

5.1 問題實例

現有8個牌號卷煙牌號在一個周期內的需求量，如表1所示，要將生產任務合理分配到4個生產點進行生產。

表1 卷煙生產需求表 箱

表2給出了各生產點不同牌號卷煙的生產成本系數，考慮了人工成本、機器損耗、物料供應成本等在內的綜合生產成本系數（注：“--”表示該生產點工藝上不具備生產某品種香煙的能力）；最后一行是生產點的物流運輸成本系數/箱。

表2 各生產點不同牌號卷煙成本系數

表3給出各個生產點每周期的最大生產能力；表4是各生產點各牌號卷煙的在制品庫存。

表3 各個生產點每天的最大生產能力（箱·周－1）

表4 各個生產點在制品數量 箱

目標是在滿足周需求計劃，各點生產能力限制的前提下使總成本最低，在制品庫存最少。

生產點詳細排產以6個加絲機單元為例，每個加絲機連接不同數量、型號的卷包機，共30臺卷包機。目標是確定批次任務在加絲機單元的分配，考慮工藝路徑約束，使最大生產流程時間最短。

各牌號卷煙批次不同設備加工時間如表5所示。為方便起見，規定設備不同牌號中途切換時間都相同，為30 min。首個牌號開始生產的準備時間為15 min。

表5 煙絲工序加工時間表（h：mm)

5.2 程序運行結果分析

針對多點任務分配，設置算法參數：模式搜索表決方法采用GPSPositiveBasisNp1模式由N+1個向量組成，最大迭代次數400；遺傳算法種群數量30，變異方法為自適應可行變異，交叉為啟發式交叉，進化30代無改進則停止。

優化結果見表6，各牌號卷煙生產量加上庫存滿足了周需求；各點生產總量小于生產能力限制；各點生產的牌號滿足了工藝限制。該方案的總生產成本482 986.18，實數編碼小數點向上取整。

表6 各生產點一周內的任務計劃 箱

圖5 混合算法進化過程

混合算法進化過程如圖5所示，上圖為遺傳算法最佳適應度進化圖；下圖為模式搜索最佳目標函數迭代圖。當GA進化到150代時收斂、停滯，而模式搜索在此基礎上進一步搜索，迭代200代后，得到了更好的成本優化指標，該混合算法改善了在單獨使用遺傳算法會出現的迭代停滯問題，或在單獨使用模式搜索法難以選擇搜索初始點的問題。

以生產點2分配的卷煙任務為例，轉換成生產批數，共75批各牌號卷煙。可用的加絲機限制如表7所示。

表7 卷煙生產訂單表

加絲機上的牌號優先級為（P8、P7、P6、P5、P4、P3、P2、P1）。種群規模m=20；遺傳運算的終止進化代數T=20；保留最佳個體。

優化結果如圖6所示，圖中不同顏色代表不同批次卷煙，該圖直觀地給出了不同牌號批次卷煙任務在b1～b6加絲機上的分配方案。通過窗口，可以精確地查看每一牌號批次生產任務詳細排產信息；同時從圖上可以反映出工廠日歷對生產的影響，工作日歷每天6：00—20：00，下方藍色塊表示生產周期內排班休息時間。這為生產提供了有價值的精確參考。可以看出好的排產方案，使所有設備的工作效率提高，設備負荷均勻，因此如何對各牌號卷煙排產是提高設備總體效率的關鍵。

圖6 卷煙批次排產甘特圖

該算法以較小的時間代價，通過1 380次計算，得到了任務分配方案，獲得了近優的滿意結果，總完成時間在20代第10個體獲得最優值：2 d19 h57 min；優化耗時：1 min15 s，換牌次數：32次，證明了算法的有效性。從圖7的進化適應度圖譜，可以看出算法收斂性。

6 結束語

針對卷煙多點生產任務分配與單生產點詳細排產優化實際問題，提出了一種混合遺傳算法和模式搜索的優化模型進行求解。綜合遺傳算法強于全局求近優的能力，和模式搜索強于局部求最優的能力，有效解決了卷煙排產優化的復雜性，獲得優化、可行的排產方案，降低卷煙多點生產成本、縮短生產完工時間。通過改進遺傳算法為現有ERP卷煙排產功能的完善提供有益的參考。同時還需要對排產優化算法與ERP系統訂單管理模式的集成進行相應的研究，更好地發揮各自相應的作用，為生產資源的優化配置奠定基礎。

圖7 遺傳算法收斂曲線

[1]郝雨.煙草企業生產排程模型的建立與優化[D].武漢：華中科技大學，2008.

[2]周文軍.三維一體生產調度方法及其在卷煙制絲過程中的應用[D].長沙：湖南大學，2009.

[3]孫潔香.基于仿真的面向煙草行業制絲排產方法研究與實現[D].北京：北京機械工業自動化研究所，2009.

[4]鄧燦勇.常德卷煙廠MES系統設計及高級排產方法研究[D].長沙：中南大學，2010.

[5]王愛民.煙草卷包作業動態調度技術[J].計算機集成制造系統，2010（3）：603-606.

[6]陳志剛.卷煙廠制絲線自動排產系統設計[J].制造業信息化，2009（11）：105-107.

[7]謝五峰.基于西門子平臺的卷包排產子系統的研究[J].企業管理與信息化，2006（1）：5-11.

[8]王萬良.生產調度智能算法及其應用[M].北京：科學出版社，2007.

[9]姚麗麗.煙草排產中嵌入規則的遺傳算法應用研究[J].制造業信息化，2011（4）：89-91.

[10]Mitchell T M.Machine learning[M].New York：McGraw-Hill，1997：179-193.

[11]Russell S J，Norvig P.Artificial intelligence：a modern approach[M].2nd ed.[S.l.]：Pearson Education，Inc.，2003：712-793.