彭来湖，万璐璐，李建强，袁嫣红，王伟华

(1.浙江理工大学，浙江 杭州 310000；2.浙江理工大学龙港研究院，浙江 温州 325000；3.浙江大学，浙江 杭州 310000)

1 引言(Introduction)

随着我国经济的发展，印刷包装行业的社会需求日益增加，其对包装、印刷技术等方面的需求越来越大[1]。大部分印刷包装企业主要以“按需生产，零剩余产品”为目标制订合理高效的生产计划，从而提高生产效率和车间设备利用率。

近年来，研究车间动态调度的文献逐渐增多[2-4]。匡鹏等[5]提出了一种将动态柔性作业车间调度问题中动态时间预测与遗传模拟退火算法相结合的优化调度方法。刘微等[6]针对动态作业车间中的机器故障、取消订单、增加订单和加急订单的动态调度问题，以最短加工时间为优化目标，提出了一种混合灰狼算法的动态作业车间调度技术，但是未考虑机器负荷和机器总能耗情况。张祥等[7]提出了一种考虑最大完工时间、机器负荷和机器总能耗等性能指标更加合理情况下的粒子群遗传算法。

印刷包装包括原材料供应、切纸、设计、制版、印刷、烫金、盖光、压痕、装订、打包、托运等多道工序分工协作，是典型的长流程型生产工艺。在生产过程中存在设备故障、紧急插单、交货期变更、物料短缺等不确定因素，目前针对印刷包装车间动态问题进行研究的文献较少。

结合印刷包装车间生产实际需求，综合考虑机器故障和紧急订单对正常生产的影响，本文设计了最大完工时间、机器负荷、机器总能耗为目标函数的多目标车间动态调度优化模型，并提出了一种改进灰狼算法，以解决车间调度过程涉及大量人为主观判断而导致机器总能耗、订单最大完工时间等无法保证的问题。

2 问题描述及建模(Problem description and modeling)

2.1 问题描述

表1 参数含义表Tab.1 Parameter meaning table

(续表)

2.2 问题建模

2.2.1 目标函数

为应对印刷包装车间调度的需要，实现各个需求间的相互平衡，该印刷包装车间调度模型设置了三个评价目标。

(1)最大完工时间最小化。最大完工时间指订单的最后一道工序完成时间，最大完工时间(f1)可以宏观反映车间生产状况和车间的生产效率，如公式(1)所示：

(2)机器负荷平衡。机器负荷与机器利用率成反比，若要提高机器的利用率，则需使机器的负荷尽量小且平衡，如公式(2)所示：

(3)机器总能耗低。合理的调度方案不仅要考虑最大完工时间，还要综合考虑车间机器总能耗。在最大完工时间一样的情况下，合理选择机器，使机器总能耗最低，如公式(3)所示：

2.2.2 约束条件

印刷包装车间调度问题的约束条件如下。

(1)同一时刻、同一台机器只能加工一个工件，同一时刻、同一工件只能在同一机器上加工。

(2)不同订单的不同工序之间不存在顺序约束，但同一订单的不同工序存在顺序约束，并且不同订单的同一工序之间不存在优先级约束。

(3)每台机器和每个工件具有相同的优先级，工件一旦开始加工，除非机器发生故障，否则不能中断加工过程。

(4)不同工序的准备时间可忽略不计。

3 改进灰狼算法设计(Design of improved Grey Wolf algorithm)

MIRJALILI等[8]提出了灰狼算法，它是由灰狼群体捕食机制演化而来的元启发式算法。与其他智能算法相比，该算法设计简单，并且具有设置初始参数少、求解精度高等优点，受到了学者的广泛关注[9-11]，广泛地应用于车间调度等领域。与此同时，该算法存在种群多样性差、后期收敛速度慢、易陷入局部最优的缺点。因此，可以采用混合策略方法初始化、NSGAII方法更新决策层个体位置、局部搜索及精英反向学习策略的方法改进灰狼算法，以提高算法的收敛性与分布性。

3.1 编码与解码机制

本文采用一种数字编码的方法求解具有机器故障和紧急订单的印刷包装车间调度问题。编码包含两个部分：机器选择和工序排序。

(1)机器选择：每个基因都用一个数字表示当前的工序在可用机器中选择的顺序号，每个数字根据工序的加工顺序依次排列(图1)。

图1 机器选择编码规则Fig.1 Coding rules of machine selection

(2)工序排序：每个基因由订单编号编码。订单号出现的次数(工单J有n道工序)表示订单与工序之间的连续处理顺序，即从左到右编译染色体，如J1表示订单1，O11表示订单1的第1 道工序(图2)。

