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

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

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

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

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

0 引言

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

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

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

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

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

1.1 正排

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

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

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

1.2 倒排

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

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

1.3 機(jī)臺(tái)齊停算法

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

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

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

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

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

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

2.1 煙草加工過程分析

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

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

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

圖1 煙草加工過程

2.2 參量描述

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

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

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

3）b：每組柜對(duì)應(yīng)的卷煙機(jī)臺(tái)數(shù)；

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

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

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

7）M：卷煙機(jī)臺(tái)時(shí)耗絲量；

8）Z：柜組單位時(shí)間耗絲量

9）Q：柜組儲(chǔ)絲量

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

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

2.3 規(guī)則介紹

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

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

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

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

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

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

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

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

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

3.2 排產(chǎn)思路

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

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

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

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

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

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

3.3.1 編碼

編碼采用基于流水線的編碼。例如：共7個(gè)品牌的物料，有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ù)計(jì)算

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

3.3.3 選擇

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

3.3.4 交叉

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

交叉位置為3和6，則交叉后的個(gè)體為

3.3.5 變異

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

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

4 仿真與分析

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

4.1 實(shí)例驗(yàn)證

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

4.1.2 算法輸入量

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

表1 各個(gè)牌號(hào)的煙絲需求量

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

表2 各個(gè)牌號(hào)的煙在各個(gè)生產(chǎn)線上的生產(chǎn)時(shí)間

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

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

4.1.3 結(jié)果展示

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

圖3 甘特圖顯示

4.2 結(jié)果分析

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

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

5 結(jié)論

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

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

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

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

[4]呂希勝, 史海波, 潘福成. 制絲線計(jì)劃與調(diào)度系統(tǒng)研究與實(shí)現(xiàn)[J]. 制造業(yè)自動(dòng)化, 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)用背景，對(duì)煙草排產(chǎn)中的工藝路徑和規(guī)則進(jìn)行分析，構(gòu)建基于遺傳算法（Genetic Algorithm）的車間排產(chǎn)系統(tǒng)模型。同時(shí)將排產(chǎn)中的約束條件嵌入到算法設(shè)計(jì)過程中，給出算法設(shè)計(jì)方案。最后進(jìn)行實(shí)例驗(yàn)證，結(jié)果表明，所提出的排產(chǎn)算法在煙草的排產(chǎn)中具有很好的可行性。

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

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

TP315

A

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

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

2010-11-17

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