煙草排產中嵌入規則的遺傳算法應用研究

姚麗麗，史海波，劉 昶，潘福成

（1. 中國科學院 研究生院，北京 100049；2.中國科學院 沈陽自動化研究所 工業信息學 重點實驗室，沈陽 110016）

煙草排產中嵌入規則的遺傳算法應用研究

姚麗麗1,2，史海波2，劉 昶2，潘福成2

（1. 中國科學院 研究生院，北京 100049；2.中國科學院 沈陽自動化研究所 工業信息學 重點實驗室，沈陽 110016）

0 引言

中國煙草行業是國家稅收的主要貢獻者之一，年稅收為國家總稅收的10%左右。在我國煙草行業是一個政策性影響很大的行業，國家對其實施統一領導、垂直管理的運行體制。但是由于市場經濟的發展所趨以及國內市場國際化的迫切需要，行業之間的競爭也日益激烈。同時隨著制造業自動化信息程度的提高，煙草制造設備的信息提取與控制決策等已經達到了一個很高的水平，從而為企業的組織與管理提供了必要的信息基礎。所以實施信息化的生產組織管理和優化決策，提高煙草企業的生產效益成為煙草行業的迫切需要。

生產調度作為生產組織與管理的關鍵，對提高企業的生產效率、設備利用率等有著重要的意義。但是由于煙草生產中的約束條件的限制，各個企業的生產調度方案多依靠計劃員憑借經驗手工完成，即使是已有的排產軟件，也多是利用一些簡單的排產算法，如正序排產、倒序排產、齊停規則算法等，這些算法都是基于規則的算法，算法運行完后僅產生一種調度方案，很難實現企業最小化或最大化目標性排產的需求。

遺傳算法作為一種智能進化算法，以其靈活性并行處理能力和快速收斂性等特點在各種優化工程領域得到了廣泛的應用，尤其是在處理大規模調度問題中。文獻[2]中作者利用運籌學的方法進行建模，利用遺傳算法進行求解，本質上來說，并沒有將遺傳算法直接應用于煙草行業的排產中。本文利用遺傳算法對煙草行業的生產調度進行研究，將煙草排產中的約束規則隱含于算法設計中，構建煙草生產過程中的關鍵工序的調度方案，為以后的煙草行業實際目標性的排產奠定了堅實的基礎。

1 煙草排產中采用的算法及應用

由于煙草行業的生產過程中，存在著許多的潛在性規則要求，目前為止，煙草行業實際企業中的自動排產軟件也僅僅是利用一些簡單的排產算法實現。以下對煙草行業中的已經存在的常用的排產算法以及本文提出的遺傳算法做一簡單總結性描述。

1.1 正排

正排，即正序排產的簡稱，是將當前排產時間或者某一特定時間作為起點，按照時間的先后順序對工件的各道進行安排，也就是按照工件的工藝路徑來安排各個工件的加工順序。

正序排產是一種基于規則的排產策略。常見的排產規則主要包括：1）訂單排產規則，主要影響待加工產品上線順序。如“物料 —> 訂單要求交貨期 —> 客戶的重要度 —> 接單的先后順序”（其中“—>”表示優先級由高到低的順序安排）。2）工序選擇規則，針對加工時機器選擇加工的工件順序而言，如根據工件的最早完成日期、最少剩余工序、排程文件優先順序、前道工序最早完成等，對滿足其中之一的工件優先進行加工。3）資源選擇規則，針對同道工序存在多臺機器，工件選擇哪臺機器進行加工來說，如最早結束時間、最早開始時間、 最遲結束時間、與前工序一樣、非瓶頸最早開始時間等。

正序排產算法簡單，易于實現，很適合在多規則的煙草排產中使用，現有的多數煙草行業自動排產軟件也是應用這種算法進行排產的。但是正序排產算法本質上來說就是一種基于規則的策略，很難解決排產中各種目標的最小化或最大化問題。

1.2 倒排

倒排，即倒序排產的簡稱，是指將確定的訂單完成時間或者某條工藝路徑的加工完成時間作為起始點，然后從后向前安排各道工序，也就是按照工藝路徑的倒序進行安排，依次推出各個工件的各道工序的開工時間，最后得到各訂單的最晚開工時間。

