基于粒子群和蚁群混合算法的柔性车间调度算法

王昱钦

（江苏自动化研究所信息技术研究部，江苏连云港 222006）

随着经济和社会的发展，工厂化生产已经越来越普及。在流水线的生产过程中，合理安排工件的订单和使用的机器可以使整个生产过程的时间和机器功率消耗降到最低，这也被称为作业车间调度或作业车间问题（Job-shop Scheduling Problem,JSP）[1]。由于JSP 的优化经常涉及许多复杂的约束条件，并且这些条件往往是非线性的，因此传统的线性规划方法难以解决[2]。进化算法由于其稳健性和强大的适应性，其已经在众多研究中显示出处理复杂约束条件时的有效性。最近，关于JSP 的研究不仅在模型本身上得到了发展，而且在求解方法上取得了较大进步。柔性工作车间调度问题（Flexible Job-shop Scheduling Problem,FJSP）是现代制造系统中经典工作车间调度问题的一个实际有用的扩展，它允许一个操作由给定的任何机器来处理[3]。

1 柔性工作车间调度问题

传统的JSP 模型只考虑一个优化目标，一般是最小化整个过程的完成时间。然而，很多时候制造商对完工时间并不敏感，因为一般来说生产的最后期限总是多余的。相反，由于经济原因，较低的能源消耗通常被视为优化目标。近期，关注柔性作业车间调度问题的研究变得火热，其中，黎阳[4]等人为解决大规模(工件数＞100)置换流水车间调度问题，提出一种改进的模拟退火算法，并通过实验进行了验证；李尚函[5]等人则提出一种混合超启发式遗传算法(HHGA)，考虑了最小化最大模糊完工时间，用于求解一类采用三角模糊数表示工件加工时间的模糊柔性作业车间调度问题。

在对FJSP 进行求解时，已有的文献大都只考虑了问题规模较小，复杂度不高的情况[6-8]。在一些复杂问题上，已有的文献往往只注重于快速地收敛，而忽视了种群本身的多样性问题。这就会导致种群早熟的问题[9]。具体来说，对于简单的遗传算法求解FJSP，算法在初期（前10 代），种群中的个体就变得几乎一样，大大降低了种群跳出局部最优解的概率。另一方面，过早的收敛也会导致剩余的搜索变得无效。因此，为了解决这个问题，该文提出了一种全新的基于粒子群[10]和蚁群[11]的混合算法，具体来说，蚁群算法具有较好的局部搜索能力，而粒子群算法具有较强的全局搜索能力。通过将两个算法进行混合，可以在前期以较大概率采用粒子群搜索算法进行初步探索，在这一阶段，种群的收敛性不是算法的首要目标。接着在算法运行的中后期，设置较大的概率，使用蚁群算法进行局部探索。在这一阶段，引入了局部搜索策略以提高种群的收敛能力。为了验证该文所提算法的有效性，在一个规模较大的算例上进行了对比实验，实验结果表明该文所提算法收敛能力较强。

JSP 是计算机科学和运筹学中的一个经典优化问题[12]，其中不同的工件需要在规定时间内被分配到指定的机床上进行加工，从而在规定时间内完成所有的加工任务。为了简洁地进行表达，在该研究中给出了最基本的版本。给定n个处理时间不同的作业J1,J2,…,Jn，这些作业需要被安排在处理能力不同的机器上。安排的目标是试图使全部任务的完成时间最小化。makespan 是计划的总长度（即所有工作都完成处理）。一般来说，该过程的目标是使makespan 最小化。随着制造业的发展，其他目标也被考虑在内，如能源消耗最小化，机床利用率最大化等[13]。柔性作业车间问题（FJSP）是经典作业车间调度问题的扩展，它允许一个任务由给定的任何机器来处理。文中考虑一个基于基本FJSP 的模型。在一个灵活的加工车间，有I种需要加工的工件类型，其中每一种都包含有Ji道工序，在这个车间里，机床的数量为M。

1.1 约束条件

为了更好地理解该文研究的柔性工作车间调度问题，使用i、j、m分别代表工件、工件工序和机器代码的索引。

对于所有的工件，各工序之间存在着顺序关系。也就是说，只有在前序工序完成后，才能在机床上加工后续工序。

对于所有的机床来说，在整个加工过程中，同一时间内只能加工一个工件，这一点可以表示如下：

工件只有在截止时间前到达并完成后才能进行加工。如式（3）所示：

1.2 目标函数

对于一个传统的工作车间调度问题，有几个目标。然而，该文考虑的是最常见的两个目标。一个目标是最小化整个过程的makespan 时间，另一个目标函数是最小化单位时间的功耗，可以表示为：

2 粒子群和蚁群混合算法

2.1 粒子群算法

粒子群优化（Particle Swarm Optimization,PSO）算法是一类非常经典的算法。近年来，针对粒子群算法的改进非常多。标准的粒子群优化同时使用当前的全局最佳位置和个体最佳位置。使用个体最佳的原因之一可能是为了增加高质量解决方案的多样性。然而，这种多样性可以用一些随机性来模拟。因此，除非优化问题是高度非线性和多模态的，否则没有令人信服的理由去使用个体最佳位置。

2.2 蚁群算法

