李 丹，周延輝，周 明，曾 昕

紅云紅河煙草（集團(tuán)）有限責(zé)任公司昆明卷煙廠，昆明市五華區(qū)紅錦路366 號 650202

近年來在卷煙生產(chǎn)小批量、多規(guī)格、多品牌的市場需求下，對生產(chǎn)工藝、排產(chǎn)效率和快速反應(yīng)能力提出了更高要求[1-2]。生產(chǎn)效率是卷煙生產(chǎn)企業(yè)關(guān)注的重點問題之一，直接影響企業(yè)生產(chǎn)進(jìn)度，特別是承擔(dān)多品牌生產(chǎn)任務(wù)的機(jī)組，具有品牌多、任務(wù)重、卷煙規(guī)格復(fù)雜等特點，在頻繁換牌的生產(chǎn)條件下，保證設(shè)備生產(chǎn)效率十分重要。隨著卷煙生產(chǎn)精益化管理的不斷推進(jìn)，卷煙企業(yè)大多采用ERP（Enterprise Resource Planning）系統(tǒng)進(jìn)行排產(chǎn)調(diào)度，但該方法過于依賴人工經(jīng)驗，且其算法所受制約較多，難以得出最優(yōu)方案，影響生產(chǎn)效率。針對此問題，謝瑞波[3]設(shè)計了卷煙排產(chǎn)優(yōu)化及調(diào)度系統(tǒng)，鄧燦勇等[4]采用遺傳算法進(jìn)行卷煙排產(chǎn)，金劍等[5]通過建立模型優(yōu)化了排產(chǎn)計劃。上述研究主要是針對大品牌或總?cè)蝿?wù)的產(chǎn)能分配問題，未涉及多品牌卷煙排產(chǎn)。雖然有些企業(yè)制定了卷包換牌設(shè)備保養(yǎng)、換牌工藝流程等管理規(guī)范，但仍未能從根本上解決換牌生產(chǎn)效率低等問題，優(yōu)化排產(chǎn)計劃、減少換牌時間已成為提升多品牌機(jī)組生產(chǎn)效率的關(guān)鍵。 生產(chǎn)排程問題類似于TSP（Traveling Salesman Problem）問題，需要處理錯綜復(fù)雜的約束條件。研究表明TSP 問題無法用精確算法求解，只能尋求有效近似算法[6]。常用的求解TSP問題的方法主要有貪婪算法、粒子群算法、蟻群算法和遺傳算法等[7]。對比發(fā)現(xiàn)，遺傳算法的優(yōu)勢特性和廣泛性適用于卷煙換牌排產(chǎn)，但遺傳算法容易出現(xiàn)早熟問題，對此可采用惡化變異概率和增大交叉基因兩種方法進(jìn)行優(yōu)化，當(dāng)最優(yōu)解不發(fā)生變化且迭代次數(shù)較少時，增大變異概率和交叉概率，可防止遺傳算法所求解為局部最優(yōu)解[8-10]。為此，以昆明卷煙廠為例，通過分析生產(chǎn)計劃與調(diào)度策略[11-13]，采用遺傳算法對卷煙換牌排產(chǎn)進(jìn)行優(yōu)化設(shè)計，以期減少卷煙換牌所耗時間，提高設(shè)備生產(chǎn)效率。

1 問題分析

卷煙生產(chǎn)工藝流程主要包括制絲和卷包兩個環(huán)節(jié)，見圖1。制絲車間負(fù)責(zé)煙絲制造和供應(yīng)，制絲和卷包之間存在一個緩存區(qū)（即貯絲柜），用于儲存半成品煙絲。卷包車間完成煙支卷接和包裝，是卷煙生產(chǎn)的核心環(huán)節(jié)，根據(jù)卷包設(shè)備機(jī)型和數(shù)量進(jìn)行供絲分配，生產(chǎn)出的成品卷煙經(jīng)過運(yùn)輸、封箱后進(jìn)入成品高架庫等待發(fā)貨。

圖1 卷煙生產(chǎn)工藝流程Fig.1 Technical process flow of cigarette production

卷煙生產(chǎn)計劃通常按月執(zhí)行，要求各品牌卷煙按時完成計劃任務(wù)。卷包車間的設(shè)備分為單一品牌機(jī)組和多品牌機(jī)組，多品牌機(jī)組在完成某品牌卷煙生產(chǎn)任務(wù)后，經(jīng)換牌調(diào)整后生產(chǎn)下一卷煙品牌。換牌工作包括煙絲排空、濾嘴排空、輔料清退、清理吹車、調(diào)整設(shè)備規(guī)格、輔料輸送、煙絲接收、濾嘴接收、輔料加載以及生產(chǎn)調(diào)試等步驟，除調(diào)整設(shè)備規(guī)格環(huán)節(jié)存在差異外，其他環(huán)節(jié)基本相同，因此各品牌間換牌所耗時間存在差異。