同正序排產一樣，倒序排產也是一種基于規則的排產方法，其規則包括工序選擇規則和資源選擇規則。該排產在煙草行業中解決MTO型（訂貨生產）的排產時尤為適合，且算法簡單，容易實現。同樣該算法很難解決煙草行業的目標性排產問題。

1.3 機臺齊停算法

機臺齊停算法是文獻[3]中新提出的一種算法。基本宗旨就是保證卷煙機的同時停止，即每臺卷包機具有相同的結束時間。根據預計開始時間、排產過程中的加工時間、維護訂單時間、以及總生產產量等，計算出統一的預計結束時間，然后根據預計結束時間對每個機臺進行產量的分配。這種算法簡單，容易實現，人工都可以完成簡單的計算排產。但是保證機臺的同時停止沒有太大的實際工程意義。

1.4 遺傳算法排產

遺傳算法，是模擬達爾文生物進化論的自然選擇及遺傳學機理的生物進化過程的計算模型，是基于“適者生存”的一種高度并行、隨機和自適應優化算法。其具有很高的靈活性、并行處理能力等特點。

遺傳算法在生產調度領域的研究，無論在理論界還是實際工程界，都已經達到了一個很高的程度。眾多實際例證也表明遺傳算法能夠很好的解決生產調度的目標性問題。然而，至今在多規則的煙草排產中，利用遺傳算法也僅僅是做一些建模后的優化工作，并沒有將遺傳算法直接應用于排產中。本文將煙草排產過程中的約束規則隱含于算法設計中，首次利用遺傳算法直接進行煙草排產研究。

2 煙草生產過程描述

煙草的生產加工過程與一般的機械產品的加工過程不一樣，在煙草的生產過程中，由于其特殊工藝的需求，生產過程存在著許多約束規則，這些約束規則有的為必須遵循的規則，有的則為盡量滿足的規則，在進行生產調度時，必須予以考慮。

2.1 煙草加工過程分析

本文的算法研究以某煙草生產企業為背景，在該煙草企業中，其生產過程主要涉及兩個車間：制絲車間和卷接包車間。其中制絲車間主要由3條制絲線組成，其中一條梗絲線，一條6000kg/h的葉絲線，一條3000kg/h的試驗線。卷包車間主要由卷接機、包裝機、裝箱機等設備組成，卷接機的機速和臺數決定了生產線的產量大小。制絲車間和卷接機車間通過布料機、喂絲機相連。

實際煙草企業中的加工過程相當復雜，為了方便研究，本文對煙草的生產過程做簡化型建模描述。具體加工過程圖1所示。

通過對煙草的加工過程分析，不難發現，煙草的制造過程屬于混合流水線式加工模式。每批品牌的煙草生產時，工藝路徑確定不變，即加工過程中的工序加工順序不能互換，同時在同道工序進行加工時，又存在多臺設備的選擇利用，這就構成了混合流水線調度模型。但是在煙草的加工過程中，并不像普通的混合流水線車間調度那樣，設備在加工過程中可以任意選擇，在煙草生產過程中，部分不同工序的設備之間有著固定的鏈接，即前臺設備的出料只能到固定的下臺設備上加工。為了簡化模型，我們可以直接將有著固定鏈接的設備或工序進行整合規劃，將其定為一道工序或者一臺設備而論。

圖1 煙草加工過程

2.2 參量描述

利用遺傳算法進行目標性調度時，同其他算法一樣，需要許多量化性的參數計算作為排產基礎數據。無論是什么樣的目標性排產，時間參數是必不可少的。下面對遺傳算法在煙草排產中所需要的參數進行簡單介紹。

1）a：卷煙機機速(單位：支/分鐘)；

2）m：煙支的單支重量(單位：g)；

3）b：每組柜對應的卷煙機臺數；

4）N：每組柜包含的柜數

5）Pi：每柜組中i號柜里的儲絲量(單位：kg，其中i不大于N)；

6）Gi：每種煙牌的煙絲需求量；

7）M：卷煙機臺時耗絲量；

8）Z：柜組單位時間耗絲量

9）Q：柜組儲絲量

