基于NSGA-II算法的柔性流水车间优化调度模型的构建与应用

张欢欢 李继庚 洪蒙纳 满 奕

（华南理工大学制浆造纸工程重点实验室，广东广州，510640）

车间调度问题可分为单机调度问题、流水车间调度问题以及作业车间调度问题［1］。在工业生产领域中，流水车间调度问题是一个通用的问题模型［2］。柔性流水车间与实际生产的过程最为接近，因此对其进行研究具有重要意义。柔性流水车间的优化调度问题中，多以求解单目标问题为主，大部分目标为最小化最大完工时间［3-5］等。然而在实际生产中，生产调度人员考虑更多的是多个目标，一般情况下，这些目标之间往往互相冲突。

由于调度问题的复杂性，目前还没有一种通用的方法可适用于各种类型的调度问题［6］。现有的求解方法大致可以归纳为以下3种：传统的运筹学方法、启发式规则方法以及智能优化算法。传统的运筹学方法一般只适用于小规模调度问题。启发式规则方法是通过设计好一定的规则，然后将其应用到调度过程中，从而产生相应的生产调度方案。其具有简单、易实现的特点，但在求解大规模调度问题时效率较低且无法实现多个目标的同时优化。而智能优化算法求解过程一般是先随机生成多个调度方案，然后通过所需要优化的目标函数以及约束条件逐渐对生成的解进行迭代优化。因此，智能优化算法对所求问题的依赖程度不高，可以应用于解决各类优化问题［7-8］。其中，快速非支配遗传算法（NSGA-II）非常适合处理存在多个相互冲突目标、搜索空间规模大且复杂度高的优化问题，NSGA-II 已成为近几年最受欢迎的多目标进化算法之一［9］。

生活用纸企业的生产调度问题可以简化为一种特殊的两阶段柔性流水车间调度问题。然而，不同于普通的两阶段柔性流水车间，生活用纸企业的特殊性体现在，前后两段加工过程具有一定依赖性，但后加工无需等待前加工完全完成生产任务后再开始加工［10］。这导致了传统的两阶段柔性流水车间模型不适用于生活用纸企业的生产调度问题。由于不同产品在生产过程中，造纸阶段和包装阶段均存在多个设备或多条生产线可供选择，因此通过优化排产能够实现缩短完工时间、减少切换次数等目标。对生活用纸企业而言，由于其产品具有快速消费品的特点，产品种类规格繁多［10］，受市场影响较大，生产计划变动频繁，产品切换不仅使其生产过程能耗上升、物耗加大，也为需要稳定生产的造纸阶段带来了巨大的挑战［11］。造纸生产过程的能源消耗量约占单位产品总能耗的15%～20%［12］。因此，优化生产调度以实现机器利用率最高、降低生产总能耗，对生活用纸企业极为重要［13］。目前，生活用纸企业更多是依靠排产人员的经验制作排产任务单，排产效率低下。

为实现高效优化排产，降低生产成本、提升生产效率，本研究以生活用纸企业为研究对象，设计了一个具有机器约束、运输约束、切换约束、交货期约束的柔性流水车间作业调度模型。该模型在考虑优化最大完工时间的同时，通过安排合理的生产调度优化生产成本。为促进这一问题的解决，本研究将NSGA-II算法用于求解建立的生产调度模型，并通过一家生活用纸企业的实际生产案例验证模型的可行性。

1 两阶段柔性流水车间调度建模

1.1 两阶段柔性流水车间调度问题描述

两阶段柔性流水车间调度问题的特点如下：n个工件要进行2个阶段的加工，每个加工阶段有m个并行机。在每个加工阶段至少有2 个或2 个以上的并行机器可供使用。对于生活用纸生产企业而言，要求满足以下约束条件：①所有任务都必须先在第一阶段（前加工）加工，然后再到第二阶段（后加工）加工；②每个任务在每个阶段只能选择该阶段的1台设备或1条生产线进行加工；③每台设备或每条生产线在任意时刻只能加工1个任务；④每个任务在不同设备或生产线的加工时间，可能相同，也可能不同；⑤第一阶段和第二阶段之间存在一个缓冲时间。本研究为每个加工任务选择机器或生产线，确定每台设备或每条生产线上加工的任务以及任务的加工顺序，优化目标是成本和最大完工时间最小化。

1.2 参数定义

为方便模型的建立，列出模型的相关参数，如表1所示。其中第一阶段表示造纸阶段，第二阶段表示包装阶段。

1.3 成本分析

本研究的成本主要包括加工成本、运输成本、切换成本以及拖期成本。

（1）加工成本（PC）为所有设备或生产线对任务进行加工过程中产生的能源消耗，主要指进行生产加工时各设备或生产线的电力或蒸汽消耗。

（2）运输成本（TC）为将造纸阶段生产出来的原纸运送到包装阶段进行加工过程中产生的成本，主要是指小车、吊车等运输工具执行运输功能时产生的能耗，以用电成本度量。

（3）切换成本（SC）为当前一个加工任务与后一个加工任务的产品类型不一致时，设备重新调参数过程中产生的电力费用。

表1 模型相关参数表

（4）拖期成本（DC）为当任务的完工时间比交货期晚时，所需要额外支付的违约金费用。

（5）总成本（Cost）为加工成本、运输成本、切换成本以及拖期成本之和。

1.4 以成本和最大完工时间最小化为目标的生产调度模型

