基于制丝生产单元的智能调度模型研究与应用

李 凡，李 斌，卫建斌

（红云红河集团红河卷烟厂，云南 红河州 652399）

0 引言

随着工业 4.0的变革，信息化技术对现代工厂的发展产生了巨大的影响，智能工厂概念的提出，使得物联网、大数据、边缘计算、人工智能等先进技术逐步引入到工厂的管理、办公、甚至生产自动化之中，从而以技术手段实现规范企业管理、提升工作效率的目标[1]。

以卷烟行业为例，目前卷烟制造行业根据“按照订单组织生产”的特点，对卷烟生产的柔性制造[2]以及智能生产调度提出了更高的要求。卷烟制造过程分为制丝生产及卷包生产，制丝生产为典型的流程型制造，与离散工业相比，不如离散工业那样产品可以单件计数，制造过程易于数字化；制丝的生产过程涉及物理、化学反应，部分原料成分、设备状态及工艺参数难以实时获取，且生产过程是连续的，中间任一环工序出现问题，则会影响整条生产线的生产效率，从而形成了测量难、建模难、优化决策困难等问题。

因此，针对生产订单多规格、小批量的特点，结合制丝线生产能力，合理组织生产，调度订单生产顺序，从而节约生产过程成本，节约生产时间，是提高生产效率的目标。然而，目前的生产计划制定大多依靠专家进行人工调度，采用经验方法，可经验的积累需要时间，而在市场化经济的今天，时间就是金钱，制丝调度问题实际上是一个较为复杂的实际问题，需要考虑产线的生产能力、缓冲、设备情况等各种状态，对此问题，[3]提出，将生产调度问题以层次划分，细化问题规模，逐步求解，目前针对卷烟生产调度，研究人员通过提取问题特点，将其与流水线调度经典问题结合起来，徐永虎等人[4]提出了一种柔性制丝线排产算法，分析烟草排产工艺流程和约束规则设计架构模型；[5]提出了一种面向分组加工的烟草生产调度模型，以仿真模型优化排产调度设计；[6]设计出一种基于生产时间的二重有线分配启发式算法，这些算法大部分从整个生产过程入手，统一看待整条制丝线、卷包线的生产计划问题，分析粒度大部分只到大的生产单元，在实际生产过程中，关键生产单元的优化对于整条生产线的生产影响是明显的，因此基于生产单元内部的调度问题也需要进行考虑。

因此本文针对制丝烟片预处理生产单元的订单调度问题，结合实际特点构建调度模型，将现实生产状况映射到流程型流水线调度模型之中，利用模拟退火算法优化的遗传算法求解订单执行及调度顺序，再利用实际算例进行验证，为制丝预处理段的调度优化提供解决思路。

1 问题分析

近年以来，随着客户的需求逐步向中小批量、个性化改变，产品生产周期缩短，交货时间提前等问题使得传统的大批量生产模式受到了新的挑战。单元生产模式[7]作为精益生产的一种方式，目前正广泛应用于制丝生产过程中。其主要特点是产品族概念的提出，将不同品种的产品按照特点划分为产品族，针对产品族的工艺特点从而进行高效的设备布局，再按照柔性设备与单元自治的组织分工模式，从而实现生产运作的高效、快速和灵活等目标。

卷烟生产的要点在于深化分组处理，充分发挥原料使用价值，从而改善产品质量[8]，以生产单元为单位的生产能够有效地提高卷烟生产的效率。在制丝过程中，烟片预处理阶段不仅涉及到原烟的入库、流程化处理，还涉及到配叶贮叶过程，有原料的输入，也有烟片半成品的输出。根据目前卷烟生产工艺规范，主要分为备料、开箱和计量、切片、松散回潮、烟片预配、筛分和加料以及配叶贮叶共7个阶段，如图 1所示。在实际的制丝车间中，它是制丝流程的一个起点，属于关键生产单元，因此针对烟片预处理阶段的调度优化，对于整个制丝生产的效率都有一定提升。

图1 烟片预处理段工艺流程Fig.1 Process flow of pre-treatment section of cigarette

