基于遗传算法的两阶段多目标卷包生产调度优化

王劲松，张 敏，杨 明，万年彬，罗 冬，皮俊涛，杨丁凤

（1.襄阳卷烟厂，湖北 襄阳 441000；2.华中科技大学 管理学院，湖北 武汉 430074）

0 引言

中国是世界上最大的卷烟生产国与消费国，卷烟消费量占世界烟草消费总量的约30%，同时烟草是国家和地方财税的重要来源。市场竞争日益激烈，生产计划管理受市场影响越来越大，多品种小批量的需求逐渐增多，而卷包排产与上游制丝计划、滤棒生产计划、下游封装计划相互影响，相互制约，烟厂生产排产的复杂性大大增加，卷包自动排产及卷包优化排产得到越来越多烟厂的关注，如何按订单组织生产成为烟厂当下的迫切需求[1-3]。

卷烟生产计划的分层优化框架将冗长复杂的生产过程分块，为生产排程优化提供了清晰的思路与范围。王军，等[4]将卷烟生产过程分为上层总生产计划层、中间卷包分组计划层、下层制丝批次计划层。严蕾[5]研究分析了某卷烟厂卷包车间的交接班工作。王劲松，等[6]考虑卷烟生产的全过程，设计了包括卷包车间自动排产、制丝车间自动排产、滤棒生产计划优化、辅料组盘计划优化、原料香糖料配送计划优化共六个功能模块。

生产排程问题属于NP-hard问题，很难寻求到问题的最优解[7]。陈庄，等[8-9]分析了卷烟生产线的工艺流程，提出了有关的合理假设，构建了卷烟生产线优化调度模型；谢五峰，等[10]基于SIMATICIT（西门子平台）的软件架构和规则算法建立了卷包排产子系统；郝雨[11]用层次化建模方法分别构建了卷包和制丝的调度模型。王爱民，等[12]、丁雷，等[13]以资源动态组合为核心对卷包作业动态调度技术进行了研究。姚丽丽，等[14]分析了排产中工艺路径的规则，提出了嵌入规则的遗传算法。金静文[15]设计了一种基于首批作业计划的二重启发式算法，对卷包车间柔性资源动态组合生产进行了研究；王伟玲，等[16]建立了多目标混合整数规划模型，采用NSGA-II 算法对多目标进行求解。李丹，等[17]采用遗传算法对卷烟换牌排产进行了优化设计。刘西尧，等[18]提出按喂丝机排产的多种群混合遗传算法。周秋艳，等[19]提出了一种以“等待时间最短”为主的生产排程智能优化算法。陈应飞，等[20]应用了嵌入粒子群算法和模拟退火遗传算法。

目前，国内关于卷包生产调度的研究多是固定的链路连接关系，即卷接机与喂丝机的连接是排产前人工确定的，且排产过程中不可更换，导致排产结果很难满足实际生产；或是先选中一种链路关系，再判断时间段内是否可用，不可用再更换下一种链路关系，这种算法不够灵活，因为链路选择规则多、难度大，且排产容易出现卷接机等待喂丝机（或封装机）的情况，导致卷接机在本该工作的时间段待机，订单不能按时交付。因此，现有的卷包生产调度优化算法很难在实践中直接应用。

本文结合襄阳卷烟厂的实际生产情况，首先安排卷接机的生产订单，保证卷接机在正常工作时间内不停机，再根据柔性连接关系确定卷接机与上游喂丝机、发射机，下游封装机每时段内的连接路径，逐步实现面向计划和实际生产的卷包生产优化调度。

1 问题描述

卷烟卷包生产具体生产线工艺流程如图1所示。卷接机接收到喂丝机或人工供应的烟丝和发射机发射的滤棒后进行卷接，卷接结束由包装机包装成条盒后进入封装机封装成箱，最后入库。

烟厂收到中烟下达的生产调度令，生产调度人员将调度令分解成订单（大牌号拆分为多个小订单），综合卷包车间的设备、工作日历、库存等信息编制卷包生产计划。此过程可抽象描述为：