10）T：不同煙牌在不同生產線上的加工時間

其中i代表煙牌號，j代表生產線號。

2.3 規則介紹

在煙草的排產過程中，由于煙草生產的特殊工藝需求以及煙草設備之間的固定鏈接等因素，煙草排產中存在許多潛在的規則需要遵循。在這里，我們僅對一些基本的規則進行介紹。

1）儲絲柜中，同一時間只能存儲同一品牌煙的物料，且滿足一定的儲絲時間要求，以完成醇化過程。

2）在單點時間內，儲絲柜與喂絲機之間是一對一得關系，喂絲機與卷煙機之間是一對多的關系。也就是同一時間內，喂絲機只能從一個儲絲柜那里獲取原料，而同時可以給該流水線上的多臺卷接機供料。

3）同道生產線上，加工的品牌盡量由高到低。品牌由高到低時，可連續生產，相反生產時則必須停止20min左右后才能生產。這是由于品牌由低到高生產時，為了保證質量問題，低品牌的煙生產完工后，必須對設備進行清理，保證高品牌煙絲的純度要求。

4）保證卷接機組連續不斷料。這是煙草生產過程中必須遵循的原則。

3 遺傳算法在煙草排產中的應用研究

3.1 排產模型構建

在煙草的整個加工過程中，成品儲絲柜、喂絲機、卷接機之間存在固定鏈接關系。將有著固定鏈接關系的這些設備看作一個整體，此時與這些設備前后鏈接的所有設備由于都為單條流水線式加工，工序加工時的設備不存在選擇性問題。所以在這里，我們將有著相同喂絲機的整個流水線加工設備也看作一個整體，即以生產線為單位進行遺傳算法排產。

對于物料的處理，為了便于研究問題說明，在這里實行品牌不可拆分原則，整個排產問題也可以看作0-1背包問題來處理。最終所得到的排產模型如圖2所示。

3.2 排產思路

圖2 煙草排產模型

1）實行批量不可分原則，即同一品牌的煙只能在同一道流水線上連續加工。要求遺傳算法編碼以批量為單位，進行十進制編碼。

2）假設各個流水線的設備配置合理，以生產線為單位進行調度，加工時間與流水線的生產能力以及該批量的產量有關。各個批量在每條流水線上的加工時間通過所給的各個煙草參量計算獲得。即算法輸入參數中的加工時間依靠計算得出。

3）同條流水線上采用品牌由高到低的優先規則。即當一條流水線上安排2批或者2批以上時，則此流水線上的生產先后順序根據品牌的優先級而定，品牌高的優先生產。對于遺傳算法來說，即要求算法解碼時嵌入優先規則。

3.3 煙草排產中的遺傳算法操作

遺傳算法的操作在求解各個問題時，是具體情況而定。根據已經建立的煙草排產模型，遺傳算法的各個操作也就基本確定。

3.3.1 編碼

編碼采用基于流水線的編碼。例如：共7個品牌的物料，有3條流水線，如編碼為：

[1，3，1，2，2，1，3]

此表示批量1在流水線1上生產，批量2在流水線3上生產，批量3在流水線1上生產，批量4在流水線2上生產，批量5在流水線2上生產，批量6在流水線1上生產，批量7在流水線3上生產。

3.3.2 適應度函數計算

一般來說，適應度函數越高的個體適應性越強，如果采用極小化目標函數，則應將目標函數轉換為適應度函數時取相反數，或者用最大值減去目標函數。極大化問題則無需變換。適應度函數的計算也就是編碼的反操作過程。

3.3.3 選擇

采用輪盤賭的選擇方法，對于當前種群，首先計算出每個個體的適應度函數值，然后根據所得的適應度函數值，計算相應的累積概率、選擇概率。由于適應度函數高的個體選擇概率較大，則滿足“優勝劣汰”的規律。

3.3.4 交叉

由于編碼是基于流水線的特殊性，則交叉時最好的方法是采用簡單的基因互換的方法。即隨機確定兩個位置，對兩父代的這兩個位置之間的基因進行交叉互換即可。如父代個體為：

交叉位置為3和6，則交叉后的個體為

3.3.5 變異

