面向卷烟生产调度的集成产能过滤算法与仿真技术的优化框架

沈 倩，管在林，张正敏+，王创剑，岳 磊

(1.华中科技大学 机械科学与工程学院，湖北 武汉 430074；2.武汉科技大学 机械与自动化学院，湖北 武汉 430081；3.广州大学 机械与电气工程学院，广东 广州 510006)

0 引言

卷烟生产系统属于典型的多品种大批量生产模式，效益最大化、成本最小化一直是卷烟企业追求的目标。卷烟生产过程一般由流程型制丝工艺和离散型卷包生产组成，是一种典型的混合制造模式。针对卷烟工厂建立优化模型进行生产计划与调度，不仅要考虑错综复杂的约束条件，还要满足从宏观到微观的计划调度要求，因此问题复杂且算法难度大。

目前，卷烟企业通常采用制造执行系统(Manufacturing Execution System，MES)或依靠人工经验使用简单的调度逻辑与规则进行卷烟生产调度。由于卷烟生产流程较为复杂，生产过程约束多且存在动态性与不确定性，企业现有调度方法较难得到满意的生产方案[1-4]。对此，国内外研究人员针对卷烟生产问题的建模与调度策略进行了大量研究[5]。通过分析总结现有研究发现，大多针对卷烟生产的调度研究成果未充分考虑有限产能、卷烟生产的复杂约束或卷烟整体的混合生产流程，难以应对实际生产中卷烟产线有限产能下的动态调度需求。因此，本文提出一种产能过滤算法(Capacity Filtering Algorithm，CFA)[6]与仿真技术结合的调度优化框架，通过产能过滤技术与动态仿真技术实现车间的负荷均衡与动态调度效能优化。通过生产实例显示，该框架下的瓶颈设备利用率达到97.01%，订单按时交付率达到97.44%，远超车间现行生产调度方法。

1 文献综述

近年来，国内外学者在卷烟生产调度方面进行了大量的研究与应用。很多国内卷烟厂引入了MES等生产信息系统以协助调度方案的优化与执行，例如，卞新中[7]将Rockwell Automation公司的MES产品应用于山东将军烟草集团并成功实施了高级排产；谢五峰等[8]基于SIMATIC IT软件架构展开了卷包调度研究，但该类软件并未充分考虑物料及生产能力。

针对卷烟生产调度问题，夏秀芳等[9]提出了制丝仿真计划系统解决方案；袁建华等[10]采用建模、排程和物流分析等技术针对制丝线构建数字化平台；PAN等[11]基于简化的制丝模型提出了一种计划模型和经验排产算法；张海军等[12]面向多目标优化制丝排产问题，提出了一种高级计划系统(Advanced Planning System，APS)框架，但没有对优化模型进行研究；王爱民等[13]提出了基于遍历方法的卷包作业动态调度技术，包含订单追加、移动调整和重调度；王伟玲等[1]将卷包生产抽象为多目标柔性流水调度问题进行研究。以上研究主要针对制丝生产或者卷包生产，多数没有对卷烟工厂的整体混合生产模式进行研究。

在有关卷烟生产各类约束条件的研究中，金剑等[14]基于分层递阶优化方法建立了带约束限制的卷烟多点生产任务分配模型和生产点详细排产模型，但未考虑生产连续性等约束条件；谢瑞波[15]设计了卷烟企业生产的优化排产和调度管理系统，但主要是针对总任务的产能分配问题，未涉及多种牌号的排产；陈庄等[16]将烟草生产抽象为基于连续物料流的连通网络系统，并由此建立相应的卷烟生产线优化调度模型，但其卷包线机组组合固定，无法满足资源动态组合需求。

在卷烟生产调度方法的研究层面，徐元根等[17]将制丝生产调度问题与旅行商问题(Travelling Salesman Problem, TSP)进行映射，建立了数学模型并设计了求解算法；李丹等[18]采用遗传算法对卷烟换牌排产进行了优化设计；姚丽丽等[19]对烟草排产中的工艺路径规则进行分析，构建了基于遗传算法的车间排产系统模型；沈云波[20]针对改进粒子群算法与禁忌搜索算法相结合的卷接包生产排程优化进行了研究，采用智能搜索算法对卷烟生产调度问题进行求解，但未能全面地考虑系统中的复杂约束与动态生产特性。

