Job—shop调度求解的广义蚁群算法

张宏国　宫雪

摘要：针对蚁群算法求解Job-shop调度问题，该算法考虑到利用析取图来描述工件加工关系给算法带来的复杂度，提出了一种广义蚁群算法。在综合考虑设备和工序关系约束的前提下，将信息素更新机制运用到求解Job-shop调度问题中，从而提高解的质量。为了提高搜索效率，根据蚁群算法的状态转移规则，对算法中参数的选择进行了详细的研究，设计了信息素更新策略。仿真实验结果表明，广义蚁群算法得到的解更接近最优解，该算法的收敛速度明显高于其他算法的收敛速度。

关键词：Job-shop调度问题；广义蚁群算法；信息素更新机制

中图分类号：TP391 文献标志码：A 文章编号：1007-2683（2017）01-0091-05

0 引言

现代制造业的市场竞争日益激烈，生产调度是现代制造业面临的重要问题，它的解决有利于提高企业的生产效率与经济。Job-shop调度问题（Job-shop scheduling problem，JSP）是生产调度中最基本的组合优化问题，在满足工艺路线、交货期与资源利用等约束条件下，合理安排工艺加工时间、先后顺序及使用资源，可以减小生产周期，减少库存，获得产品时间或成本的优化。因此Job-shop调度问题的优化求解具有重要的理论价值和实际意义，是学术界与工程界共同关注的热点。

目前求解Job-shop调度问题的主要方法是建立智能优化算法，以禁忌搜索、模拟退火、遗传算法为代表。蚁群算法具有正反馈、较强的鲁棒性、全局性、普遍性、优良的分布式并行计算机机制，易于与其他方法相结合等诸多优点。近年来，很多学者将蟻群算法逐渐地应用于Job-shop调度求解中。文提出了一种自适应蚁群算法（AACA），自适应地初始化信息素并限定其大小范围以得到优解。文提出了最大最小蚁群算法，对信息素进行限制防止算法陷入局部最优。文提出了混合算法，将蚁群算法和遗传算法相结合的ACSGA算法，充分利用它们的特性。

但上述文献都是采用传统蚁群算法中析取图的方式对工件加工关系进行描述的。虽然析取图是用来描述路径关系比较好的视图形式，但是车间生产中各工件之间的加工关系不同于旅行商问题（TSP）中的路径选择。特别是对于加工规模较大的Job-shop调度问题，每增加一个机器，析取图就会增加条边，则形成的析取图结构会十分复杂，使得算法的复杂度增加，收敛速度变慢，影响解的质量。

本文提出一种广义蚁群算法，将其用于Job-shop调度求解中。该算法利用一次调度就是蚂蚁的一次爬行的思想，摆脱传统的析取图方式，把信息素更新机制应用到Job-shop调度问题中，这样能有效的简化算法复杂度，提高算法的收敛速度，优化解的质量。将信息素机制合理的应用在每一道工序上，在满足约束条件和解的合法性的前提下，越早完成加工的工序和同一工件优先进行加工的工序上残留的信息素浓度越高。

1 Job-shop调度问题分析

1.1 问题描述

n个工件在m台机器上加工，每个工件有m道工序，加工时间已知，要求总完工时间最小。针对Job-shop调度问题的具体约束条件如下：

1）同一时刻同一台机器只能加工一个工序；

2）前一道工序加工完毕后才能加工下一道工序；

3）每个工序在可用机器上的加工时间不同且已经确定；

4）允许工件在工序间等待，也允许机器在工件未到达前闲置；

5）工序一旦开始，不允许中断。

1.2 问题建模

关于Job-shop调度问题，作如下定义：1）n：工件数目；

2）m：机器数目；

3）工件集J={J₁，J₂，…，J_n}，1≤i≤n；

4）机器集M={M₁，M₂，…，M_m}，1≤k≤m；

5）工序集O_i={O_i，1，O_i，2，…，O_i，m}，其中O_i，j表示工件i的第j道工序；

6）M_i，j表示O_i，j占用的机器，M_i，j∈M；

7）T_i，j表示第i个工件第j道工序的加工时间；

8）S_i，j表示第i个工件第j道工序的开始时间；

9）C_i，j表示第i个工件第j道工序的完工时间，C_i，j=S_i，j+T_i，j。

因为工件完工要求所有工序加工完毕，并且每道工序开始加工时，它的紧前工序必须加工完毕，所以工件加工完毕的时间为各设备完工的最大时间值。因此在给定约束条件的前提下，调度的最短时间值是所求的结果，其数学描述为：

（1）

（2）

（3）