蚁群算法(ACO)的灵感来自于蚂蚁的觅食行为。这种行为的核心是蚂蚁之间在化学信息素轨迹的帮助下进行间接交流，使得它们能够找到巢穴和食物来源之间的短路径。ACO 算法具有很强的鲁棒性以及良好的分散计算机制。局部蚂蚁有能力向具有最佳解决方案的潜伏区域移动，这与区域k的过渡概率有关。

2.3 粒子群和蚁群混合搜索

与其他基于启发式算法的进化算法相比，PSO的优势在于易于实施，需要调整的参数数量较少。然而，众所周知，最初的PSO 在控制探索（全局搜索）和利用（围绕局部最优的精细搜索）之间的平衡方面存在困难。另一方面，现有的进化算法由于缺乏种群多样性保持机制，因此极容易陷入局部最优解[14-15]。为了改善PSO 的这一特点，该文提出使用粒子群和蚁群的混合搜索策略（hACOPSO）。

具体来说，hACOPSO 算法的实现包含了两个种群，分别对应粒子群和蚁群算法的种群。在初始化阶段，粒子的位置和蚂蚁的位置一一对应。在每一次迭代过程中，首先计算出蚂蚁的信息素浓度，并根据过渡概率选择搜索方式。当过渡概率低于预设值时，使用基于蚁群算法的局部搜索策略进行搜索；反之，则使用粒子群算法进行大规模搜索。值得注意的是，在每一次搜索完之后，如果个体的目标函数值比原来较好，则同时更新蚂蚁和粒子的位置，从而推动算法向最优解不断前进。

2.4 求解FJSP的编码方法

应用进化算法对现实世界的问题进行求解的主要问题是如何对解决方案进行编码[16]。对于传统的作业车间调度问题，大多数研究采用基于工序的编码。但是，在解决柔性作业车间调度问题时，还需要为每道工序选择合适的机床进行处理，较以往问题更加复杂。鉴于上述问题，该文提出了一种两层染色体编码方法，其示意图如图1 所示。一个染色体就是一个调度问题的解决方案。从图中可以看出，第一层编码（即工序码）用于确定不同工件对应工序的顺序，第二层（即机器码）用于确定工序的机床。

图1 编码方式

工件码的基因总数等于所有工件的工序数之和。在图1 中，工件码的基因总数为8。每个工件的工序直接用相应的工件编号编码，工件的累计出现次数等于其工序数。染色体的工序编码从左到右进行扫描。

3 实验

3.1 实验案例

表1 列出了每台机器的待机功率和空载功率。表2 说明了每个工件的到达时间和最后期限，可以看出，整个过程的最后期限是60 000 s。此外，在该研究中，有5 个工件需要被加工。每个工件工序的数量分别为3、4、3、4 和4。

表1 不同机床的待机和空载功率

表2 工件到达和截止时间

3.2 不同算法的收敛性对比

文中提出了一种粒子群和蚁群的混合搜索算法。为了验证该算法的有效性，选择标准的粒子群算法、蚁群算法和粒子群和蚁群混合搜索算法进行对比。为了保证实验的公平性，统一设置种群大小为100，迭代次数为100 次。为了降低随机因素带来的影响，将所有实验独立运行31 次并取平均值。选择最接近算法平均值的单次运行结果被进行分析和展示。

图2 显示了不同的算法在求解该文研究问题时的最优解收敛情况。可以看出，粒子群和蚁群混合搜索算法优于其他两个算法。值得注意的是，混合算法在收敛速度和收敛精度上均表现较好。这是因为，混合算法结合了两种搜索策略的优势，在全局搜索和局部搜索中均能采用最合理的方式进行搜索，因此表现较好。

图2 不同算法的收敛示意图

3.3 结果分析

为了探究所提算法的有效性，将粒子群和蚁群混合搜索算法的最终求解结果展示如图3 和图4 所示。从图3中可以看到，最小的完成时间是365 044 s，此时的能量消耗为1 233.3 kW·h。可以看到，工件5是最后完工的。这是因为算法试图尽可能早地关闭机器，这是一个精明的策略，以尽量减少电力的使用。因为，当机器处于闲置状态时，会有空载功耗，这完全是一种浪费。通过对工作车间的调度进行建模，并采用适当的优化算法，可以在一定程度上减少不必要的电力消耗。

图3 注重功耗的工序甘特图

图4 注重完工时间的工序甘特图

图4 所示是更加注重完工时间的工序甘特图，其最小完成时间为405 390 s，所需要的能量为1 245.6 kW·h。

4 结论

随着社会和制造业的发展，作业车间调度问题已经得到了有效的解决。然而，对于规模较大或者非线性系统来说，传统的优化算法容易陷入局部最优中，且收敛速度较慢。为了进一步提高进化算法在此类问题的搜索效率，文中给出了一个柔性工作车间调度模型，并进行了明确的说明。考虑两个目标来优化这个模型，一个目标是最小化整个制造过程的完工时间，另一个目标是最小化能量使用。并且提出了一种基于粒子群和蚁群算法的混合算法进行求解。通过实验结果，证明混合算法具有更快的收敛速度和收敛精度。

进一步的研究包括制作一个更详细的模型来对生产进行指导。此外，该文提出的方法不仅可以在工作车间调度问题上进行，也可以扩展到其他问题。因此，对这种算法的进一步研究，使其更适合也更容易用于解决现实世界的问题。