改进灰狼算法求解多目标柔性作业车间调度问题

孙新宇

(上海理工大学机械工程学院，上海 200093)

807713550@qq.com

1 引言(Introduction)

柔性作业车间调度的概念是在1990 年BRUCKER和SCHLIE提出的，其作为经典作业车间调度问题的进一步扩展，属于一个典型的NP-hard问题，存在求解优化的困难。不同于作业车间调度，柔性作业车间调度可以使每个作业在不同的机器上进行加工，也可以在机械设备出现故障时处理问题，并满足不同加工需求的变化，更有利于提高生产效率，贴近现实具体的生产环境。按照求解目标，柔性作业车间调度问题可分为单目标和多目标，单目标一般的优化目标为最大完工时间、机器空闲时间、总流动时间等，目前研究最多的是最大完工时间。多目标是将多个目标同时考虑，选择最优情况，更符合现实生产要求。

灰狼优化算法(Grey Wolf Optimizer，GWO)是MIRJALILI等在2014 年观察模仿狼群生活和狩猎方式提出来的一种基于群体的优化搜索算法。该算法的搜索原理简单、鲁棒性较好、收敛性能较强、求解速度较快和参数较少。通过近些年的研究，其已经很好地应用在车间调度问题的求解、图像分类、参数优化等领域。

灰狼算法较多用于解决连续函数方面的问题，对于柔性作业车间问题，特别是本文对多目标的优化方面的应用还是较少。因此本文通过优化初始种群，在此基础上，与非支配排序算法结合，引入非支配排序与拥挤度，提出了一种解决多目标优化问题的思路，并通过调度算例进行有效验证。

2 问题描述(Problem description)

对柔性作业车间问题的描述如下：假设一个柔性作业车间有台加工机器和个工件，不同机器会加工多种工件，每个工件的工序数量也不一定相同，每个工序的加工需要按照一定的先后顺序进行，并且加工的时间也会各不相同。按照某些优化目标，为每道工序分配合适的加工机器，并且每台机器按照分配的任务进行顺序加工，从而实现最优化的目标安排。

对于柔性作业车间，还存在下面的假设条件：

(1)一台机器某一时刻只能加工处理一个工件；

(2)所有工件在开始的零时刻都可以被加工；

(3)同种工件的工序一定要按照次序加工，不同工件的工序之间相互独立；

(4)各个工件之间不存在加工的优先级的差别；

(5)任意工序只要开始加工，就不能中断；

(6)同一工件的同一道工序在同一时刻被加工的机器数是一。

3 模型建立(Model building)

把车间的最大完成加工时间、机器总耗能及总机器负荷作为优化目标，建立柔性车间的多目标模型。

(1)最大加工完成时间最小化

加工完成时间是每个工件的最后一道工序完成的时间，当最后一个工件的最后一步工序结束时，加工零件所用时间最长的就是最大完工时间。在调度排产中，完工时间可以体现一个车间生产效率的高低，表示为

式中，表示最大完成加工时间；表示工件序号；表示工件总数；C表示每个工件的完成加工时间。

(2)机器总耗能最小化

总耗能是空载能耗与负载能耗之和，零时刻机器开工，能耗计算公式表示为

式中，表示机器序号；表示机器总数；表示速度挡位序号； d表示机器的速度挡位； E表示单位时间内机器加工时的加工能耗；p表示工件以速度挡位在机器上的实际加工时间； x表示0或1变量，若工件在机器以速度挡进行加工则为1，否则为0；SE表示机器单位时间内的平均空载能耗；MC表示机器的完成加工时间；W表示机器的总负载。

(3)总机器负荷最小化

在不同的调度安排下，机器的总负荷也会不同，所以在不同机器上同种工序花费的时间也不同，因此最小化机器的总耗能显得很有必要，前提是最大完工时间最好一致，表示为

式中， h表示第个工件的工序总数； p表示第个工件的第道工序在机器上的加工时间； x为0或1变量，如果第个工件的第道工序在机器上加工则值为1，否则为0。

(4)上述假设条件的约束模型

式中， s为第个工件的第道工序加工开始的时间； c为第个工件的第道工序加工完成的时间；代表工序序号；表示不同于的工件序号； y为0或1变量，如果第台机器上第个工件的第道工序先于该台机器上第个工件的第道工序加工则为1，否则为0。

式(4)和式(5)表示工序加工时按照工件规定的次序；式(6)表示总的完工时间一定大于每个工件的完成加工时间；式(7)和式(8)表示一台机器某一时刻只能加工处理一个工件的工序；式(9)表示工件的工序在任意时刻有且仅有一台机器可以加工处理它；式(10)和式(11)表示车间中的任何一台机器的操作是可重复的；式(12)表示各个变量不可小于零。

