李 凡，李 斌，衛(wèi)建斌

（紅云紅河集團(tuán)紅河卷煙廠(chǎng)，云南 紅河州 652399）

0 引言

隨著工業(yè) 4.0的變革，信息化技術(shù)對(duì)現(xiàn)代工廠(chǎng)的發(fā)展產(chǎn)生了巨大的影響，智能工廠(chǎng)概念的提出，使得物聯(lián)網(wǎng)、大數(shù)據(jù)、邊緣計(jì)算、人工智能等先進(jìn)技術(shù)逐步引入到工廠(chǎng)的管理、辦公、甚至生產(chǎn)自動(dòng)化之中，從而以技術(shù)手段實(shí)現(xiàn)規(guī)范企業(yè)管理、提升工作效率的目標(biāo)[1]。

以卷煙行業(yè)為例，目前卷煙制造行業(yè)根據(jù)“按照訂單組織生產(chǎn)”的特點(diǎn)，對(duì)卷煙生產(chǎn)的柔性制造[2]以及智能生產(chǎn)調(diào)度提出了更高的要求。卷煙制造過(guò)程分為制絲生產(chǎn)及卷包生產(chǎn)，制絲生產(chǎn)為典型的流程型制造，與離散工業(yè)相比，不如離散工業(yè)那樣產(chǎn)品可以單件計(jì)數(shù)，制造過(guò)程易于數(shù)字化；制絲的生產(chǎn)過(guò)程涉及物理、化學(xué)反應(yīng)，部分原料成分、設(shè)備狀態(tài)及工藝參數(shù)難以實(shí)時(shí)獲取，且生產(chǎn)過(guò)程是連續(xù)的，中間任一環(huán)工序出現(xiàn)問(wèn)題，則會(huì)影響整條生產(chǎn)線(xiàn)的生產(chǎn)效率，從而形成了測(cè)量難、建模難、優(yōu)化決策困難等問(wèn)題。

因此，針對(duì)生產(chǎn)訂單多規(guī)格、小批量的特點(diǎn)，結(jié)合制絲線(xiàn)生產(chǎn)能力，合理組織生產(chǎn)，調(diào)度訂單生產(chǎn)順序，從而節(jié)約生產(chǎn)過(guò)程成本，節(jié)約生產(chǎn)時(shí)間，是提高生產(chǎn)效率的目標(biāo)。然而，目前的生產(chǎn)計(jì)劃制定大多依靠專(zhuān)家進(jìn)行人工調(diào)度，采用經(jīng)驗(yàn)方法，可經(jīng)驗(yàn)的積累需要時(shí)間，而在市場(chǎng)化經(jīng)濟(jì)的今天，時(shí)間就是金錢(qián)，制絲調(diào)度問(wèn)題實(shí)際上是一個(gè)較為復(fù)雜的實(shí)際問(wèn)題，需要考慮產(chǎn)線(xiàn)的生產(chǎn)能力、緩沖、設(shè)備情況等各種狀態(tài)，對(duì)此問(wèn)題，[3]提出，將生產(chǎn)調(diào)度問(wèn)題以層次劃分，細(xì)化問(wèn)題規(guī)模，逐步求解，目前針對(duì)卷煙生產(chǎn)調(diào)度，研究人員通過(guò)提取問(wèn)題特點(diǎn)，將其與流水線(xiàn)調(diào)度經(jīng)典問(wèn)題結(jié)合起來(lái)，徐永虎等人[4]提出了一種柔性制絲線(xiàn)排產(chǎn)算法，分析煙草排產(chǎn)工藝流程和約束規(guī)則設(shè)計(jì)架構(gòu)模型；[5]提出了一種面向分組加工的煙草生產(chǎn)調(diào)度模型，以仿真模型優(yōu)化排產(chǎn)調(diào)度設(shè)計(jì)；[6]設(shè)計(jì)出一種基于生產(chǎn)時(shí)間的二重有線(xiàn)分配啟發(fā)式算法，這些算法大部分從整個(gè)生產(chǎn)過(guò)程入手，統(tǒng)一看待整條制絲線(xiàn)、卷包線(xiàn)的生產(chǎn)計(jì)劃問(wèn)題，分析粒度大部分只到大的生產(chǎn)單元，在實(shí)際生產(chǎn)過(guò)程中，關(guān)鍵生產(chǎn)單元的優(yōu)化對(duì)于整條生產(chǎn)線(xiàn)的生產(chǎn)影響是明顯的，因此基于生產(chǎn)單元內(nèi)部的調(diào)度問(wèn)題也需要進(jìn)行考慮。