在实际生产中，由于特殊工艺需求，在生产过程中存在许多规则与约束，烟片预处理阶段的调度目标是获得成本最低的批次生产安排，在生产过程中，生产成本与生产时间密切相关，在保证产品质量的前提下，应尽量提高设备利用率，减少设备等待，从而使得总生产时间最短，受到如下几方面的约束：

（1）牌号加工优先级约束

针对生产订单的差异，不同牌号的卷烟都具有对应的叶组配方，并依照订单批次进行生产，不同牌号进行批次切换时成本不同，由高端批次向低端批次切换时，由于不需要生产线的清洁，因此成本较低；反之成本较高。

（2）设备加工能力约束

在按照工序生产时，针对一批物料，不同设备具有固定加工能力，加工时间固定。

（3）缓存约束

在工序生产过程中，一部分工序之间存在固定容量的储柜可以进行缓存，且保持FIFO（先进先出）原则。

（4）加工路径约束

对于制丝生产，不同批次具有固定的加工路径和加工设备，保持先进先出原则。

烟片预处理段具有以下特点：

（1）各个批次的原烟依次通过每一道工序，且顺序相同；

（2）不同批次的原烟加工时间已知；

（3）每台设备在每个时刻只加工一批原烟；

（4）每批原烟只在每台设备中加工一次。

由上可知，烟片预处理段的调度充分满足典型的批量受限的有限缓冲区流水车间调度问题（Flow-Shop Scheduling Problem, FSSP）特点，这是一个经典的 NP（Non-deterministic Polynomial）问题，难以直接求解。

2 基于生产单元的制丝预处理生产调度模型

2.1 模型设计

以 FSSP的角度分析烟叶预处理段生产调度过程，可将其抽象为数学描述：

在m台设备上需要加工n个订单，每个订单都有m道工序，每个订单的工序相同，且各个订单在m台设备中加工时间已知。每个设备同一时刻只能加工一个订单，则调度目标为根据条件设置合理的n个订单的加工顺序，从而使某些调度指标达到最优。

根据实际制丝生产单元提取必要属性进行抽象，从而获得生产单元模型M和订单模型N，以表示第 i道工序与 i-1道工序之间存在的缓冲区大小，表示第 i道工序的工艺制造能力；对于订单而言，s表示订单所需的不同物料种类数目，表示第 i个订单的优先级，实际表示生产订单牌号，高级的牌号优先级高于低级。

①生产单元模型M：

基于订单和生产单元的模型，设计以物料输入、仓储输出、最大流程时间、有效作业率等属性组合成的评估模型 E，检验订单调度序列是否能够更好地满足排产调度情况，决策者可以根据实际生产需要选择合适评估属性。

③评估模型E

物料输入：In

仓储库存：Out

其中，In指的是订单所需物料输入：

Out指订单生产完成后生成的半成品所需的仓储空间：

对于有效作业率ξ，其计算公式为：

2.2 算法设计

对于制丝过程烟片预处理生产单元的模型抽象如 x.x所述，求解该模型即是找到一个合理的订单加工序列 π={π(1),π(2),π(3),…,π(n)}，使得订单总生产时间最小化，节约生产成本，因此目标函数为：

流水线调度问题的核心在于如何更快更方便地找到那个相对最优解，目前并不存在一个绝对有效的算法，能够在多项式时间内求出这个最优解，经过多年研究，业界对于这类调度问题已经具有一定研究经验，现在的研究可分为精确方法以及近似方法两类。

精确方法包括线性规划[9]、分支定界方法[10]等，其目的为保证得到全局最优解，其限制在于只能用于解决较小规模的流水线调度问题，求解过程耗时较长，效率低，但能够保证解的准确性。

而近似方法是相对于精确方法无法求解的情况下，寻找相对最优解的算法，随着流水线调度问题日趋复杂，精确方法求解效率低下的情况下，近似方法能够在较少的耗时中求解能够接受的近似解，求解时间短，效率较高，如何提高近似解的准确性和求解效率是目前的重要研究方向。近似方法主要包含构造方法、局部搜索、人工智能、系统仿真[11]四类。目前较常见的为人工智能算法，针对缓冲区是否有限的问题，文献[12-15]提出了混合蝙蝠算法、微粒群算法求解流水线调度问题求解缓冲区有限的情况，文献[16]考虑了缓冲区为0，即阻塞流水车间的调度问题。

