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

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

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

1 問(wèn)題分析

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

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

卷煙生產(chǎn)計(jì)劃通常按月執(zhí)行，要求各品牌卷煙按時(shí)完成計(jì)劃任務(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é)基本相同，因此各品牌間換牌所耗時(shí)間存在差異。

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

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

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

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

2 算法優(yōu)化

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

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

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

式中：xi為兩品牌間的換牌耗時(shí)。

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

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

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

3 應(yīng)用效果

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

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

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

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

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

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

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

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

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

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

表4 試驗(yàn)換牌耗時(shí)Tab.4 Experimental brand change duration （min）

研究還發(fā)現(xiàn)，運(yùn)用遺傳算法仿真得到的最優(yōu)解不止一個(gè)，由于某些品牌的設(shè)備規(guī)格相同，在實(shí)際生產(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ī)格相同，品牌及品牌組合可互換排序，見(jiàn)表5。在排產(chǎn)中根據(jù)實(shí)際情況進(jìn)行順序調(diào)整，不會(huì)影響換牌效率。

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

4 結(jié)論

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