改进的蚁群算法求解置换流水车间调度问题

张丽萍(青岛科技大学 信息科学技术学院，山东 青岛266061)

置换流水车间是很多实际流水线生产调度问题的简化模型，是目前研究最广泛的一类经典的调度问题。由于置换流水车间调度问题属于NP-hard难题，不存在多项式精确求解算法，因此，对这类问题的研究具有重要意义。

求解置换流水车间调度问题的方法大致可以分为三类[1]：经典算法(如线性规划、动态规划、整数规划、分枝定界等)、启发式算法(如 Gupta 法、Palmer法、Johnson 法、CDS法、NEH法等)和基于人工智能的元启发式算法(如模拟退火、禁忌搜索、遗传算法、蚂蚁算法等)。经典算法的计算复杂性一般很大，只适合求解小规模置换流水车间调度问题，在工程中往往不实用。启发式算法通过一定的规则可以快速地构造出问题的解，但通常解的质量较差[2]。基于人工智能的元启发式算法能够较快地构造出问题的解，因此，在置换流水车间调度问题中被广泛使用。

蚁群算法是受到自然界中真实蚂蚁的启发，由意大利学者DORIGO M于1991年提出的一种元启发式算法。该算法具有鲁棒性和通用性等良好特性，在求解作业车间、流水车间等调度问题上取得了较好的效果。但是，传统的蚁群算法存在计算时间长和易陷入停滞的问题，故本文从结合NEH算法和自适应调节策略两方面来改善蚁群算法的性能，经Taillard基准测试验证，改进后的蚁群算法有效。

1 问题描述

置换流水车间调度问题研究的是n个工件在m台机器上的流水加工过程，所有工件以相同的顺序在每一台机器上加工完成，同时约定每个工件在每台机器上只加工一次，每台机器每次最多只能加工一个工件，各工件在各机器上所需的加工时间已知，要求得到某调度方案使得总加工时间最小。定义J=(j1，…，jn)为所有机器上的一个加工排序，ti，j为操作的执行时间，Ci，j表示操作的完成时间。则加工任务jk在机器i上的完成时间Ci，jk按式(1)计算：

2 蚁群算法

2.1 蚁群算法简介

蚂蚁是一种没有视觉的动物，但是它们可以通过信息素，协同找到食物和巢穴之间的最短路径[3]。蚂蚁在运动过程中能够感知这种物质的存在及其强度，并以此指导自己的运动方向，使蚂蚁倾向于朝着该物质强度高的方向运动。这样，由大量蚂蚁组成的蚁群的集体行为便表现出一种自催化的正反馈行为，较短路径上会有较多的信息素累积，越来越多的蚂蚁选择信息素浓度高的路径，而其他路径上的信息素浓度却会随时间衰减，最终蚁群能找到一条从食物源到巢穴的最短路径[4]。

蚁群算法最初用于解决旅行商问题，之后陆续渗透到其他领域中。较早把蚁群算法应用到置换流水车间问题的是YING K C和LIAO C J，后者在Tailard的benchmark问题上做了测试，证实该方法非常有效。

2.2 蚁群算法

本文以求解置换流水车间问题说明MMAS模型。求解这类问题有两种解构造模式，分别为弧模式和节点模式[5]。本文采用的是节点模式。

在解构造的结点模式下，代表流水车间调度问题的有向图 G=(N，A)，如图 1所示。 其中，N={Oij}是图中的节点集合，节点Oij代表作业j位于作业处理序列π的第i个位置；A是图G中部分连接节点集N中各节点的有向弧的集合，连接节点 Oij和 O(i+1)，l的有向弧方向为从 Oij～O(i+1)，l。 这里的路径选择 概率为：

图1 节点模式下的流水车间

在节点模式下，式(2)中 Nk(Oij)={O(i+1)，l|l∉π′}代表节点 Oij的可行领域集合。 其中 τij和 ηij分别代表对应于节点Oij的信息素浓度和基于问题的启发式信息。表示人工蚁搜索过程中从节点移到节点 Oij的概率。

从虚构节点job0出发，按照式(2)给出的状态迁移规则，在G图中一步步地构造出问题的解，蚁群算法的流程如下：

(1)设置参数。设置迭代次数counter=0,设置最大迭代次数Ncmax。计算每个工件的总加工时间Si(i=1，…，n)，定义能见度ηij=Si。按照工件总加工时间 Si最大优先的原则计算出最大流程时间makespan，设置信息素赋初始值 τ0=1/((1-ρ)·makespan)；τmax=τ0，τmin=τmax/5。

(2)初始化m个蚂蚁，将m个蚂蚁放在虚拟节点job0上。

(3)每个蚂蚁都按照式(2)选择下一步路径。

(4)将新选择的工序添加到禁忌表中，判断是否遍历了所有的工件，是则执行步骤(5)，否则执行步骤(3)。

(5)按照式(3)更新信息素。

其中，ρ为信息素残留系数(1-ρ为挥发系数)；△τij=1/Cbest，令Cbest为迭代以来最优解，|Cbest|为 Cbest的 makespan值，如果Cbest中位置 j上工件不为 i，则 △τij为 0，否则 △τij=1/|Cbest|。信 息 素 取 值 区 间 为 [τmin，τmax]， 若 τij＞τmax， 则 设 定 τij=τmax；若 τij＞τmin，则设定 τij=τmin。 这样可以较好地防止早熟现象。

(6)count++。 如果 count＜Ncmax，则清空禁忌表，返回步骤(2)继续执行；否则，结束循环。

3 MMAS的优化

3.1 NEH启发式算法