综上所述，当前针对烟草行业生产调度的研究，需要进一步深入考虑实际生产中的现实约束满足和实施效果保证。为此，本文重点研究考虑有限产能约束与复杂生产场景的卷烟生产调度问题，结合烟草企业的生产特点，提出一种集成CFA与仿真技术的优化方法，以实现车间的均衡负荷，提高设备利用率，为解决卷烟企业的生产计划优化问题提供参考。

2 问题描述

烟草生产行业属于连续—离散的混合生产模式，具有多个关联的生产环节和复杂约束的动态过程。如图1所示，卷烟工厂的生产流程主要包括备料、制丝、卷包、封装等工序。制丝生产线分为梗丝线与叶丝线，梗丝线主要包括烟梗回潮、润梗、切梗丝、梗丝干燥等工段，为叶丝线提供梗丝；叶丝线包括切片、加料润叶、切叶丝、掺配等工段，将梗丝按一定的比例掺配到叶丝中，加香加料之后成为成品烟丝。成品烟丝按照牌号存储在不同的贮丝柜中进行醇化，然后通过喂丝机传送到卷包车间的卷接设备。滤棒车间将原材料按一定的规格切成滤棒，并发射到卷接设备的接嘴机。卷包车间将成品烟丝和滤棒进行卷接，经过包装、封箱等工序后存入成品高架库等待发货。

如图2所示，从工艺上可将卷烟的生产流程分为制丝、滤棒和卷包3个相对独立的环节。制丝阶段中，原料依次经过各个串联的工序，生产成品烟丝；滤棒阶段生产成型滤棒并发射到卷包阶段；卷包阶段使用成品烟丝、成型滤棒和相应的辅料，通过卷接等工序生产成品烟支。3个环节均有多条不同的生产线并行生产，可以同时加工不同牌号的产品。因此，卷烟的生产流程可以看作是3阶段的并行机调度问题，且具有部分流水与备货式生产特征，后续工艺依赖前工艺的半成品。

3 集成产能过滤算法与仿真技术的优化框架

为确保卷包车间生产的连续性，需要在发布订单投放计划时，考虑车间在制品和库存量，根据产出目标逆推卷烟的整个生产过程。因此，需要通过一种有限产能算法较为精确地计算卷烟工厂每天的投入产出量，以控制库存，并保证生产目标的合理性。由于目前大多针对卷烟企业生产计划的研究都未精准地考虑相关的产线产能，导致生产目标设置不合理、库存控制不平衡等问题，因此本文引入CFA，以进行车间产线的有限产能分析。

另一方面，由于烟草加工过程中存在众多约束，如卷烟牌号与喂丝机、卷包机的对应关系，卷包机与封箱机的连接关系，贮丝柜的最小醇化时间限制等，使得卷烟的生产调度问题十分复杂。通常，使用一般追求确定性全局优化的智能算法无法在考虑众多约束的同时满足实际生产动态调度的要求。相比之下，采用基于组合规则的仿真调度模型可以模拟车间的实际运行情况，通过选择合适的动态调度策略，可达到提高车间产出与设备利用率等目标。

综上所述，针对卷烟行业的生产特点，本文提出一种集成CFA与仿真技术的优化框架(如图3)，考虑实际生产能力进行有限产能分析，满足库存平衡、产出制订合理化，实现动态调度和实际生产的最优化。该框架重点考虑了有限能力约束下的调度优化算法，实现车间的均衡负荷，适用于系统中各个生产环节的调度方案制订。系统根据主生产计划和客户需求，得到车间日产出计划作为该框架的输入，考虑在制品及车间实际生产能力使用反向CFA从最后一道工序逐级向前递推，获得车间的订单发布计划及各个阶段原辅料的投料计划。该发布计划作为仿真模型的输入，结合组合规则，获得产出结果及相关指标，如车间产出总量、设备利用率、按时完工率等。判断产出指标是否满足车间日产出计划及其他生产要求，若不满足，则修改仿真策略或优化仿真参数，重新运行仿真模型；若仍然难以满足产出要求，则修改相应的产出计划。仿真结果满足车间日产出计划后，形成订单发布计划、最佳调度策略等指导企业的生产。

