基于遺傳算法的卷煙換牌排產與優化設計

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

紅云紅河煙草（集團）有限責任公司昆明卷煙廠，昆明市五華區紅錦路366 號 650202

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

1 問題分析

卷煙生產工藝流程主要包括制絲和卷包兩個環節，見圖1。制絲車間負責煙絲制造和供應，制絲和卷包之間存在一個緩存區（即貯絲柜），用于儲存半成品煙絲。卷包車間完成煙支卷接和包裝，是卷煙生產的核心環節，根據卷包設備機型和數量進行供絲分配，生產出的成品卷煙經過運輸、封箱后進入成品高架庫等待發貨。

圖1 卷煙生產工藝流程Fig.1 Technical process flow of cigarette production

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

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

式中：xmint表示設備規格優先級高的調整耗時；k 為通用耗時，為30 min。

表1 為8 個卷煙品牌4 種情況下設備規格調整優先級排序及所用時間。可見，不同設備規格調整決定了換牌所用時間，其中調整濾嘴長度耗時最長，調整膠輥類型耗時最短，如何使換牌耗時最短是提高多品牌機組生產效率的關鍵。

表1 卷煙設備規格調整優先級排序和耗時Tab.1 Priority and duration of cigarette making machine adjustment

2 算法優化

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

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

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

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

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

式中：Cmax為預設參數。

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

3 應用效果

3.1 數據預處理

以22 號機組PROTOS70-FOCKE350 和8 個卷煙品牌（A、B、C、D、E、F、G、H）為例，濾嘴長度、平準器類型、接裝紙寬度、膠輥類型的調整耗時分別為150、60、40、20 min。當兩品牌間進行換牌時，設備規格調整環節因耗時較長其優先級最高，設備規格調整耗時與通用耗時累計即為換牌耗時。表2 為各品牌卷煙設備規格，表3 為兩品牌間的換牌耗時。

表2 各品牌卷煙設備規格①Tab.2 Specification of each brand cigarette making machine

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

3.2 數據分析

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

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

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

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

根據仿真最優排序進行卷煙排產得到試驗數據，計算當月換牌耗時，結果見表4。可見，優化后換牌耗時689 min，優化前平均耗時794 min，最優排產方案節約時間105 min。仿真數據與試驗數據均表明優化后排產方案可有效減少換牌耗時。

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

研究還發現，運用遺傳算法仿真得到的最優解不止一個，由于某些品牌的設備規格相同，在實際生產中可靈活調整。例如，品牌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）的設備規格相同，品牌及品牌組合可互換排序，見表5。在排產中根據實際情況進行順序調整，不會影響換牌效率。

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

4 結論

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