在上面式子中，式（1）表示目标函数，调度的整体完工时间最短。式（2）表示对于同一工件i来说，工序j+1的开始加工时间，一定会大于其紧前工序j的开始加工时间与连续加工时间之和。式（3）表示对于同一设备来说，同一设备在同一时刻只能加工一道工序。

2 Job-shop调度求解的广义蚁群算法

2.1 广义蚁群算法的总体思想

蚁群算法是一种基于反馈机制和并行机制的模拟进化算法，在大规模的调度问题中有其固有的优势，但也容易出现搜索时间过长导致局部优解。传统的蚁群算法用析取图来求解JSP问题，析取图被描述为一个有向图，更直观的展现便于分析。但对于规模大的JSP问题会加剧蚁群算法的缺陷，因需要优化的问题规模变大，那么得到相应的解就会增加迭代次数，增加了相应的计算时问，进而影响解的质量和算法的收敛速度。

广义蚁群算法利用每一次的调度需要蚂蚁爬行一次的思想，寻找的最优路径就是蚂蚁爬行所走的最短路径。运用广义蚁群算法求解时，一只蚂蚁从一个工件的第一道工序开始爬行，根据转移状态规则对可调度的工序进行选择。将选择的工序标记为已操作工序，计算概率继续选择接下来要调度的工序，直到每台机器未调度的工序集为空为止，即完成一次调度。

每次调度之后更新信息素，信息素的改变直接影响工序转移概率的计算结果，因此信息素的更新要与工序的优先级紧密联系。针对蚁群算法的特点，对信息素更新机制进行改进，以便更快找到工序在各机器上加工的一组优先序列。

2.2 信息素更新机制

1）状态转移规则

蚂蚁根据信息素的浓度和工序问的启发式信息，在其可选尚未调度的集合中选择接下来的目标工序。选择工序的时候需要判断各工序在机器上的加工概率，状态转移概率公式如下：

（4）从式（4）可看出，状态转移概率主要根据t时刻工序i转移到工序j上的信息素浓度τ_ij（t）以及工序i到工序j的启发式信息η_ij（t）。其中，α和β是两个参数，分别表示信息素的影响力和启发式信息的相对重要性，AS表示可选尚未调度的集合。

2）信息素计算公式

在求解Job-shop调度问题时，蚂蚁在遍历过程中留下信息素，路径上的信息素浓度随着蚂蚁每次遍历进行更新。信息素浓度的强弱引导着后面的蚂蚁对工序的选择，某个路径上蚂蚁遍历的次数越多，信息素浓度越大，后来者选择该路径遍歷的概率就越大。当蚂蚁所走的路径越短即调度结果越优时，该路径的信息素浓度越大。

信息素更新机制是工件加工排序中的重中之重，因此本文对信息素的更新公式进行优化，会着重突出信息素的作用和影响，削弱启发式信息的重要性。信息素浓度的变化受工序节点开始时间以及局部目标函数完成时间的影响，根据这一原则区分工序的优先级，优先安排信息素浓度大的工序。

在一次遍历工序中，蚂蚁遍历工序的完成时间越早，信息素浓度越大。其次，开始时间越早的工序，信息素浓度越大，越优先安排。在传统的信息素公式中，由于开始时间和完成时间都与信息素的大小有直接影响，所以在信息素浓度相同的情况下，确定不了工序的优先顺序。因此对计算信息素浓度的公式加以完善，这样会更快得到较优的加工序列。计算信息素的公式如下：

（5）

通过式（5）对信息素浓度的赋值，保证了越早完成加工的工件对应的工序上信息素浓度越大，并且同一工件的前道工序获得的信息素浓度比后道工序获得的信息素浓度大。

3）公式参数的分析

为了避免信息素过小而影响解的计算，故在式（5）的分母上加上系数γ以保证解的合理性公式，γ为信息素放大系数，取经验值γ=∑T_ij。同时为了保证工序的选择不会因为开始时间而淹没完工时间的影响，故在式（5）的分子中的完成时间上乘上一个常数z，适当扩大完工时间对信息素的影响，z为调整信息素浓度系数，z取经验值。在算法的具体实行时通常取z=n，这样通过对公式参数的设置更有效的保证了对调度周期的优化。

4）信息素更新方式

蚂蚁完成一次调度后，更新当前路径上的各工序信息素浓度，更新方式如下：

（6）

（7）式（6）中，△τ^k_ij（t，t+1）表示第k只蚂蚁在（t，t+1）时刻从工序i移动到工序j这一过程的信息素增量。式（7）表示信息素的更新方式，其中ρ表示信息素挥发系数，信息素会随着时间不断挥发，ρ∈（0，1）。

2.3 算法步骤

符号表示：AS为可调度的工序集合，CS为完成调度的工序集合，GS为未调度的工序集合，IS为正在调度的工序集合。