以昆明卷煙廠22 號機(jī)組PROTOS70-FOCKE 350 為例，共承擔(dān)8 個品牌的生產(chǎn)任務(wù)，包括1 個普通品牌（A）和7 個特殊品牌（B、C、D、E、F、G、H），普通品牌產(chǎn)量不限制，而特殊品牌產(chǎn)量固定。因此，在月初生產(chǎn)A 品牌時不確定排序更換B、C、D、E、F、G、H 品牌，生產(chǎn)完成后又更換為A 品牌，即A→X→X→X→X→X→X→X→A（X 代表B、C、D、E、F、G、H，不重復(fù)出現(xiàn)）。調(diào)整設(shè)備規(guī)格外的其他環(huán)節(jié)，通用耗時約為30 min，而調(diào)整設(shè)備規(guī)格主要對卷接機(jī)組的濾嘴長度、平準(zhǔn)器類型、接裝紙寬度、膠輥類型等進(jìn)行調(diào)整，以耗時長短對這4種情況進(jìn)行優(yōu)先級排序，耗時長的優(yōu)先級高，即如果兩品牌間優(yōu)先級高的設(shè)備規(guī)格不同，那么在此時間內(nèi)可以并行完成優(yōu)先級低的規(guī)格調(diào)整。因此，計算換牌時間時只需考慮優(yōu)先級高的設(shè)備規(guī)格，換牌耗時T 為：

式中：xmint表示設(shè)備規(guī)格優(yōu)先級高的調(diào)整耗時；k 為通用耗時，為30 min。

表1 為8 個卷煙品牌4 種情況下設(shè)備規(guī)格調(diào)整優(yōu)先級排序及所用時間?？梢?，不同設(shè)備規(guī)格調(diào)整決定了換牌所用時間，其中調(diào)整濾嘴長度耗時最長，調(diào)整膠輥類型耗時最短，如何使換牌耗時最短是提高多品牌機(jī)組生產(chǎn)效率的關(guān)鍵。

表1 卷煙設(shè)備規(guī)格調(diào)整優(yōu)先級排序和耗時Tab.1 Priority and duration of cigarette making machine adjustment

2 算法優(yōu)化

遺傳算法是仿照生物遺傳和進(jìn)化原理，同時與隨機(jī)統(tǒng)計方法相結(jié)合而形成的一種算法。其求解過程是逐代尋找問題最優(yōu)解，利用初始變量群體逐代進(jìn)行搜索，直至完成預(yù)先假定的迭代次數(shù)或者找到滿足收斂條件才停止。圖2 可見，運(yùn)用遺傳算法進(jìn)行求解時，首先對問題參數(shù)進(jìn)行編碼，隨機(jī)產(chǎn)生一個初始種群，計算樣本自適應(yīng)函數(shù)；然后進(jìn)行選擇、交叉、變異等遺傳搜索操作，迭代到最大次數(shù)，直到找到滿足收斂條件的解，即可得到問題的最優(yōu)解。

圖2 遺傳算法搜索原理Fig.2 Search principle of genetic algorithm

根據(jù)卷煙生產(chǎn)實際情況，運(yùn)用遺傳算法對卷煙換牌排產(chǎn)優(yōu)化問題進(jìn)行求解時需考慮以下因素：①優(yōu)化目標(biāo)，使換牌耗時最小化，尋找換牌耗時最短的最優(yōu)換牌序列；②約束條件，普通品牌為換牌最初和最后品牌，即A 品牌排在換牌序列的首和尾，其他7 個特殊品牌各出現(xiàn)一次。由此得知，在A 品牌排在首和尾的約束下，該問題是在A（7，7）=5 040 種方案中尋找一個或多個最優(yōu)排序方案，求解的目的是將7 個特殊品牌進(jìn)行換牌組合排序，尋找換牌耗時最短的排序方案。該問題的目標(biāo)函數(shù)為：

式中：xi為兩品牌間的換牌耗時。

根據(jù)遺傳算法適者生存原則，個體適應(yīng)度越高被選中的機(jī)會越大。為了計算個體的適配值，將目標(biāo)函數(shù)映射為遺傳算法的適應(yīng)度函數(shù)。由于該問題的目的是求出最短換牌耗時，屬于最小化問題，所以適應(yīng)度函數(shù)為：

式中：Cmax為預(yù)設(shè)參數(shù)。

在隨機(jī)生成的樣本（方案）中，每個樣本點（品牌）都可以作為一個基因點進(jìn)行交叉處理，交叉后滿足完全遍歷和無重復(fù)兩個條件，即可確認(rèn)父代有效，隨機(jī)生成交叉的基因點，再根據(jù)生成的位置繼續(xù)進(jìn)行交叉。交叉后的變異過程也是為了加快種群進(jìn)化，在進(jìn)行交叉和變異時，遺傳算法可能會出現(xiàn)個體適應(yīng)度趨于一致或者局部最優(yōu)解等情況，通過對交叉概率Pc和變異概率Pm進(jìn)行調(diào)整，可避免出現(xiàn)算法早熟問題，保證遺傳算法的收斂性。