3.1 产能过滤算法(CFA)

CFA是一种由无限产能负荷曲线生成有限产能负荷曲线的算法，用于对生产过程中的各个环节进行有限产能计划，调整控制输入产出。如图4所示为某处理阶段的无限产能负荷曲线ULP(t)和产能曲线CP(t)。 若ULP(t)的任何部分高于CP(t)，则必须“压低”它以满足产能约束，得到该处理阶段的有限产能负荷曲线LLP(t)，该按压操作称为产能过滤。

过滤操作根据生产特征分为前向过滤和反向过滤两种。若在向后推溢出量的同时从右向左执行操作(时间向后)，则称为反向过滤，用于确定一个阶段的有限产能负荷曲线LPj(t)来满足下一个阶段的负荷曲线LPj+1(t)。 与此相反，从左到右执行过滤操作称为前向过滤。柔性流水作业车间是根据生产目标倒推生产需求，因此需要执行反向过滤过程，算法流程如图5所示。

步骤1构造工序n的无限产能负荷曲线和初始产能曲线。

初始时，n表示最后一道工序，根据产出计划中不同订单的数量和交货期，生成不同产品的末工序无限产能负荷曲线。初始产能曲线是在考虑预防性维护和其他干扰之后得到的设备产能。若不是末道工序，则无限产能负荷曲线根据前一道工序获得。

步骤2减去工序n的在制品库存和工序n+1的缓存库存。

在计划开始时，系统中已存在部分产品在生产，因此需要减去这部分负荷，如图6所示。对于末道工序，只需减去在制品库存Wn；而对于其他工序，应减去后道工序的缓冲区库存Bn+1和在制品库存Wn。

步骤3进行产能过滤，生成工序n的有限产能负荷曲线LLP(t)。

产能过滤时存在产能不足和产能过剩两种情况，产能不足时的详细过滤操作如图7所示。无限产能负荷曲线ULP(t)由若干LP=(RL,QL,SL,EL)片段组成，其中：RL、QL分别表示LP片段的负荷率和负荷量；SL、EL分别表示LP片段的开始时间和结束时间。同理，有限产能曲线CP(t)由若干CP=(RC,SC,EC)片段组成，其中：RC表示CP片段的产能率；SC、EC表示CP片段的开始时间和结束时间。产能过滤时，比较LP段与对应的CP段，二者的结束时间应相同，因此可能会在LP段的结束时间对CP段进行分割。

类型A-1中，在CP段的开始时间，将LP段分为L1和L2，进行如下操作：①将L2减小到C的大小；②将L2的溢出量增加到L1上；在类型A-2中，L被“压低”到C的高度，导致其开始时间向左移动。

产能过剩情况类似于产能不足情况的过滤过程。

当针对多种产品进行产能过滤时，按照优先级的高低，依次考虑不同的产品类型，即先对优先级更高的产品进行产能过滤，再依据剩余产能曲线对优先级低的产品进行过滤。

步骤4判断当前工序是否为首工序。

若为首工序，则根据其有限产能负荷曲线生成订单发布计划，结束算法；否则转步骤5。

步骤5负荷曲线左移。

柔性流水线由多个被缓冲区分隔的工序组成。为了得到工序n-1的无限产能负荷曲线，需将工序n的有限产能负荷曲线向左平移工序n-1的通过时间Tn的距离，左移过程如图6b所示。因此，用于获得工序n处的无限产能负荷曲线的过程可以表示为：ULPn(t)=LPn+1(t+Tn)-(Bn+1+Wn)。

令n=n-1，继续对前一道工序进行产能过滤。

3.2 基于仿真的优化模型