假设某烟厂可生产G个规格共B个牌号的卷烟，拥有m台卷接机，w台喂丝机，f台滤棒发射机，z台封装机，其中牌号与卷接机、喂丝机与卷接机、发射机与卷接机、卷接机与封装机之间的柔性连接关系已知，每个规格下的卷烟所用卷接机、封装机相互独立，卷接机j对牌号b的卷接速率为vjb，卷接机从牌号a换牌

图1 卷包工艺流程图

图2 卷包计划甘特图

某月烟厂收到P个订单，订单信息包括对应的牌号、生产数量、交货期、最早开始时间，当月卷接机的工作日历已知，订单优先级已知。调度人员需要决策每台卷接机每天应生产的订单、订单的生产顺序与数量以及卷接机所连接的喂丝机、滤棒发射机、封装机，其中链路关系在生产过程中可能会发生改变，使得生产计划既满足卷接设备不停机、齐开齐停等约束，也能达到设定的目标（逾期订单最少、换牌次数最少等）。最终得到如图2所示的卷包生产计划，其中a图为卷接机的生产计划，主要包括机组与订单的对应关系，生产顺序与生产起止时间，不同机组上的同一个订单同时生产同时停止；b图为喂丝机安排计划，主要显示生产过程中的喂丝机连接情况，不同的机组生产同一个订单，但在不同时间段使用的喂丝机可能不同（滤棒发射机、封装机图类似）。

2 优化建模

2.1 卷包生产调度的假设及原则

结合烟厂的调研结果，卷包作业排产过程中需要遵循以下假设与原则：（1）假设原辅料供应能力为无穷大。（2）假设所有卷接机能按照既定的工作日历正常工作。假设保证了每一个订单一定能在其最早开始时间开始生产，且生产设备在工作日历的可用时间段内是连续生产的。出现违反假设的情况，则需要对卷包调度计划进行重调度。（3）订单连续生产原则：一般情况下，订单的生产不能中断，同一订单必须连续生产。（4）订单优先级生产原则：订单优先级是由人工根据重要程度对订单进行的排序，排产中按照订单优先级逐一安排各订单的生产。（5）机台齐停原则：执行同一订单的多台卷接机需要满足齐停规则，以便于卷包车间同时换牌，减少生产混乱，也有利于喂丝机同时向对应卷接机供应烟丝，便于制丝车间按照烟丝批次下达制丝作业计划。（6）机台优选组合原则：根据烟草企业手工排产经验总结，提前设置机台资源的优选组合配置，比如：固定某些机台用于生产某一牌号，某些牌号优先选择某喂丝机供丝。（7）考虑瓶颈资源能力原则：在排产中，主要考虑瓶颈资源卷接机组的生产能力约束，针对瓶颈资源建立模型进行求解，先得出卷接机组上的生产作业计划，再根据设备链路关系，得出工艺路径上非瓶颈资源的生产作业计划。

2.2 卷包生产调度的约束

卷包生产调度的瓶颈资源为卷接机，本文以卷接机为核心建立模型。卷包生产调度需满足多方面的约束：（1）订单交货期约束。（2）订单最早开始时间约束。订单的原辅料需要备货时间，订单只有在原辅料到位后才能开始生产。（3）订单生产数量约束。当月订单的生产数量总和应不小于订单需求量。（4）设备产能约束。卷包调度的结果显示以“天”为粒度，每天的产量不能大于设备的最大产能。（5）柔性连接关系约束。牌号与卷接机、喂丝机与卷接机之间是多对多的柔性连接关系，但在某个时刻只能选择一个牌号生产，一台喂丝机供丝。（6）换牌时间约束。卷接机上会安排多个生产订单，订单按序生产，前一个订单到下一个订单需要切换时间，切换时间不能小于换牌时间。（7）工作日历约束。每台卷接机的日保养时间、接班保养时间、轮保时间、放假时间等不同，导致每台卷接机的可用时间不同，排产中必须考虑这些时间，排产结果才能与实际相符。