因此本文針對(duì)制絲煙片預(yù)處理生產(chǎn)單元的訂單調(diào)度問(wèn)題，結(jié)合實(shí)際特點(diǎn)構(gòu)建調(diào)度模型，將現(xiàn)實(shí)生產(chǎn)狀況映射到流程型流水線(xiàn)調(diào)度模型之中，利用模擬退火算法優(yōu)化的遺傳算法求解訂單執(zhí)行及調(diào)度順序，再利用實(shí)際算例進(jìn)行驗(yàn)證，為制絲預(yù)處理段的調(diào)度優(yōu)化提供解決思路。

1 問(wèn)題分析

近年以來(lái)，隨著客戶(hù)的需求逐步向中小批量、個(gè)性化改變，產(chǎn)品生產(chǎn)周期縮短，交貨時(shí)間提前等問(wèn)題使得傳統(tǒng)的大批量生產(chǎn)模式受到了新的挑戰(zhàn)。單元生產(chǎn)模式[7]作為精益生產(chǎn)的一種方式，目前正廣泛應(yīng)用于制絲生產(chǎn)過(guò)程中。其主要特點(diǎn)是產(chǎn)品族概念的提出，將不同品種的產(chǎn)品按照特點(diǎn)劃分為產(chǎn)品族，針對(duì)產(chǎn)品族的工藝特點(diǎn)從而進(jìn)行高效的設(shè)備布局，再按照柔性設(shè)備與單元自治的組織分工模式，從而實(shí)現(xiàn)生產(chǎn)運(yùn)作的高效、快速和靈活等目標(biāo)。

卷煙生產(chǎn)的要點(diǎn)在于深化分組處理，充分發(fā)揮原料使用價(jià)值，從而改善產(chǎn)品質(zhì)量[8]，以生產(chǎn)單元為單位的生產(chǎn)能夠有效地提高卷煙生產(chǎn)的效率。在制絲過(guò)程中，煙片預(yù)處理階段不僅涉及到原煙的入庫(kù)、流程化處理，還涉及到配葉貯葉過(guò)程，有原料的輸入，也有煙片半成品的輸出。根據(jù)目前卷煙生產(chǎn)工藝規(guī)范，主要分為備料、開(kāi)箱和計(jì)量、切片、松散回潮、煙片預(yù)配、篩分和加料以及配葉貯葉共7個(gè)階段，如圖 1所示。在實(shí)際的制絲車(chē)間中，它是制絲流程的一個(gè)起點(diǎn)，屬于關(guān)鍵生產(chǎn)單元，因此針對(duì)煙片預(yù)處理階段的調(diào)度優(yōu)化，對(duì)于整個(gè)制絲生產(chǎn)的效率都有一定提升。

圖1 煙片預(yù)處理段工藝流程Fig.1 Process flow of pre-treatment section of cigarette

在實(shí)際生產(chǎn)中，由于特殊工藝需求，在生產(chǎn)過(guò)程中存在許多規(guī)則與約束，煙片預(yù)處理階段的調(diào)度目標(biāo)是獲得成本最低的批次生產(chǎn)安排，在生產(chǎn)過(guò)程中，生產(chǎn)成本與生產(chǎn)時(shí)間密切相關(guān)，在保證產(chǎn)品質(zhì)量的前提下，應(yīng)盡量提高設(shè)備利用率，減少設(shè)備等待，從而使得總生產(chǎn)時(shí)間最短，受到如下幾方面的約束：

（1）牌號(hào)加工優(yōu)先級(jí)約束