4 改进的灰狼算法(Improved GWO algorithm)

4.1 基本的灰狼算法

灰狼算法的数学模型由两部分组成：包围猎物的部分和猎杀猎物的部分。包围猎物的数学公式如下：

猎杀猎物的数学模型如下：

4.2 初始化种群的改进

对于群智能优化算法来说，好的初始化种群可以加快全局收敛的速度，以及寻找更精确的解，所以改进算法的初始种群，提高寻优能力就显得很有必要。在标准灰狼算法中，种群的多样性无法保证，因为其采用随机初始化的方法来初始种群。

本文采用了LUO等提出的复数值编码的方法，初始化种群，并与工序结合，较好地提高了全局优化的策略，寻找工序中最优的分配，减少最大完工时间和机器耗能等。该方法为了提高种群的多样性，引入了复数，因为复数包含实部和虚部，可以单独分别更新，从而包含了更多的信息，进而增强了种群的多样性。

4.3 非支配排序及拥挤度

为了解决柔性作业车间的多目标问题，标准的灰狼算法对于单目标问题，个体的优劣比较容易判断，但当涉及多目标问题时，就很难寻找目标。引入非支配排序遗传算法中的非支配排序和拥挤度的概念，将每个个体按照它们的支配与非支配关系进行分层，再根据拥挤度，选出同级别中的优解，保持了种群的多样性，从而达到求解多目标问题的目标。

(1)在种群中寻找单独的个体，这类个体不受上一级个体的控制影响，把它们放入集合中。

(2)对上述集合中的每个个体，找出受它影响控制的下一级个体集合，那么因为找出了一类上一级个体，集合中个体的受上一级影响数量需要减去一类。

(3)当该个体受上一级影响的数量减去1后值为0时，存入另一个集合中。那么集合中的个体都是非支配的，第一次分级找出的这些个体也被叫作第一级非支配个体。然后重复上面的操作，由集合开始分级，不断进行下去，那么所有的个体都可以分级完成。

密度估计：对同一个前沿面的解集合按各个目标分量大小排序，计算每个解在该分量下的两侧点的距离差值，而后进行累加各个分量上的距离作为拥挤系数。

4.4 算法流程

图1 算法步骤流程图Fig.1 Flow chart of algorithm steps

步骤1：设置算法参数、种群大小及迭代次数。

步骤2：采用上文所述的复数值编码的方法初始化种群。

步骤3：解码得到加工时间、耗能和机器负荷，进行非支配排序和拥挤度计算。

步骤4：对拥挤度排序后，找出决策层的、和狼。

步骤5：更新每个灰狼个体的位置。

步骤6：计算更新后群体个体的适应度，再找出最优的三条狼。

步骤7：判断迭代次数是否满足，是则转到步骤8，否则转到步骤5。

步骤8：算法结束，输入结果。

5 实例结果与分析(Example results and analysis)

为了验证上述模型和算法在解决FJSP问题方面的有效性，本文采用了Brandimarte中的基准算例MK10，算例中的工件数为20，机器数量为10。

以最小完工时间、最小机器负荷及最小机器耗能为目标，在柔性作业车间中，通过改进的灰狼算法进行甘特图的排产安排，其中灰狼优化算法的种群大小设置为100，最大迭代次数为100。最终优化的三个目标结果图如图2、图3和图4所示；甘特图排产的结果如图5所示。

图2 最小完工时间趋势曲线Fig.2 Trend curve of the minimum completion time

图3 最小机器负荷趋势曲线Fig.3 Trend curve of the smallest machine load

图4 最小机器耗能趋势曲线Fig.4 Trend curve of the minimum machine energy consumption

根据运行结果，从图2—图4中可以看出收敛的所有零件完成加工的最小时间在510 分钟左右，最小机器负荷为2，395 kW，最小机械总能耗为6，175 kW。可以看到改进后的灰狼算法可以较快收敛到最优解，加入非支配排序和拥挤度后，该算法在解决三目标的优化问题方面是有效的。

图5 实例MK10的甘特图Fig.5 Gantt Chart of example MK10

6 结论(Conclusion)

为了研究柔性作业车间多目标调度的优化问题，本文采用改进的灰狼优化算法，用复数值编码的方式初始化种群，使用了非支配排序遗传算法中的非支配排序和拥挤度，使得改进后的灰狼算法，也可以用于解决多目标优化问题。

建立了关于完工时间、机械负荷和机械总能耗的数学模型，并用灰狼算法对模型进行验证，结果表明改进后的灰狼算法可以较快地收敛，找到多目标的最优解，说明了该算法的有效性。

本文研究的内容都是在静态调度的情况下，针对动态调度的情况没有考虑，下一步需要考虑更多的现实问题和与其他智能随机算法结合对比研究，获得更高效的算法。