2.3 卷包生产调度的目标

卷包生产是一个多部门协同的生产过程，需要满足多个目标。本文主要考虑以下目标：逾期订单数量最少，最大完工时间最小，换牌次数最少，人工喂丝最少，卷接机完工时间方差最小。目标的重要性依次降低，即逾期订单数量最少的计划可能不止一个，在这些计划中，进一步找到最大完工时间最小的计划，再找到换牌次数最小的订单，依次优化目标。其中逾期订单数量最少是一级目标，用式（1）表示，若订单结束时间Ei大于订单交货期Di，则标记此订单逾期。最大完工时间最小为二级目标，用式（2）表示。其余目标为再次一级目标，用式（3）-式（5）表示，其中Cj表示卷接机j上的换牌次数，W表示人工喂丝的烟支数量，σ表示卷接机完工时间的方差。通过权重来区分目标的重要程度，用式（6）表示，在此式的基础上进行轮盘赌选择计算。本文中权重依次为0.40，0.30，0.15，0.10，0.05。

3 算法设计

本文提出一种两阶段遗传算法，其基本思路是：（1）仅考虑牌号与卷接机的柔性关系，确定每台卷接机上生产的牌号，从而确定其生产的订单，再根据订单优先生产顺序，形成卷接机生产计划；（2）对于阶段一的生产计划，得到每一台卷接机的生产时间线，再结合卷接机与喂丝机、封装机、发射机的柔性关系及优化规则确定每个时刻的链路关系。

这种两阶段遗传算法将卷接计划与链路关系计划分开，充分考虑了柔性连接关系，保证了卷接机连续生产，得到的结果更符合实际生产情况。

3.1 机台分组

将链路关系完全相同、可生产牌号完全相同的卷接机分为一个机组。同一时间一台喂丝机只能供应一种烟丝，所以与同一喂丝机相连的卷接机最好生产同样的牌号，否则同一时间生产牌号过多，容易出现增加人工上丝、部分烟丝过期、部分卷接机等待喂丝机、换牌人员调度混乱等问题。每个机组内卷接机安排的订单以及订单生产顺序相同，但因工作日历的差别可能会导致每台卷接机具体生产数量不同。

3.2 第一阶段编码

一个有效的染色体的一个基因位表示一个机组上生产的订单编号。以6个机组、7个订单为例，如图3所示。

图3 第一阶段染色体编码方式

一个染色体有6个基因位（机组个数），表示机组1生产订单6,7，机组2生产订单5,6,7，机组3生产订单5,6,7，机组4生产订单3,4,7，机组5生产订单2，机组6生产订单1,2。一条染色体必须包含所有订单{1,2,3,4,5,6,7}。

3.3 齐停算法

齐停算法主要用于第一阶段的染色体解码过程中。一个订单由多台卷接机进行生产时，要求这些卷接机同时释放，但由于订单与机组的组合不同，卷接机的工作日历不同，造成生产同一订单的卷接机不能同时释放。采用对工作日历的可用时间段逐一推进的方法，计算出具体的齐停时间点，具体操作如下：

Step1:找到生产此订单的所有卷接机，罗列出这些卷接机的所有可用时间段，并按照时间段从小到大排列，建立可用时间集R={(time1,1,time1,2),(time2,1,time2,2),…,(timen,1,timen,2)} 。 (time1,1,time1,2) 表示第一个可用时间段的起止时间点，在时间段time1,1～time1,2内，卷接机正常工作，而在时间段time1,2～time2,1内，卷接机停机。

Step2:初始化i=1,计算时间段（timei,1,timei,2)的产量，再计算出订单累计产量，与需求量比较，若累计产量高于订单需求量，则进入步骤3，否则表示订单不能在此时间段内结束生产，将时间段往下推一个，令i=i+1。