針對(duì)生產(chǎn)訂單的差異，不同牌號(hào)的卷煙都具有對(duì)應(yīng)的葉組配方，并依照訂單批次進(jìn)行生產(chǎn)，不同牌號(hào)進(jìn)行批次切換時(shí)成本不同，由高端批次向低端批次切換時(shí)，由于不需要生產(chǎn)線(xiàn)的清潔，因此成本較低；反之成本較高。

（2）設(shè)備加工能力約束

在按照工序生產(chǎn)時(shí)，針對(duì)一批物料，不同設(shè)備具有固定加工能力，加工時(shí)間固定。

（3）緩存約束

在工序生產(chǎn)過(guò)程中，一部分工序之間存在固定容量的儲(chǔ)柜可以進(jìn)行緩存，且保持FIFO（先進(jìn)先出）原則。

（4）加工路徑約束

對(duì)于制絲生產(chǎn)，不同批次具有固定的加工路徑和加工設(shè)備，保持先進(jìn)先出原則。

煙片預(yù)處理段具有以下特點(diǎn)：

（1）各個(gè)批次的原煙依次通過(guò)每一道工序，且順序相同；

（2）不同批次的原煙加工時(shí)間已知；

（3）每臺(tái)設(shè)備在每個(gè)時(shí)刻只加工一批原煙；

（4）每批原煙只在每臺(tái)設(shè)備中加工一次。

由上可知，煙片預(yù)處理段的調(diào)度充分滿(mǎn)足典型的批量受限的有限緩沖區(qū)流水車(chē)間調(diào)度問(wèn)題（Flow-Shop Scheduling Problem, FSSP）特點(diǎn)，這是一個(gè)經(jīng)典的 NP（Non-deterministic Polynomial）問(wèn)題，難以直接求解。

2 基于生產(chǎn)單元的制絲預(yù)處理生產(chǎn)調(diào)度模型

2.1 模型設(shè)計(jì)

以 FSSP的角度分析煙葉預(yù)處理段生產(chǎn)調(diào)度過(guò)程，可將其抽象為數(shù)學(xué)描述：

在m臺(tái)設(shè)備上需要加工n個(gè)訂單，每個(gè)訂單都有m道工序，每個(gè)訂單的工序相同，且各個(gè)訂單在m臺(tái)設(shè)備中加工時(shí)間已知。每個(gè)設(shè)備同一時(shí)刻只能加工一個(gè)訂單，則調(diào)度目標(biāo)為根據(jù)條件設(shè)置合理的n個(gè)訂單的加工順序，從而使某些調(diào)度指標(biāo)達(dá)到最優(yōu)。

根據(jù)實(shí)際制絲生產(chǎn)單元提取必要屬性進(jìn)行抽象，從而獲得生產(chǎn)單元模型M和訂單模型N，以表示第 i道工序與 i-1道工序之間存在的緩沖區(qū)大小，表示第 i道工序的工藝制造能力；對(duì)于訂單而言，s表示訂單所需的不同物料種類(lèi)數(shù)目，表示第 i個(gè)訂單的優(yōu)先級(jí)，實(shí)際表示生產(chǎn)訂單牌號(hào)，高級(jí)的牌號(hào)優(yōu)先級(jí)高于低級(jí)。

①生產(chǎn)單元模型M：

基于訂單和生產(chǎn)單元的模型，設(shè)計(jì)以物料輸入、倉(cāng)儲(chǔ)輸出、最大流程時(shí)間、有效作業(yè)率等屬性組合成的評(píng)估模型 E，檢驗(yàn)訂單調(diào)度序列是否能夠更好地滿(mǎn)足排產(chǎn)調(diào)度情況，決策者可以根據(jù)實(shí)際生產(chǎn)需要選擇合適評(píng)估屬性。

③評(píng)估模型E

物料輸入：In

倉(cāng)儲(chǔ)庫(kù)存：Out

其中，In指的是訂單所需物料輸入：

Out指訂單生產(chǎn)完成后生成的半成品所需的倉(cāng)儲(chǔ)空間：

對(duì)于有效作業(yè)率ξ，其計(jì)算公式為：

2.2 算法設(shè)計(jì)

