向伟康，殷军普

（上海威士顿信息技术股份有限公司，上海 200000）

0 引言

遗传算法作为最优化领域中的一个热点得到了广泛应用，但由于其存在算法早期收敛、耗时长、局部搜索能力差等缺陷，在实际应用中一般会基于求解问题进行针对性优化。例如，文献［2］设计了一种改进的遗传算法解决旅行商问题，引入贪婪算法初始化种群并自适应调节交叉与变异；提出了一种基于二代非劣前沿排序遗传算法的城市物流设施选址方法；基于新的编码方式提出了一种基于改进遗传算法的微小图像边缘特征快速识别方法；提出了一种改进的相对快速收敛的遗传算法，并应用到网格任务调度管理，其增加了对染色体的分割与重组[1]。本文则提出了一种基于改进遗传算法的烟厂卷包排产方法，针对烟厂卷包排产问题，采用特殊编码方式、删除了交叉算子、改进了初始化与变异算子并选择精英保留策略，以提高遗传算法的收敛速度。

1 烟厂卷包排产问题描述

烟厂卷包排产是以月为周期，当月要制定下月的生产计划。已知下月的基础数据为n台设备和m个订单。

设备属性：设备号（设备的编号）、可生产牌号（设备能生产的烟支编号）、各牌号生产速度（设备单位时间内生产指定牌号的数量）、换牌时间（从一个牌号切换生产另一个牌号时，停止生产的时间）、工班制度（设备可使用的时间段）。

订单属性：订单号（订单的编号）、需求牌号（订单所需烟支编号）、需求量（订单所需烟支数量）、需求时间点（订单需在该时间点前完成生产）。……