3 應(yīng)用效果

3.1 數(shù)據(jù)預(yù)處理

以22 號機(jī)組PROTOS70-FOCKE350 和8 個卷煙品牌（A、B、C、D、E、F、G、H）為例，濾嘴長度、平準(zhǔn)器類型、接裝紙寬度、膠輥類型的調(diào)整耗時分別為150、60、40、20 min。當(dāng)兩品牌間進(jìn)行換牌時，設(shè)備規(guī)格調(diào)整環(huán)節(jié)因耗時較長其優(yōu)先級最高，設(shè)備規(guī)格調(diào)整耗時與通用耗時累計即為換牌耗時。表2 為各品牌卷煙設(shè)備規(guī)格，表3 為兩品牌間的換牌耗時。

表2 各品牌卷煙設(shè)備規(guī)格①Tab.2 Specification of each brand cigarette making machine

表3 各品牌卷煙換牌耗時Tab.3 Brand change duration for each cigarette brand（min）

3.2 數(shù)據(jù)分析

以2018 年1 月22 號 機(jī) 組PROTOS70-FOCKE 350 為對象分別采集數(shù)據(jù)，仿真數(shù)據(jù)通過仿真分析模擬運(yùn)算得到，試驗數(shù)據(jù)通過現(xiàn)場統(tǒng)計換牌耗時得到。為考察實際應(yīng)用效果，選取2017 年1—9 月的換牌耗時作為對比數(shù)據(jù)，其平均換牌耗時為794 min。在數(shù)據(jù)預(yù)處理的基礎(chǔ)上進(jìn)行仿真，按照圖3 流程進(jìn)行遺傳搜索，求解出換牌耗時最短的最優(yōu)排序，當(dāng)算法迭代到最大次數(shù)后，得到圖4 所示的迭代曲線。

圖3 算法流程圖Fig.3 Algorithm flowchart

圖4 可見，最大迭代次數(shù)為100 次，算法經(jīng)過多次迭代后逐漸收斂，在此過程中有幾次陷入局部最優(yōu)解，但通過適當(dāng)增加交叉概率Pc和變異概率Pm，算法能夠快速跳出局部最優(yōu)解繼續(xù)優(yōu)化，逐漸收斂得到全局最優(yōu)解660 min，最終得到最優(yōu)生產(chǎn)排序為A→G→F→E→H→D→B→C→A，而排序A→B→E→C→F→D→G→H→A 換牌耗時最長，為900 min。仿真結(jié)果表明，最優(yōu)排產(chǎn)方案最多可節(jié)約時間240 min。

圖4 算法迭代曲線Fig.4 Algorithm iterative curve

根據(jù)仿真最優(yōu)排序進(jìn)行卷煙排產(chǎn)得到試驗數(shù)據(jù)，計算當(dāng)月?lián)Q牌耗時，結(jié)果見表4?？梢?，優(yōu)化后換牌耗時689 min，優(yōu)化前平均耗時794 min，最優(yōu)排產(chǎn)方案節(jié)約時間105 min。仿真數(shù)據(jù)與試驗數(shù)據(jù)均表明優(yōu)化后排產(chǎn)方案可有效減少換牌耗時。

表4 試驗換牌耗時Tab.4 Experimental brand change duration （min）

研究還發(fā)現(xiàn)，運(yùn)用遺傳算法仿真得到的最優(yōu)解不止一個，由于某些品牌的設(shè)備規(guī)格相同，在實際生產(chǎn)中可靈活調(diào)整。例如，品牌B（b，b，b，b）與品牌C（b，b，b，b），品牌D（b，b，b，c）與品牌H（b，b，b，c），品牌E（b，c，c，d）與品牌F（b，c，c，d）的設(shè)備規(guī)格相同，品牌及品牌組合可互換排序，見表5。在排產(chǎn)中根據(jù)實際情況進(jìn)行順序調(diào)整，不會影響換牌效率。

表5 品牌換序Tab.5 Brand change order

4 結(jié)論

針對卷煙生產(chǎn)換牌耗時較長等問題，結(jié)合生產(chǎn)工藝流程，采用遺傳算法對卷煙換牌排產(chǎn)進(jìn)行了優(yōu)化設(shè)計，通過加入惡化變異概率和增大交叉基因以防止算法陷入局部最優(yōu)解，遺傳算法能夠快速找到全局最優(yōu)解，計算得到最短換牌耗時并給出最優(yōu)排產(chǎn)方案。仿真結(jié)果表明，在5 040 種換牌方案中尋找到的最優(yōu)排產(chǎn)方案可節(jié)約時間240 min；根據(jù)仿真最優(yōu)排序進(jìn)行卷煙排產(chǎn)試驗，結(jié)果顯示優(yōu)化后換牌耗時比優(yōu)化前縮短105 min，有效提高了生產(chǎn)效率。該方法可為優(yōu)化卷煙生產(chǎn)計劃和調(diào)度策略提供支持。