煙草排產(chǎn)中嵌入規(guī)則的遺傳算法應(yīng)用研究

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

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

煙草排產(chǎn)中嵌入規(guī)則的遺傳算法應(yīng)用研究

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

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

0 引言

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

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

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

1 煙草排產(chǎn)中采用的算法及應(yīng)用

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

1.1 正排

正排，即正序排產(chǎn)的簡稱，是將當(dāng)前排產(chǎn)時間或者某一特定時間作為起點，按照時間的先后順序?qū)ぜ母鞯肋M行安排，也就是按照工件的工藝路徑來安排各個工件的加工順序。

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

正序排產(chǎn)算法簡單，易于實現(xiàn)，很適合在多規(guī)則的煙草排產(chǎn)中使用，現(xiàn)有的多數(shù)煙草行業(yè)自動排產(chǎn)軟件也是應(yīng)用這種算法進行排產(chǎn)的。但是正序排產(chǎn)算法本質(zhì)上來說就是一種基于規(guī)則的策略，很難解決排產(chǎn)中各種目標(biāo)的最小化或最大化問題。

1.2 倒排

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

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

1.3 機臺齊停算法

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

1.4 遺傳算法排產(chǎn)

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

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

2 煙草生產(chǎn)過程描述

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

2.1 煙草加工過程分析

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

實際煙草企業(yè)中的加工過程相當(dāng)復(fù)雜，為了方便研究，本文對煙草的生產(chǎn)過程做簡化型建模描述。具體加工過程圖1所示。

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

圖1 煙草加工過程

2.2 參量描述

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

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

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

3）b：每組柜對應(yīng)的卷煙機臺數(shù)；

4）N：每組柜包含的柜數(shù)

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

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

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

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

9）Q：柜組儲絲量

10）T：不同煙牌在不同生產(chǎn)線上的加工時間

其中i代表煙牌號，j代表生產(chǎn)線號。

2.3 規(guī)則介紹

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

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

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

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

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

3 遺傳算法在煙草排產(chǎn)中的應(yīng)用研究

3.1 排產(chǎn)模型構(gòu)建

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

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

3.2 排產(chǎn)思路

圖2 煙草排產(chǎn)模型

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

2）假設(shè)各個流水線的設(shè)備配置合理，以生產(chǎn)線為單位進行調(diào)度，加工時間與流水線的生產(chǎn)能力以及該批量的產(chǎn)量有關(guān)。各個批量在每條流水線上的加工時間通過所給的各個煙草參量計算獲得。即算法輸入?yún)?shù)中的加工時間依靠計算得出。

3）同條流水線上采用品牌由高到低的優(yōu)先規(guī)則。即當(dāng)一條流水線上安排2批或者2批以上時，則此流水線上的生產(chǎn)先后順序根據(jù)品牌的優(yōu)先級而定，品牌高的優(yōu)先生產(chǎn)。對于遺傳算法來說，即要求算法解碼時嵌入優(yōu)先規(guī)則。

3.3 煙草排產(chǎn)中的遺傳算法操作

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

3.3.1 編碼

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

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

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

3.3.2 適應(yīng)度函數(shù)計算

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

3.3.3 選擇

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

3.3.4 交叉

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

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

3.3.5 變異

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

產(chǎn)生的隨機位置為2和4，則變異后的個體為：

4 仿真與分析

本文以最小化生產(chǎn)成本為目標(biāo)進行實例驗證。

4.1 實例驗證

4.1.1 最小化生產(chǎn)成本量化描述

4.1.2 算法輸入量

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

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

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

表2 各個牌號的煙在各個生產(chǎn)線上的生產(chǎn)時間

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

表3 生產(chǎn)線加工費率

4.1.3 結(jié)果展示

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

圖3 甘特圖顯示

4.2 結(jié)果分析

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

圖4 生產(chǎn)成本迭代曲線圖

5 結(jié)論

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

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

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

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

[4]呂希勝, 史海波, 潘福成. 制絲線計劃與調(diào)度系統(tǒng)研究與實現(xiàn)[J]. 制造業(yè)自動化, 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

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

煙草制造；遺傳算法；車間調(diào)度

姚麗麗（1986－），女，甘肅慶陽人，碩士研究生，主要從事生產(chǎn)調(diào)度與計劃、企業(yè)自動化集成等研究。

TP315

A

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

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

2010-11-17

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