對(duì)于制絲過(guò)程煙片預(yù)處理生產(chǎn)單元的模型抽象如 x.x所述，求解該模型即是找到一個(gè)合理的訂單加工序列 π={π(1),π(2),π(3),…,π(n)}，使得訂單總生產(chǎn)時(shí)間最小化，節(jié)約生產(chǎn)成本，因此目標(biāo)函數(shù)為：

流水線(xiàn)調(diào)度問(wèn)題的核心在于如何更快更方便地找到那個(gè)相對(duì)最優(yōu)解，目前并不存在一個(gè)絕對(duì)有效的算法，能夠在多項(xiàng)式時(shí)間內(nèi)求出這個(gè)最優(yōu)解，經(jīng)過(guò)多年研究，業(yè)界對(duì)于這類(lèi)調(diào)度問(wèn)題已經(jīng)具有一定研究經(jīng)驗(yàn)，現(xiàn)在的研究可分為精確方法以及近似方法兩類(lèi)。

精確方法包括線(xiàn)性規(guī)劃[9]、分支定界方法[10]等，其目的為保證得到全局最優(yōu)解，其限制在于只能用于解決較小規(guī)模的流水線(xiàn)調(diào)度問(wèn)題，求解過(guò)程耗時(shí)較長(zhǎng)，效率低，但能夠保證解的準(zhǔn)確性。

而近似方法是相對(duì)于精確方法無(wú)法求解的情況下，尋找相對(duì)最優(yōu)解的算法，隨著流水線(xiàn)調(diào)度問(wèn)題日趨復(fù)雜，精確方法求解效率低下的情況下，近似方法能夠在較少的耗時(shí)中求解能夠接受的近似解，求解時(shí)間短，效率較高，如何提高近似解的準(zhǔn)確性和求解效率是目前的重要研究方向。近似方法主要包含構(gòu)造方法、局部搜索、人工智能、系統(tǒng)仿真[11]四類(lèi)。目前較常見(jiàn)的為人工智能算法，針對(duì)緩沖區(qū)是否有限的問(wèn)題，文獻(xiàn)[12-15]提出了混合蝙蝠算法、微粒群算法求解流水線(xiàn)調(diào)度問(wèn)題求解緩沖區(qū)有限的情況，文獻(xiàn)[16]考慮了緩沖區(qū)為0，即阻塞流水車(chē)間的調(diào)度問(wèn)題。

針對(duì)煙片預(yù)處理段的實(shí)際情況，我選擇以模擬退火算法[17]優(yōu)化的遺傳算法[18]求解。遺傳算法是一種基于自然選擇與遺傳機(jī)制的元啟發(fā)式搜索算法，將問(wèn)題求解的過(guò)程轉(zhuǎn)換為解空間的“染色體”迭代的過(guò)程，如圖2所示。具體實(shí)現(xiàn)步驟如下：

（1）參數(shù)編碼：使用無(wú)符號(hào)二進(jìn)制整數(shù)對(duì)訂單任務(wù)進(jìn)行編碼，設(shè)置種群大小S，迭代次數(shù)En。

（2）初始群體：由于生產(chǎn)實(shí)際情況可知，換牌頻繁則會(huì)影響生產(chǎn)效率，初始群體必然存在一定約束，因此選擇生產(chǎn)量最大牌號(hào)作為初始群體之一。

（3）適應(yīng)度函數(shù)：在此可將目標(biāo)函數(shù)（最大完工時(shí)間）作為適應(yīng)度函數(shù)的參數(shù)：

（4）遺傳算子計(jì)算

選擇：首先通過(guò)輪盤(pán)賭選擇方法執(zhí)行遺傳算法的初步選擇，然后將當(dāng)前群體中適應(yīng)度最高的個(gè)體完整地復(fù)制到下一代群體中。

交叉：設(shè)置交叉概率 θ ∈ [ 0,1]，根據(jù)交叉概率隨機(jī)選擇成對(duì)染色體按照單點(diǎn)交叉方式兩兩交叉。

變異：設(shè)置變異概率 η ∈ [ 0,1]，以基本位變異的方法按照變異概率隨機(jī)選取變異染色體進(jìn)行計(jì)算，形成新的一代種群。