NEH启发式算法是由 NAWAZ M、ENSCORE E、和HAM I共同提出的算法[6]，该算法步骤如下：

(1)按n个工件在机器上总加工时间递减的顺序排列各个工件。

(2)取前两个工件调度使部分最大流程时间达到极小。

(3)从k=3～n把第k个工件插入到k个可能的位置，求得最小部分的最大流程时间。

3.2 与NEH算法的结合

(1)获取初始解。利用NEH启发式算法计算得到最大流程时间 makespan，并定义 τ0=1/((1-ρ)·makespan)。

(2)部分NEH局部搜索。在使用MMAS构造出路径之后，对构造的工件顺序按照NEH启发式算法的步骤(2)、(3)构造出解。利用NEH启发式算法进行局部寻优，可以进一步提高MMAS的求解质量。但是为了保证算法的时间效率，在此只对Nmax次迭代中的前N次迭代利用NEH启发式算法对迭代最优蚂蚁进一步局部寻优。

3.3 自适应信息素挥发系数

与NEH算法相结合，虽然极大程度地提高了MMAS解质量，但是也从一定程度上加速了MMAS的局部收敛速度。为此，本文引入自适应改变挥发度系数的方法，以进一步提高MMAS的全局搜索能力。

在算法模型中，信息素挥发系数ρ的大小直接关系到蚁群算法的全局搜索能力及收敛速度[3]。ρ过小，从未被搜索到的节点的信息量会减少到接近于0，降低了算法的全局搜索能力；而ρ过大，以前搜索过的解被选择的可能性过大，也会影响到算法的全局搜索能力。因此可以自适应地改变ρ的值，当最优值在一定循环次数内没有明显改变时，降低ρ的值。公式如下：

其中，ρmin为 ρ的最小值，用来防止 ρ过小，降低算法收敛速度。

3.4 改进MMAS的实现流程

改进后的MMAS算法求解置换流水车间问题的流程图如图2所示。

图2 改进MMAS算法流程图

(1)初始化各个参数。设置蚂蚁数量为m、迭代次数counter=0、最大迭代次数为Ncmax、局部搜索次数为 N。计算每个工件的总加工时间Si(i=1，…，n)，定义能见度ηij=Si。 设置信息素残留系数为 ρ，ρmin为 ρ的最小值，定义Nm次迭代最优解相同，则判定陷入局部最优。

(2)利用NEH启发式算法得到总加工时间的初始值makespan，设置 τ0=τmax=1/((1-ρ)·makespan)，τmin=1/5·τmax。

(3)将各只蚂蚁放在虚拟节点job0上，对于每只蚂蚁，按照式(2)选择下一步路径，直到所有蚂蚁均构造出解。

(4)若count＜N，则利用NEH启发式算法的后两步对最优迭代蚂蚁选择的路径做进一步局部寻优；否则，执行步骤(5)。

(5)判断迭代最优解相同次数小于 Nm，则执行步骤(6)；否则，按照式(4)改变挥发系数的值，再执行步骤(6)。

(6)按照式(3)进行信息素的更新，检查信息素的边界，使其保持在[τmin，τmax]的范围内。

(7)count++。如果 count＜Ncmax，清空禁忌表，返回步骤

(3)继续向下执行；否则，结束循环，输出结果。

4 仿真实验

本文测试数据采用Taillard在1993年提出的基准测试问题，并将运行结果与其他参考文献提出的算法进行比较，以此验证提出的改进蚁群算法是有效的。

本文算法各参数设置如下：蚂蚁个数 na=20，挥发系数 ρ=0.99，挥发系数最小值 ρmin=0.5，α=1.0，β=4.0，最大迭代次数为300，局部搜索次数为10。本文选取每种规模系列问题中的第一个问题进行计算，并与NEARCHOU A C[5]提出的算子遗传算法(GA)、Lian Zhigang[7]提出的NPSO粒子群算法进行比较，每个算例连续运行20次，记录其中的最优结果，如表1所示。其中，BS表示运行结果中的最优解，RPD(Relative Percentage Deviation)表示相对误差百分率。由表1可知，相比其他两种算法，本文提出的算法在求解Taillard系列问题方面能够更好地收敛在最优解附近。

表1 改进蚁群算法的运行结果

本文针对解置换流水车间调度问题提出了一种改进的蚁群算法。在该算法中，采用NEH算法产生初始解，并利用自适应挥发系数的方法避免算法早熟，使分散搜索和集中搜索达到有效平衡，提高了算法的搜索能力。Taillard系列基准问题测试表明，本文的算法是有效的。

[1]高海兵，周驰.广义粒子群优化模型[J].计算机学报，2005，28(12)：1980-1987.

[2]王凌.车间调度及其遗传算法[M].北京：清华大学出版社，2003.

[3]李士勇.蚁群算法及其应用[M].哈尔滨：哈尔滨工业大学出版社，2004.

[4]吴启迪，汪镭.智能蚁群算法及其应用[M].上海：上海科技教育出版社，2004.

[5]NEARCHOU A C.The effect of various operators on the genetic search for large scheduling problems[J].International Journal of Production Economy，2004，88(1)：191-203.

[6]NAWAZ M，ENSCORE E，HAM I.A heuristic algorithm for the mmachine，n job flow shop[J].The International Journal of Management Sciences，1983，11(1)：91-95.

[7]Lian Zhigang，Gu Xingsheng，Jiao Bin.A Novel particle swarm optimization algorithm for permutation flow shop scheduling to minimize makespan[J].Chaos，Solitons and Fractals，2008，35(5)：851-861.