Step3:订单能在时间段（timei,1,timei,2)内结束生产，因此需要计算出具体齐停的时间点，令st=timei,1,通过公式计算订单b的具体结束时间点，其中rest_m表示订单在st时刻的剩余产量。

3.4 第二阶段编码

由第一阶段的编码及齐停算法，得到了卷接机的生产计划，以6个卷接机机组，7个订单为例，结果如图2(a)所示。整个时间线被切割成5个小时间段，每个时间段内的链路关系互相独立。在时间段1中的链路关系生产结束后释放，在时间段2重新组合，时间段2结束后再释放，时间段3重新组合，以此类推。这一阶段编码共有5个基因位，即一列表示一个基因位，每个基因位表示所有卷接机组在时间段内对应连接的喂丝机，如图2(b)所示。

第二阶段的编码优化：图2(b)中每一列表示某时间段内已安排的链路关系，链路关系优化的一个重要指标为切换次数最少，所以在生成下一列链路时，先判断之前的链路是否依旧可用，若可用则直接沿用上一列的链路，若不可用则重新生成。

3.5 算法流程

3.5.1 种群初始化。种群规模为pu，初始种群由两部分构成：一部分根据机台优选组合原则产生，即总结手工排产经验，将认为可能不错的组合作为部分输入；另一部分则根据卷接机与牌号的柔性连接关系随机组合生成。

3.5.2 嵌入第二阶段遗传算法。对种群中的每一个个体，安排每一个时间段的喂丝机、封装机、发射机。将链路关系独立安排，使得处理难度降低。安排链路关系需满足的约束有：（1）设备之间的柔性连接关系。（2）某时刻卷接机只能与一台喂丝机相连、一台发射机相连、一台封装机相连。（3）喂丝机连接数量上限约束。某时刻一台喂丝机最多能同时给有限数量的卷接机供丝，发射机与封装机同理。优化目标：（1）人工喂丝最少；（2）半自动喂丝最少；（3）切换次数最少。3.5.3 选择（多目标的处理）。采用最优个体和轮盘赌混合的方式进行选择。本文考虑了5个目标：逾期订单数量最少，最大完工时间最小，换牌次数最少，人工喂丝最少，卷接机停止时间方差最小。根据目标值排序，当第一目标最优时，找第二目标最优，再找第三目标最优，以此类推。将种群中排前10%的个体直接复制到下一代的种群中，这样很好的保留了上一代的优秀个体，也在一定程度上加快了收敛速度。

剩余90%的个体采用轮盘赌的方式进行选择。卷包生产调度问题属于多目标复杂问题，一般可直接根据权重计算出每个个体的综合目标值，由于5个目标值之间数值差距太大，即使极端化设置权重，也很难消除数量级之间的差距，所以本文先在种群中对每个目标值进行比较，将目标值归一化后再加权计算，作为轮盘赌选择的基础，见式（8）。

3.5.4 交叉。采用单点交叉的方式进行交叉。交叉过程如下：

Step1:计数器g=0，作为交叉的父本father和母本mother；

Step2:判断是否进行交叉。产生一个随机数r，如果r ≤Pc（交叉概率），进行Step3，否则父本和母本直接进入下一代种群中，ch ild1=fa th er, ch ild2=mo th er；

Step3:生成一个机组数量JQ以内的整数随机数rr(1 ≤rr ≤JQ)，将随机数及随机数以后的机组上生产的订单进行交叉，得到两个子代；

Step4:分别判断ch ild1、ch ild2是否包含本月所要生产的所有订单，如果包含，则是可行解，写进新的种群，g=g+2，否则进入Step5；

Step5:子代中不包含所有订单，找到未包含订单，对这些订单逐一进行安排，对子代进行修正，然后写进新种群，g=g+2；

Step6:直到新种群中的个体数等于种群规模时停止，即g=pu。

3.5.5 变异。采用单点变异的方式进行变异。变异过程如下：

Step1：计数器g=0，从种群中选择一个个体，作为变异的父本father；