图2 工序排序编码规则Fig.2 Coding rules of process sequencing

依据机器选择和工序排序的编码机制转换出工序的加工时间，通过每台机器的生产状况及对应的加工时间计算出对应机器负荷和最大完工时间。

3.2 混合策略的种群初始化

为了保证初始种群分布均匀且保存种群的多样性，使用Logistic混沌与均匀分布相结合的混合策略对种群进行初始化。Logistic序列具有全局遍历性强的优点，其方程如下：

其中，k为迭代的次数，ak是第k个混沌数。

针对机器选择和工序排序进行种群初始化。具体步骤如下。

(1)机器选择：S为车间可用机器，统计每台机器当月工作时间，采用均匀分配原则，若某台机器当月工作时间超过平均工作时间，则优先考虑使用其他机器，保证机器的负荷均衡。随机生成一组数据M ij(Mij∈ [0,1])，根据Logistic方程得到具有混沌序列特性的Mij作为机器选择的初始方案。

图3 工序排序Fig.3 Process sequencing

3.3 策层个体位置更新机制

针对多目标问题，灰狼优化算法由于多次迭代而难以判断个体优劣。为解决这一问题，采用非支配排序遗传算法(Non-dominated Sorted Genetic Algorithm-II，NSGAII)的非支配排序及拥挤度方法，将每个个体按照它们的支配与非支配关系进行再分层，提出了拥挤度与拥挤度比较算子，按照拥挤度大小对种群进行排序，并在快速排序后挑选出三组最优解集分别为α狼、β狼、δ狼，重复上述，对种群进行更新，从而确定新的三组最优解集。

3.4 局部搜索

ω狼是等级最低的阶层，需要依赖α狼、β狼、δ狼的信息进行更新，多次运行后会导致种群的多样性下降，出现早熟收敛现象，因此在算法中融入局部搜索算法对决策层个体进行扰动，设计了以下两种领域结构。

(1)机器选择：随机选取一个订单，其对应每道工序可选择的机器为多台，任意选取一台不同的机器代替原来的机器。

(2)工序排序：随机选取两个不同订单的工序，将其位置互换。

3.5 精英反向学习策略

本文使用反向学习策略提高算法搜索性能和收敛速度。α狼、β狼和δ狼作为狼群中的精英群体，对其进行反向求解，从中发现潜在的精英个体用于更新父代种群。某一解Di在某个n维空间内，D'为反向解，数学模型如下：

其中，Di∈(ai,bi)，ai= min(Di)，bi= max(Di)，ai和bi为动态边界，反向学习策略解决了固定边界难以保存搜索经验的问题，使精英反向解能够在有限的空间中进行搜索且不易陷于局部最优。

3.6 算法流程

改进灰狼算法(IGWO)算法求解流程如图4所示。

图4 算法流程图Fig.4 Algorithm flow chart

步骤1：采用混合策略方法将种群初始化，设置当前迭代次数k=0和最大迭代次数为kmax。

步骤2：寻找最优解，采用NSGAII方法进行非支配排序和拥挤度的计算，选取三个最优解集分别为α狼、β狼、δ狼。

步骤3：对α狼、β狼、δ狼进行局部搜索，根据适应度值大小及狼群公式更新个体位置信息。

步骤4：采用精英反向学习策略，选取前N个最优灰狼个体作为下一代种群。

步骤5：判断是否满足终止条件，若满足，则输出所有非支配解，若不满足，则执行步骤2。

4 实例验证与分析(Case verification and analysis)

4.1 案例背景

本文选择某软包制造企业的印刷包装车间对IGWO进行应用验证。车间设备信息详见表2，车间订单信息详见表3。

表2 车间设备信息(节选)Tab.2 Workshop equipment information (excerpt)

表3 车间订单信息(节选)Tab.3 Workshop order information (excerpt)

4.2 案例验证

根据企业的实际需求，三个目标函数所占权重比为最大完工时间f1＞机器负荷f2＞机器总能耗f3。本文采用AHP(层次分析法)确定最大完工时间、机器负荷、机器总能耗的权重为w= (0.563,0.297,0.14)T。初始种群规模为200，最大迭代次数取100。

4.2.1 初始调度方案

根据生产车间设备信息和订单信息，基于改进灰狼算法的动态调度技术求解得到初始调度方案的甘特图(图5)。

图5 初始调度方案甘特图Fig.5 Gantt chart of initial scheduling scheme

4.2.2 机器故障下的调度方案

在10，000 s时，机器M5发生故障，维修时间为18，720 s。机器发生故障时，各订单的加工状态详见表4。

表4 机器故障发生时的各订单加工状态Tab.4 Processing status of each order when machine failure occurs