基于仿真的优化模型以CFA得到的订单发布计划作为输入，模拟车间的实际运行情况，判断车间的总产出是否满足要求。运行时可以直观地展示设备状态等信息，是在虚拟环境中对排产规则及算法进行预验的重要工具。

考虑生产线中各对象物理特征及对象间的逻辑与约束关系，根据车间布局、设备的主要技术参数以及物流流程建立如图8所示的仿真模型。仿真初始阶段，需初始化缓存区和处于设备加工过程中的在制品，与订单投放计划一起作为输入。通过选取不同的调度策略进行对比分析，如先进先出策略(First In First Out, FIFO)，最少切换时间策略(Minimum Setup Time, MST)，最早交货期策略(Earliest Due Date, EDD)，最短加工时间策略(Shortest Processing Time, SPT)等，可为进一步的决策与优化提供依据。仿真结果优劣可通过分析关键性能指标评价，典型性能评价指标包括瓶颈设备利用率、总换牌次数、车间总产出和订单按时交付率等。

4 实例应用

4.1 问题实例

为验证集成CFA与仿真技术的优化框架在柔性作业车间中的有效性，本文利用某卷烟工厂1周的实际生产数据进行实例研究。该卷烟工厂制丝车间有两条制丝线，生产能力分别为5 000 kg/h和4 800 kg/h，烟丝在贮丝柜中的醇化时间应大于4 h。滤棒车间中有滤棒成型机和滤棒发射机各14台，生产能力均为195千支/h。卷包车间包含24台生产能力为9.6箱/h的卷包机，6台生产能力为54箱/h的封箱机。该工厂4月1日～4月7日的产出计划如表1所示，需生产5种牌号的卷烟，不同牌号之间的切换时间为30 min。

为保证卷包车间加工的连续性，需要提前1天根据卷包需求制定制丝车间的生产计划，卷烟工厂各个工序3月31日的在制品分布数据如表2所示。

表1 卷烟车间产出计划表 箱

表2 卷烟车间在制品分布表

4.2 实验结果与分析

4.2.1 有限CFA算法比较分析

对卷烟工厂1周的产出计划应用3.1节中的有限CFA，求解获得该工厂叶丝线的叶片投放计划(表3)、梗丝线的烟梗投放计划(表4)和滤棒车间的滤棒投放计划(表5)。

表3 叶片投放计划表 kg

表4 烟梗投放计划表 kg

表5 滤棒投放计划表 千支

如图9所示为依据卷烟实际生产环境与工艺流程采用FlexSim软件构建的仿真调度模型。分别将使用有限CFA算法和未使用有限CFA算法的订单投放计划作为输入，对比分析两者在先进先出策略FIFO、最少切换时间策略MST、最早交货期策略EDD、最短加工时间策略SPT 4种基本调度策略下的性能。

使用有限CFA算法与未使用有限CFA算法的性能对比情况如表6所示，分析可知：

(1)未使用有限CFA算法的车间总体产出量均值为38 107箱，有限CFA算法下达到40 234箱，使车间总产出提高了5.58%；

(2)未使用有限CFA算法瓶颈设备利用率均值为93.16%，使用有限CFA算法则为95.58%；

(3)有限CFA算法将订单按时交付率均值从90.30%提高到了96.67%。在4种基本调度策略下，使用有限CFA算法的性能明显优于未使用有限CFA算法的调度方法。

表6 有限CFA算法性能比较表

4.2.2 调度策略比较分析

将表3～表5中3条产线的订单投放计划作为输入，选择先进先出策略FIFO、最少切换时间策略MST、最早交货期策略EDD、最短加工时间策略SPT等基本策略及EDD-MST策略和EDD-SPT策略等组合策略进行动态调度策略效能研究。

在仿真实验中，通过比较不同调度规则策略下的车间总体产出量、瓶颈工序流量、瓶颈设备利用率、总换牌次数及订单按时交付率等关键指标评价策略优劣。

(1)车间总体产出量