Step2：判断是否进行变异。产生一个随机数r，如果r ≤Pm（变异概率），进入Step3，否则父本不变异，直接进入下一代种群中，ch ild1=fa th er；

Step3：生成一个机组数量JQ以内的整数随机数rr(1 ≤rr ≤JQ)，重新选择随机数对应的机组上生产的订单，得到ch ild1；

Step4：判断是否包含本月所要生产的所有订单，如果包含，则是可行解，写进新的种群，计数器g=g+1，否则对不合格个体进行修正；

Step5：直到种群中的个体数都变异完成后停止。

4 数据分析

本文采用MATLAB.R2017a编程实现。阶段一遗传算法参数设置如下：种群规模为100，迭代停止条件为G=200，交叉概率为0.8，变异概率为0.05；阶段二的参数设置为：种群规模为40，迭代停止条件为G=100或时间超过2s，交叉概率为0.8，变异概率为0.02。

以襄阳卷烟厂某月真实的订单情况及设备数据进行模拟，设备的柔性连接关系见表1，卷接机都可连现有的5台滤棒发射机。输入的订单见表2，共有3个规格16个牌号18个订单，07205、07218两个牌号为外购烟丝，优先使用半自动喂丝机W7供丝；此订单信息表中仅07229、07237、52213、61204需要使用滤棒发射机。15#-23#、12#、14#共11台卷接机采用早班、中班两班制组织生产，3#-11#卷接机采用早、中、晚三班制组织生产，16日～20日放假，每班次为8h，为与工作日历相匹配，设置一天的开始时间为早上8:00。再结合烟厂具体的卷包生产速率等具体信息，得到的卷包计划见表3，表中显示了分组信息与明确的链路关系、订单牌号信息；生产计划甘特图如图4所示。

表1 烟厂卷接机柔性连接关系表

时间段（09 5:49,14 23:15）内，8-10#卷接机与3#卷接机交换喂丝机，是因为订单1和订单2为外购烟丝，需使用半自动喂丝机W7供丝，订单1和订单2生产完毕再切换为原来的搭配，如图4中阴影所示；在时间段（25 14:21,29 15:57）内，3#卷接机从W7 切换为W2喂丝机供丝，与8～10#卷接机一起使用W2喂丝机生产订单10，减少了半自动喂丝机W7的使用时间，为后续可能到来的加急订单留出空间。订单14与订单15进行生产时，原本可用的喂丝机、封装机、发射机皆被订单13（牌号61204）占用，已没有可用的链路，所以这两个小订单皆由人工辅助进行生产，见表3。

图4 卷包车间生产计划甘特图

表2 烟厂某月生产订单信息表

表3 卷包作业生产计划结果表

此排产结果获得了烟厂生产调度科的认可。在调度结果中，逾期订单数为0，在当月29 日完成所有生产任务，较交货期提前2天；换牌次数较人工所排计划减少；84规格和90规格的卷接设备同时停机，封装机和发射机无中途切换，卷接机无停机情况。

利用上述实际数据进行算法测试的结果表明：（1）保证了各个牌号的产品能够按期交货；（2）符合牌号—卷接机、喂丝机—卷接机的链路关系；（3）满足设备连续生产，按照工作日历时间正常工作，不待料停机；（4）满足生产同一订单的卷接设备同时停机；（5）满足同规格的卷接设备同时停机；（6）满足换牌次数最小；（7）对链路关系进行优化。此外，进一步利用多个月的实际数据进行测试，也验证了本文所设计算法的有效性。

5 结语

卷包计划是烟厂展开有序、协调、高效生产工作的核心。本文对卷包生产进行了调研，分析了卷包排产需要满足的原则与约束，构建了以卷接机为核心的多目标优化模型，针对多种柔性连接关系，提出了两阶段遗传算法，将卷接机生产计划和链路关系优化分开，对逾期订单数、最大完成时间、换牌次数、人工喂丝进行了优化。本文的算法已成功用于卷烟生产企业，调度结果获得了烟厂调度人员的认可，取得了良好的应用效果。