采用两种调度方案：(1)方案1为右移调度，在初始调度方案的基础上，不改变其他工序的调度顺序，将故障机器M8上等待加工的工序往右移18，720 s，如图6(a)所示；(2)方案2为基于改进灰狼算法的动态调度技术求解得到动态调度方案的甘特图，如图6(b)所示。

图6 机器故障重调度方案Fig.6 Machine fault rescheduling scheme

对比两种调度方案，方案2 的最大完工时间减少了2.74%，机器总能耗减少了3.42%，机器负荷减少了1.20%。方案1中的订单工序不变，机器M5发生故障后与其相关联的工序往后移，导致机器M6、M7、M8、M9、M10、M11、M12、M13的空闲等待时间和机器总能耗都增加。

4.2.3 紧急订单下的调度方案

在初始调度方案执行到80，000 s时，车间收到加工件数量为5，000 件的紧急订单，需在3 天内完成入库，收到紧急订单时各工件加工状态详见表5。

表5 收到紧急订单时的各订单加工状态Tab.5 The processing status of each order when an urgent order is received

分别采用两种调度方案：(1)方案1为不改变其他工序的调度顺序，对空闲机器进行工序分配，如图7(a)所示；(2)方案2为基于改进灰狼算法的动态调度技术求解得到动态调度方案的甘特图，如图7(b)所示。

图7 紧急订单重调度方案Fig.7 Emergency order rescheduling scheme

对比两种调度方案，虽然最大完工时间相等，但方案2中紧急订单的完工时间为19.1×104s，方案1中紧急订单的完工时间为19.5×104s，方案2比方案1提前2.05%完成订单。方案2的机器总能耗减少了3.04%，机器负荷减少了1.24%，原因是采用改进的灰狼算法对车间未开工的工序进行重调度，选择负荷和空载小的机器进行加工，并且缩短了机器的空闲时间；方案1没有考虑其他工序的影响，只是在初始调度的基础上进行调度。

4.3 与其他算法仿真对比

为了验证改进灰狼算法的有效性，与NSGAII算法进行比较，分别取机器数量为20、30、40 台生成a、b、c三组订单数量不同的案例，对每个案例独立运行20 次，并计算和统计相关评价指标的最小值(min)、最大值(max)和平均值(avg)，测试算法性能的参数反世代距离(IIGD)、非支配解个数(NNDS)、非支配解比例(RNDS)，不同实例情况下，IGWO和NSGAII在IIGD、NNDS、RNDS三个方面的对比结果分别如表6、表7、表8所示。

表6 I IGD结果比较Tab.6 Comparison of I IGD results

表7 N NDS结果比较Tab.7 Comparison of N NDS results

表8 RN DS结果比较Tab.8 Comparison of R NDS results

(续表)

由表6可知，IGWO算法得到IIGD指标的min、max和avg的平均值分别为0.02、0.27、0.13，远小于NSGAII算法得到的结果0.64、1.43、1.00。由此可得，IGWO算法的收敛性和分布性优于NSGAII算法。

由表7可知，IGWO算法得到NNDS指标的min、max和avg的平均值分别为19.00、23.33、21.48，高于NSGAII算法得到的结果8.89、12.33、11.20，从上述实例结果可知，IGWO算法求得NNDS数量都多于NSGAII算法。

由表8可知，IGWO算法得到RNDS指标的min、max和avg的平均值分别为1.00、1.00、1.00，优于NSGAII算法得到的结果0.51、0.62、0.54。

最大完工时间、机器负荷、机器总能耗的权重为w= (0.563,0.297,0.14)T，得出三种调度事件中的最优解(表9)，由表9可知，NSGAII在机器总能耗控制上具有优势，但考虑到IGWO能节省最大完工时间，因此仍具有较大优势。

表9 实验结果Tab.9 Experimental results

5 结论(Conclusion)

本文针对机器故障和紧急订单两种动态事件对印刷包装车间动态调度产生干扰的问题，建立了以最大完工时间、机器负荷和机器总能耗为目标的印刷包装车间动态调度多目标优化模型，在此基础上提出了解决该问题的一种改进灰狼算法。首先，采用Logistic混沌与均匀分布相结合的混合策略初始化种群，从而提高初始化种群的多样性。为了确定最优解集，利用非支配排序遗传算法的非支配排序及拥挤度方法，按照拥挤度大小对种群进行排序。为了避免算法出现早熟收敛现象，采用两种邻域结构对猎物进行邻域搜索，并且利用精英反向学习策略优化算法搜索性能及收敛速度。其次，通过案例验证和对比不同方案，证明动态事件发生时，所提方法能够有效降低最大完工时间、机器负荷和机器总能耗。