本研究将成本最小化作为车间调度的优化目标之一，同时将任务的最大完工时间作为另一个优化目标，从而不仅实现成本的优化，也进一步实现能效优化。具体的生产调度模型如下所示。

目标函数为：

其中，式（6）表示目标函数。式（7）表示任务i在第一阶段只能被其中任意一台机器加工，并且必须加工1次。式（8）表示任务i在第二阶段只能被其中任意一台机器加工，并且必须加工1 次。式（9）表示一台机器j只能加工一个任务i。式（10）表示任务i的完工时间。式（11）表示在2个阶段之间必须存在一个时间间隔，这个时间间隔与任务量大小、第一与第二阶段机器的加工速度有关。

2 模型的求解与验证

2.1 NSGA-II算法

NSGA-II 算法是Deb 在非支配排序遗传算法的基础上提出的［14］。它非常适合用于处理搜索空间规模大且复杂度高的多目标优化问题。本研究有2个目标函数，属于多目标优化问题。NSGA-II 混算法的流程如图1所示，其基本过程可以简述如下：首先，需要对数据进行预处理并导入到MATLAB中，计算出模型所需要的基础数据；其次，设置算法参数、对种群进行初始化并计算适应度值；最后，执行选择操作、交叉操作以及变异操作，并将结果保存输出。

2.2 数据来源和模型参数设置

采集广东省某生活用纸企业历史生产计划表中的178个任务数据，其中任务类型有20种。该生活用纸企业前加工阶段有6 条生产线，后加工阶段有7 条生产线。为了最小化加工成本、运输成本、切换成本、延期成本，实现快速排产和满足客户对产品的时间需求，需要对任务的最大完工时间、切换次数以及成本进行优化。

任务加工时间根据任务量大小以及机器的实际运行速度计算得到，每条生产线的速度范围如表2 所示。本研究中，机器设置时间均采用在实际范围内随机产生的方式，切换时间服从［10 min，60 min］均匀分布。每条生产线的单位时间切换成本如表3 所示。运输成本与生产线的距离有关，单位产品的运输成本如表4 所示。表4 中的数字为原纸的单位运输成本，如（1#，1#，4）表示1 t原纸从造纸阶段的1号生产线运送到包装阶段的1号生产线的单位运输成本为4 元。延期成本由延期时间与延期惩罚因子βi计算得到，延期时间和任务的完工时间以及交货时间相关。对于延期惩罚因子βi，令延期惩罚因子βi在［0.002，0.006］ 之间任取一个数值［15］。

表2 每条生产线的速度范围

图1 NSGA-II算法流程图

表3 每条生产线的单位时间切换成本

表4 单位产品运输成本 元/t

NSGA-II 的参数设置如下：种群大小为100，交叉概率为0.9，变异概率为0.1，NSGA-II的最大迭代次数为50。此外，本研究中采用的电单价为0.7元/kWh。

2.3 结果与分析

图2和图3是运行1次NSGA-II得到的解的最大完工时间迭代图和生产成本迭代图。从图2 和图3 可以看到，NSGA-II 寻找最优解的能力较优，且算法的收敛速度快。图4为NSGA-II运行7次解的二维散点图。从图4 可以看到，NSGA-II 求得的解分布均匀，即解的均匀性良好。

图2 NSGA-II进化50次的最大完工时间迭代图

图3 NSGA-II进化50次的生产成本迭代图

图4 NSGA-II运行7次解的二维散点图

本研究对运行2次获得的解求取平均值，结果如表5所示。从表5可以得到，NSGA-II求得的调度方案的最大完工时间比人工排产方案缩短了1683 min，总生产成本比人工排产方案降低了226557元。表6展示了由NSGA-II和人工排产方案得到的加工成本、切换成本、运输成本以及延期成本。从表6可以看到，与人工排产方案相比，模型NSGA-II求得的排产方案中加工成本以及延期成本明显减少。因此，NSGA-II 求得的排产方案明显优于人工排产方案。也进一步说明了，本研究使用的NSGA-II 算法的有效性。NSGA-II解优于人工排产方案的占比图如图5 所示。从图5 可以得到，与人工排产方案相比，NSGA-II 得到的排产结果缩短了约6.5%的最大完工时间，降低了约4.7%的总生产成本。

表5 NSGA-II和人工排产求得的解

表6 NSGA-II和人工排产得到的加工、切换、运输以及延期成本表

图5 NSGA-II解优于人工排产方案的占比图

数据的准确性会直接影响排产结果。因而在实际应用中，可以借助企业已有的一些系统（ERP、MES等）来获取更加准确及时的排产基础数据信息。例如，前加工和后加工阶段设备的运行速度不是一成不变的，因而每次调用排产模型时，设备速度的取值就可以采用从MES系统中获取的当前值，以便于更加准确地计算出生产任务的最大完工时间，从而提高排产模型的准确性与实用性。

3 结 论

本研究对生活用纸企业的高效优化排产问题进行了描述，建立了以生产成本和最大完工时间最小化为优化目标的两阶段柔性流水车间调度优化模型。用快速非支配遗传算法（NSGA-II）求解出最优生产计划方案。该模型可应用于不同设备数量和设备规格的生活用纸企业，可灵活调整订单数量，设备功率、速度以及数量等，更符合生活用纸企业生产过程中的实际需求。通过该模型求得的排产方案能明显地缩短任务的最大完工时间，节省生产成本和人力资源，为企业带来了明显的效益。此外，该模型的工业实现还需要包括与其他系统的接口、数据库设计，也需要完善如数据的集成、图形化用户界面、报表集成等功能。