（5）模擬退火優(yōu)化：針對(duì)遺傳算法編碼占用儲(chǔ)存空間大、容易陷入局部最優(yōu)解、爬山能力差等問(wèn)題，利用模擬退火算法進(jìn)行優(yōu)化，計(jì)算變異前后兩個(gè)種群的總適應(yīng)度大小 Efit1、 Efit2，若 Efit1< Efit2，則接受變異結(jié)果，確定變異后的種群為新一代種群；若 Efit1> Efit2，則考慮以概率p(dE)接受變異結(jié)果，且概率隨時(shí)間而降低，概率計(jì)算方法如下：

圖2 模擬退火算法優(yōu)化的遺傳算法求解流程Fig.2 The process of simulated annealing algorithm of genetic algorithm optimization

3 算例驗(yàn)證

為驗(yàn)證提出的調(diào)度模型能夠通過(guò)模擬退火算法改進(jìn)的遺傳算法求出最優(yōu)解，選取紅河卷煙廠(chǎng)實(shí)際生產(chǎn)流程中葉片預(yù)處理段生產(chǎn)單元作為設(shè)計(jì)參考，算法運(yùn)行環(huán)境為Windows 10, intel i7處理器，內(nèi)存16G，python 2.7。

葉片預(yù)處理生產(chǎn)單元模型可描述為下圖所示，它包括7個(gè)工序，其中松散回潮到煙片預(yù)備階段中存在一個(gè)緩沖區(qū)，映射到實(shí)際上為一個(gè)固定容量的儲(chǔ)柜，用于葉配工作，在此假設(shè)緩沖區(qū)僅能夠存儲(chǔ)同一批訂單的物料。

假設(shè)某日制絲訂單預(yù)處理段生產(chǎn)情況如下表所示，生產(chǎn)ABCD四種牌號(hào)的煙，一共10個(gè)訂單，各個(gè)訂單所需原煙質(zhì)量如表中所示。

表1 實(shí)際訂單批次信息Tab.1 Actual order batch information

表2 不同規(guī)模訂單算法執(zhí)行結(jié)果Tab.2 Results of algorithm in different size of orders

對(duì)于訂單中的數(shù)據(jù)，設(shè)置遺傳算法的初始種群規(guī)模為 100，交叉概率為 0.95，變異概率為 0.05，迭代代數(shù)為100，退火模擬算法的參數(shù)k為1，計(jì)算的迭代曲線(xiàn)如圖3所示，計(jì)算獲得結(jié)果見(jiàn)表2第一行，再與正常執(zhí)行的調(diào)度順序相比，其總生產(chǎn)時(shí)間共減少了75分鐘，可以證明調(diào)度算法的優(yōu)越性。

圖3 迭代曲線(xiàn)Fig.3 Iterative curve

考慮到訂單批次增長(zhǎng)的情況，再以20、30、40、50、60為規(guī)模，模擬調(diào)度情況，獲得表2中數(shù)據(jù)，可以發(fā)現(xiàn)，該算法能夠適應(yīng)訂單規(guī)模的增長(zhǎng)情況，輔助調(diào)度員獲得最優(yōu)訂單調(diào)度方案。

4 結(jié)論

本文針對(duì)紅河煙廠(chǎng)的實(shí)際生產(chǎn)情況進(jìn)行研究，對(duì)煙草制絲生產(chǎn)流程中的關(guān)鍵生產(chǎn)單元——煙片預(yù)處理生產(chǎn)單元的調(diào)度排產(chǎn)進(jìn)行研究，將其抽象成為求解流程型有限緩沖區(qū)的流水線(xiàn)調(diào)度問(wèn)題，通過(guò)模擬退火算法優(yōu)化的遺傳算法求解最優(yōu)解，最后通過(guò)模擬不同規(guī)模的訂單調(diào)度過(guò)程，驗(yàn)證了經(jīng)過(guò)調(diào)度后的結(jié)果更優(yōu)，驗(yàn)證了模型的實(shí)用性。未來(lái)的研究方向在于將該抽象模型應(yīng)用到不同的生產(chǎn)單元中，對(duì)訂單調(diào)度過(guò)程進(jìn)行抽象和優(yōu)化。