變異采用逆序操作的方法，即將個體中，兩個不同基因位置間的基因串逆序。如父代個體為：

產生的隨機位置為2和4，則變異后的個體為：

4 仿真與分析

本文以最小化生產成本為目標進行實例驗證。

4.1 實例驗證

4.1.1 最小化生產成本量化描述

4.1.2 算法輸入量

本實例中共有8種品牌的煙，3道加工流水線，各個品牌的煙絲需求量如表1所示（牌號由高到低）：

表1 各個牌號的煙絲需求量

利用公式（1）計算后，每批煙牌在各個生產線上的加工時間如表2所示。

表2 各個牌號的煙在各個生產線上的生產時間

不同的生產線，加工費率不同，本實例中的生產線加工費率表如表3所示。

表3 生產線加工費率

4.1.3 結果展示

本文采用visual studio 2008 進行軟件編程實現上述算法。遺傳算法的參數設置：種群規模：30，迭代次數：1000，交叉率：0.7，變異率0.5。排產完成后，所生成的甘特圖如圖3所示，優化過程中迭代曲線圖如圖4所示。

圖3 甘特圖顯示

4.2 結果分析

上述實例證明，遺傳算法在煙草的排產中應用良好，具有很好的可行性。但是這只是簡單的排產模型，在排產過程中，同種煙牌實行批量不可分原則，就好比0—1背包問題一樣，對于資源的利用率不是很合理，該算法還有待進一步研究。無論如何該算法都為煙草行業的目標性排產奠定了一定的理論基礎。

圖4 生產成本迭代曲線圖

5 結論

由于煙草生產的過程中存在著眾多的規則，所以現有的煙草行業的排產大多憑借計劃員手工完成，自動排產也是采用一些簡單的算法，正排、倒排等。本文采用遺傳算法進行煙草調度排產研究，將排產的各種規則進行自動隱含，由于遺傳算法有著并行搜索的能力，可以很好的解決煙草行業中的目標性排產問題，為煙草行業的目標性排產奠定了堅實的基礎。

[1]王凌. 車間調度及其遺傳算法[M]. 北京: 清華大學出版社, 2003: 138-144.

[2]郝雨, 奕恩杰, 余明暉. 煙草企業生產排成模型的建立與優化[M]. 武漢: 華中科技大學出版社, 2008: 1-56.

[3]謝五峰, 鄂明成. 基于西門子平臺的卷包排產子系統的研究[J]. 企業管理與信息化, 2006, 36(1): 5-11.

[4]呂希勝, 史海波, 潘福成. 制絲線計劃與調度系統研究與實現[J]. 制造業自動化, 2009, 31(1): 83-86.

[5]Erwin Pesch, Malgorzata Sterna. Late work minimization in flow shops by a genetic algorithm[J]. Computers &Industrial Engineering 2009, 57: 1202–1209.

[6]Jose M. Framinana, Rainer Leisten. A heuristic for scheduling a permutation flowshop with makespan objective subject to maximum tardiness[J]. Int. J.Production Economics, 2006, 99:28-40.

[7]Ruiz,Ruben. The hybrid flowshop scheduling problem[J].European Journal of Operational Research, 2010, 205(1):1-18.

Research on genetic algorithm application with embedded rules in tobacco production

YAO Li-li1,2, SHI Hai-bo2, LIU Chang2, PAN Fu-cheng2

提出利用遺傳算法解決煙草行業的作業調度問題。以某卷煙制造企業作為研究和應用背景，對煙草排產中的工藝路徑和規則進行分析，構建基于遺傳算法（Genetic Algorithm）的車間排產系統模型。同時將排產中的約束條件嵌入到算法設計過程中，給出算法設計方案。最后進行實例驗證，結果表明，所提出的排產算法在煙草的排產中具有很好的可行性。

煙草制造；遺傳算法；車間調度

姚麗麗（1986－），女，甘肅慶陽人，碩士研究生，主要從事生產調度與計劃、企業自動化集成等研究。

TP315

A

1009-0134(2011)4(下)-0089-05

10.3969/j.issn.1009-0134.2011.4(下).26

2010-11-17

國家863高技術計劃項目 (2007AA040702)；國家自然科學基金 (60904047)