针对烟片预处理段的实际情况，我选择以模拟退火算法[17]优化的遗传算法[18]求解。遗传算法是一种基于自然选择与遗传机制的元启发式搜索算法，将问题求解的过程转换为解空间的“染色体”迭代的过程，如图2所示。具体实现步骤如下：

（1）参数编码：使用无符号二进制整数对订单任务进行编码，设置种群大小S，迭代次数En。

（2）初始群体：由于生产实际情况可知，换牌频繁则会影响生产效率，初始群体必然存在一定约束，因此选择生产量最大牌号作为初始群体之一。

（3）适应度函数：在此可将目标函数（最大完工时间）作为适应度函数的参数：

（4）遗传算子计算

选择：首先通过轮盘赌选择方法执行遗传算法的初步选择，然后将当前群体中适应度最高的个体完整地复制到下一代群体中。

交叉：设置交叉概率 θ ∈ [ 0,1]，根据交叉概率随机选择成对染色体按照单点交叉方式两两交叉。

变异：设置变异概率 η ∈ [ 0,1]，以基本位变异的方法按照变异概率随机选取变异染色体进行计算，形成新的一代种群。

（5）模拟退火优化：针对遗传算法编码占用储存空间大、容易陷入局部最优解、爬山能力差等问题，利用模拟退火算法进行优化，计算变异前后两个种群的总适应度大小 Efit1、 Efit2，若 Efit1< Efit2，则接受变异结果，确定变异后的种群为新一代种群；若 Efit1> Efit2，则考虑以概率p(dE)接受变异结果，且概率随时间而降低，概率计算方法如下：

图2 模拟退火算法优化的遗传算法求解流程Fig.2 The process of simulated annealing algorithm of genetic algorithm optimization

3 算例验证

为验证提出的调度模型能够通过模拟退火算法改进的遗传算法求出最优解，选取红河卷烟厂实际生产流程中叶片预处理段生产单元作为设计参考，算法运行环境为Windows 10, intel i7处理器，内存16G，python 2.7。

叶片预处理生产单元模型可描述为下图所示，它包括7个工序，其中松散回潮到烟片预备阶段中存在一个缓冲区，映射到实际上为一个固定容量的储柜，用于叶配工作，在此假设缓冲区仅能够存储同一批订单的物料。

假设某日制丝订单预处理段生产情况如下表所示，生产ABCD四种牌号的烟，一共10个订单，各个订单所需原烟质量如表中所示。

表1 实际订单批次信息Tab.1 Actual order batch information

表2 不同规模订单算法执行结果Tab.2 Results of algorithm in different size of orders

对于订单中的数据，设置遗传算法的初始种群规模为 100，交叉概率为 0.95，变异概率为 0.05，迭代代数为100，退火模拟算法的参数k为1，计算的迭代曲线如图3所示，计算获得结果见表2第一行，再与正常执行的调度顺序相比，其总生产时间共减少了75分钟，可以证明调度算法的优越性。

图3 迭代曲线Fig.3 Iterative curve

考虑到订单批次增长的情况，再以20、30、40、50、60为规模，模拟调度情况，获得表2中数据，可以发现，该算法能够适应订单规模的增长情况，辅助调度员获得最优订单调度方案。

4 结论

本文针对红河烟厂的实际生产情况进行研究，对烟草制丝生产流程中的关键生产单元——烟片预处理生产单元的调度排产进行研究，将其抽象成为求解流程型有限缓冲区的流水线调度问题，通过模拟退火算法优化的遗传算法求解最优解，最后通过模拟不同规模的订单调度过程，验证了经过调度后的结果更优，验证了模型的实用性。未来的研究方向在于将该抽象模型应用到不同的生产单元中，对订单调度过程进行抽象和优化。