基于遗传算法的卷烟换牌排产与优化设计

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

红云红河烟草（集团）有限责任公司昆明卷烟厂，昆明市五华区红锦路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，有效提高了生产效率。该方法可为优化卷烟生产计划和调度策略提供支持。