步骤1：初始化AS={O_i1|i=1…n}，CS=φ，GS={O_ij|i=1…n，j=1…m}，IS=φ。

步骤2：初始化蚂蚁数目n，参数α，β，ρ，机器M_ij的可用时刻为MT_mij以及当前时刻ST_ij。

步骤3：当调度解多次不再优化时，算法停止，输出结果。否则重置并转到步骤1。

步骤4：一共有k=1～n只蚂蚁，当初始时刻t=0时，分别放在各工件的第一道工序O_，1上，更新当前时刻ST_ij=ST_k，1，各机器可用时刻MT_mij=T_k，1，更新集合AS=AS-{O_k，1}，GS=GS-{O_k，1}，IS=IS+{O_k，1}。

步骤5：对于m个机器，如果机器可用时刻MT_mij≤T_k，1，则机器空闲，进行下一个工序的选择。如果AS中只有一个可调度工序，则直接将此工序放人IS；如果存在多个可调度工序，根据式（7）计算转移概率，按轮盘赌的方式选择接下来要加工的工序O_ij；如果不存在直接跳过，转步骤7。

步骤6：当蚂蚁移动到所选工序O_ij时，AS=AS-{O_ij}，GS=GS-{O_ij}，IS=IS+{O_ij}。O_ij完成调度之后，CS=CS+{O_ij}，当前时刻ST_ij=ST_k，1+T_ij，将接下来要调度的工序O_i，j+1放入AS中。

步骤7：判断GS是否为空。如果GS=φ，说明蚂蚁遍历所有工序，完成了一次调度，执行步骤8；否则，转步骤4。

步骤8：蚂蚁完成一次调度后，记下调度序列，对该蚂蚁当前路径各工序信息素浓度进行更新。

步骤9：比较前后两只蚂蚁爬行所用的完成时间，选择完成时间短的。每次调度后都选出较优的调度序列，对目标函数值进行更新并记录调度序列。

步骤10：直到所有蚂蚁都完成寻优，得到最优的完工时间及调度序列。

3 仿真实验

3.1 实例验证

根据上述理论，针对所描述的广义蚁群算法进行模拟仿真实验，并做出分析与评价，验证算法的可行性。应用实例是6个待加工工件（J₁，J₂，…，J₆）在6台机器（M₁，M₂，…，M₆）上加工的典型Job-shop調度问题。

1）参数确定：α=2，β=3，ρ=0.5；

2）实例中加工机器对应的加工工序如表1所示，加工时间如表2所示。

表2的加工时间与表1中的加工工序对应着，根据广义蚁群算法得到最优调度序列，用6行6列的S矩阵表示。矩阵的每一行代表一个加工机器，矩阵的每一列表示工序的由开始到最后的加工顺序。例如一行一列的（1，2）代表在M₁上首先加工的是O₁₂，第二行第二列的（4.1）代表在M₂上第二个加工的是O₄₁，依此类推。

为了更直观的看出机器的加工状态，根据S矩阵绘制甘特图如图1所示。图中每个实线方块代表一个加工工序O_ij，方块的长度代表此工序在此台机器上的加工时间，方块外的空白之处代表机器的空闲时间。从甘特图可看出完成时间是55，也是已知的最优解，该算例证明了广义蚁群算法的可行性和有效性。

3.2 算法评价

用广义蚁群算法求解Job-shop调度问题的5个经典算例，采用Matlab软件进行编程仿真。仿真结果与其他算法得到的结果进行对比，其他算法的结果由文献给出，如表3所示。由表可知，与遗传算法、传统蚁群算法相比，广义蚁群算法的结果更接近最优解，可见达到了优化的目的。

收敛曲线对比：图2中纵坐标表示目标函数值，横坐标表示循环次数，黑色曲线是本文提出的广义蚁群算法的收敛曲线，红色曲线是基本蚁群算法的收敛曲线，蓝色曲线是遗传算法的收敛曲线。从图中可以看出本文的算法更优，不仅收敛的速度快而且得到的目标函数值更贴近最优解。

4 结论

根据蚁群算法求解Job-shop调度问题，考虑到用析取图求解规模较大的调度问题时会非常复杂，而且缺少对蚁群算法并行特性的体现。本文从算法的调度方式、信息素的更新机制方面进行改进，提出了广义蚁群算法。通过应用实例进行试验，检验了该算法对实际问题的有效性，与传统蚁群算法，遗传算法进行对比，结果表明本文提出的广义蚁群算法获得的解更接近最优解，而且算法的收敛速度更快，这说明本文求解Job-shop调度问题的方法更有效。

（编辑：关毅）