通过统计仿真模型3月31日～4月7日所有牌号的产出得到车间总体产出量，各个策略的表现情况，如图10所示。MST策略下车间总体产出量远高于其他策略，而将MST作为二级策略的EDD-MST组合策略相比于其他策略也具有优势。因此，可以通过减少设备切换时间来提高车间总体产出。

(2)瓶颈工序流量

瓶颈工序流量是指瓶颈设备每日加工完成的产品数量，不同策略下车间的瓶颈工序流量如图11所示。MST策略和EDD-MST组合策略下，瓶颈工序流量最大，与图10所示结果保持一致，可知减少设备切换时间可以有效地提高瓶颈设备的产出，从而提高车间总体产能。

(3)瓶颈设备利用率

统计瓶颈设备的利用率可以反映工厂是否保持连续运作，根据卷烟工厂的实际情况可知，卷接机组是整个工厂的瓶颈设备，这也与仿真的结果相符。由图12和表7可知，MST策略下瓶颈设备的利用率最高，达到了97.01%，其他策略下的瓶颈设备利用率均在95%左右。

表7 不同策略下瓶颈设备利用率 %

(4)总换牌次数

减少设备的换牌次数，可以提高设备利用率从而最大化车间的产出。由表8可知，MST策略下总换牌次数最小，较其他策略下的平均换牌次数下降45.1%。

表8 不同策略下总换牌次数

(5)订单按时交付率

卷烟工厂需要根据产出计划交付不同种类的卷烟，对每种牌号的卷烟计算每天的交付率，取平均值作为该牌号统计期内的订单按时交付率。如图13所示，本文所使用的FIFO、MST等6种策略下订单的按时交付率均高于95%，这表明使用有限CFA已经较好地均衡了车间的负荷，使车间在不同的调度策略下都能达到较高的按时交付率。其中MST策略、EDD策略和组合策略的交付率均在97%以上，效果较好。

综上所述，MST策略在车间总体产出、设备利用率和订单按时交付率等方面都有较大的优势。EDD策略下按时交付率表现良好，但总换牌次数较多且车间总体产出较低，而EDD-MST组合策略有效地改善了EDD策略的这一缺陷，在设备利用率和车间总体产能方面也表现较好。

如表9所示为集成CFA与仿真技术的优化框架与卷烟厂现行调度方法的对比情况，目前管理人员使用车间发布的未充分考虑有限产能的日产出计划，使用基于人工经验的排产规则进行动态调度。通过表9中的对比结果可知(以MST策略为例)：

(1)卷烟工厂实际总产出为35 877箱卷烟，基于仿真的优化框架下车间总产出达到40 572箱，使车间总产出提高13.09%；

(2)该优化框架将瓶颈设备利用率从实际的89.77%提高到了97.01%，减少了产能浪费；

(3)该框架下，车间的总换牌次数为42次，比现行调度方法的换牌次数(91)减少了53.85%；

(4)基于仿真的优化框架中，工厂的订单按时交付率为97.44%，比现行调度方法提高了10.08%，优化效果显著。

表9 集成CFA与仿真技术的优化框架性能对比

5 结束语

烟草生产行业属于连续—离散的混合生产模式，其生产调度问题较为复杂，为优化卷烟工厂生产调度，本文提出一种集成产能过滤算法与仿真技术的优化方法。该方法首次引入了CFA对卷烟整体生产流程进行有限产能分析，并得到各类资源有限产能下的最佳产出计划。为了保证动态制造系统中生产调度方案与实际生产过程的精准度，本文进一步建立了基于组合规则的仿真调度模型，通过实验分析得到最优动态调度规则，使车间负荷平衡，产出制订合理化。本文将某卷烟厂的实际生产数据作为实际案例进行实验，并与工厂的现行调度方法进行对比。实验结果显示，集成CFA与仿真技术的优化的方法可以有效减少换牌次数，提升设备利用率，达到较高的订单按时交付率。

本文主要对烟草生产过程中的订单发布计划和调度策略进行了研究，未来可根据不同业务需求和场景特点，对产品分批规则、设备成组和工艺路径规划等方面继续进行探索。