论文部分内容阅读
[摘要]提出一种混合蚁群算法，并用其解决经典JSP问题。受转换瓶颈启发式算法的启示，将蚁群算法与禁忌搜索算法相结合，发现这种改进在防止早熟与加速收敛这对矛盾之间找到了一个比较好的结合点。
[关键词]作业车间调度问题蚁群算法禁忌搜索算法转换瓶颈算法
中图分类号：TP3文献标识码：A 文章编号：1671－7597（2008）0510032－02
一、引言
车间调度问题一直是组合优化问题中的一个公认的NP难题[1]，对此问题的解决方案无外乎确定性算法和启发式算法。 确定性方法固然可以得到最优解但是对待规模较小的优化问题起计算是比较现实的，但是对于规模稍大一点的问题确定性算法在现有的条件下近乎是不可能的算法。近年来，启发式用于解决jsp问题取得了一定的成果[2][3]。
蚁群优化（ACO）这个在90年代初产生的群体智能算法[4]，在解决TSP问题中取得了巨大的成功，很快就被尝试用来解决JSP问题，然而结果却不是令人满意的。对于某些问题，例如单机器总权重延迟问题开放车间问题和资源约束项目调度问题，ACO是性能最好的算法之一。而对于其他经典的调度问题如排列流车间问题和作业车间问题计算结果还远逊于当前最先进的算法[5]。
本文针对单独使用蚁群优化来解决车间调度问题的不足，受转换瓶颈算法[6]启发，尝试把蚁群优化与禁忌搜索算法相结合来解决车间调度问题。
二、Job-shop scheduling problem
作业车间调度问题（Job-shop Scheduling Problem，JSP）可描述为：给定一个工件的集合和一个机器的集合，每个工件包括多道工序，每道工序需要上非间断的在一台给定的机器加工一段时间；每台机器一次最多只能加工一道工序；调度就是把工序分配给机器上的一个时间段。问题的目标是找到最小时间长度的调度。
其数学模型可描述如下：给定3个操作集合：O为操作集 ，M是在不同机器上的操作的子集合的集合， J是不同工件上操作的子集合的集合
O={O1，O2，…，Oo}
M={M1，M2，M3，…，Mm}其中Mi 表示在第i台机器上的操作集合
J={J1，J2，…，Jj}其中Ji 表示属于第i个工件的操作集合
JSP可以用图的形式表现出来。构建图除了包括代表每个操作的结点外，还有两个额外的结点作为起始结点和终结点。通常，这些结点之间都是完全连接的。给定一个JSP的实例，可以构建出图G=（V，A，E），其中，V是点的集合，对应着所有操作以及一个起点和一个终点；A是实线弧，表示的是属于同一个工件的操作之间用有向实线连接；E是虚线弧，表示的是同一台机器上执行的操作之间用不带方向的虚线连接。问题的一个可行解就是给图中的无向边选择方向，使得结果图中不带回路。虚线弧确定了方向，也就决定了相对应的机器加工操作的顺序。
三、ACO-TS-JSP算法
蚁群算法的提出借鉴和吸收了现实世界中蚂蚁种群的行为特征：蚂蚁在食过程中能分泌一种称之为信息素(pheromone)的物质，并能利用信息素的轨迹(trail)作为媒介与其它的蚂蚁进行信息沟通．一条路径上留下的信息素轨迹的多少与这条路径上通过的蚂蚁数成正比，当通过的蚂蚁越多，则留下的信息素轨迹就越多，从而导致后来蚂蚁选择该条路径的概率提高．这样，没有视觉能力的蚂蚁在上述过程中展现出了一种协作的自催化行为能力，蚂蚁正是基于此建立最短的移动路径．
本文在对蚁群算法进行改进，将禁忌搜索熔入到蚁群算法中，求解JSP问题，提出了ACO-TS－JSP算法。
（一）初始化阶段
为了减少计算量，我们应用一种简单的静态规则(总机器负载TML规则)来区分瓶颈机器[5]，总机器负载可以提前计算出来。TML规则定义如下:
其中，π（m）是机器m的排序标签。在这一步，对所有的路径赋予初始信息素τ0，τ0是一个相对较小的值。
（二）构建解阶段
1．信息素结构定义
在应用ACO算法之前，一个重要的问题是对信息素进行定义。传统的构建方法是在每一次构建中，只有当一个操作所有之前的操作都已被排程，才会考虑该操作，我们不使用这种方法，我们采用一种分解策略来构建一次排程，这一方法是受SB方法启发得到的。事实上，这种分解方法经常用于JSP问题中。
在我们的方法中，一个|M|×|J|的JSP问题被分解成|M|个独立的SMP，对于其中的每一个，一只蚂蚁逐步构建工序的排列，直到所有的机器都排程完毕。因此，我们对于每一个机器定义了一个|J|×|J|的信息素矩阵。每一个信息素矩阵使用信息素轨迹的绝对位置来定义。（例如，信息素轨迹和一次操作到一个位置的分配相关联），这一方法通常应用于SMP中，并且得到了很好的结果。
2．状态转移规则
在构建阶段，每一只人工蚂蚁在未排程的机器中选择一台具有最高TML的机器。然后，从可行集OV中选择下一步操作，而不是从OM中选择，OV的确定将在下边3.2.3节中详细介绍。我们应用下边的状态转移规则选择下一步操作：
上式中τm（p，j）为从信息素矩阵m中得到的将工序j放到位置p的信息素，是 的贪婪启发式期望值。参数q0（0≤q0≤1）决定了开发与探索之间的相对频率，参数β决定了启发式信息的影响。φ是根据下式给出的概率分布产生出来的一个随机变量：
（1）式和（2）式中的状态转移规则称为伪随机比例规则。这一规则有利于选择具提有提高信息素水平的路径。
3．延迟优先约束
在SB方法中，当几台机器已经被排程了，在给定的未排程的机器上的操作将受到特定的优先约束。这是由于在一台特定机器上的某项操作可能只有当在该机器上的某些相关操作完成后，才可以被排程。ACOFT使用了相似的构建方法因此也遇到了同样的问题。为了保证可行性，我们应用延迟优先约束进行解决，方法如下：在对一台机器m进行排程之前，我们使用深度优先搜索方法得到suc（ ），即所有的 的后继集。如果存在一项操作属于suc（ ），我们就得到一项延迟优先约束（ ）。因此，只有当 被排程了， 才能够被加入到Ov中。
4．贪婪规则
应用状态转移规则时，以下的两步贪婪启发规则应用到启发式信息η（σmj）上：
（1）最大工作剩余（MWR）：这一静态方法选择属于一个工件的具有最大剩余操作时间的操作。
（2）时间剩余（TR）：这一动态方法选择与最终结点之间具有最长路径的操作
静态方法与动态方法的一个明显的区别是前者需要提前计算，而后者必须在运行的过程计算，而这样是很耗时的。再者，为了保证构建的排程是动态排程，我们使用插入技术。当人工蚂蚁选择了σmj，我们检验这一操作在机器m上，是否可以在不延迟任何其它操作的基础上尽可能早的被排程。
5．局部信息素更新规则
当一只人工蚂蚁完成了一台机器m的排程后，相应的信息素矩阵应用下式的局部信息素更新规则进行更新：
上式中，τ0是初始信息素值，ρ（0<ρ<1）是信息素挥发因子。局部信息素转移规则的作用是使得其它的码蚁将工序j放到位置p上的可能性减少，以达到多样性。因此，这一机制有利于开发不同的排程。实验证明，不使用这一规则所有的码蚁会在之前最优排程的狭窄的邻域内搜索。
（三）局部搜索阶段
TS启发式算法：TS算法，是由Glover提出的，是用于解决组合优化问题的一种成功的局部搜索算法，简单介绍如下：TS算法从一个初始解开始。在每一次迭代都向邻域中最好的解移动，尽管该解并不一定优于当前解。该算法应用短期记忆存储禁忌表来避免重复，禁忌表用于记录当前移动的固定数字。禁忌表的应用避免了返回到已经访问过的局部最小值。此外，另一种记忆结构长期记忆被用于改进多样性。
（四）全局信息素更新阶段
这一过程在所有的蚂蚁都完成了它们的排程之后进行。为了使搜索更直接，全局信息素更新规则使更好的排程获得更多的信息素。
这一阶段大部分的研究使用精华策略，只允许对当前迭代最优路径释放信息素；但是，这一策略可能不是最好的规则。我们的实验结果显示精华策略可能不适用于JSP。精华策略只适用于少规模的问题，只对最优排程更新常常使的结果不易于收敛，这也就意味着需要高速信息素挥发参数。我们提出了对一系列好的排程（如：前5）进行信息素更新的方法。一旦当前最优排程在局部搜索阶段被改进了，新的最好解将被保存在全局信息素更新队列中。
对全局信息素更新规则下义如下：
上式中，△τm（p，j）是由人工码蚁添加到τm（p，j）上的信息素总量，参数α（0＜α≤1）是信息素挥发率，用于避免信息素无限制地累加并且使得算法能够使得最差的信息素信息消失。R被设为|J|，以从全局信息素更新队列中的排程区分出来。OptValue是优总工期（或最好上界）。
四、仿真实验
本文实验的运行环境是：操作系统为Windows XP，512MB主存，CPU 2.4GHz。程序设计语言为C语言。
试验中均采取30只蚂蚁共循环100次。采取在不同问题下对是否采取局部搜索策略，是否采取启发式信息等情况分别记录，记录数据如表1所示：
五、结论
蚁群算法是一个处于研究初期尚不成熟的算法，很多尝试改进都在不断的进行。这些包括对信息素，启发式信息，状态转移规则，局部搜索算法，信息素更新规则等的改进。实验证明，这些改进对基本算法本身收敛速度慢和早熟等现象都有改善。
本文在参阅前辈的改进意见的基础上，对信息素，启发式信息，状态转移规则，局部搜索算法，信息素更新规则都作了全面的改进，实验结果证明本文进行的改进很好地提高了基本蚁群算法的寻最优解的能力，并很好的改善了蚁群算法易陷入局部最优的情况。
参考文献：
[1]Garey M， Johnson D， Sethi R. The complexity of flow shop and job shop scheduling. Mathematics of Operations Research[J]. 1976， 24(1): 117~129.
[2]Balas E，Vazacopoulos A. Guided local search with shifting bottleneck for job shop scheduling. Management Science 1998;44:26275.
[3]Dorndorf U，Pesch E. Evolution based learning in a job shop scheduling environment. Computers and Operations Research 1995;22:2540.
[4]Colorni A，Dorigo M. The ant system:optimization by a colony of cooperating agents[J].IEEE Transaction on Systems，Man &Cybernetics B， 1996，26(2):29~41.
[5]Michael Pinedo. Scheduling: Theory Algorithms,and Systems[M].Pearson Education，Inc.2000.
[6]Adams J， Balas E， Zawack D. The shifting bottleneck procedure for job shop scheduling. Management Science 1988;34:391401.
作者简介：
于沛欣，男，硕士研究生，山东青岛，主要研究方向：人工智能技术 蚁群算法；丁香乾，男，博士生导师，山东青岛，教授，主要研究方向：制造业信息化技术，计算智能，物流技术。
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”
[关键词]作业车间调度问题蚁群算法禁忌搜索算法转换瓶颈算法
中图分类号：TP3文献标识码：A 文章编号：1671－7597（2008）0510032－02
一、引言
车间调度问题一直是组合优化问题中的一个公认的NP难题[1]，对此问题的解决方案无外乎确定性算法和启发式算法。 确定性方法固然可以得到最优解但是对待规模较小的优化问题起计算是比较现实的，但是对于规模稍大一点的问题确定性算法在现有的条件下近乎是不可能的算法。近年来，启发式用于解决jsp问题取得了一定的成果[2][3]。
蚁群优化（ACO）这个在90年代初产生的群体智能算法[4]，在解决TSP问题中取得了巨大的成功，很快就被尝试用来解决JSP问题，然而结果却不是令人满意的。对于某些问题，例如单机器总权重延迟问题开放车间问题和资源约束项目调度问题，ACO是性能最好的算法之一。而对于其他经典的调度问题如排列流车间问题和作业车间问题计算结果还远逊于当前最先进的算法[5]。
本文针对单独使用蚁群优化来解决车间调度问题的不足，受转换瓶颈算法[6]启发，尝试把蚁群优化与禁忌搜索算法相结合来解决车间调度问题。
二、Job-shop scheduling problem
作业车间调度问题（Job-shop Scheduling Problem，JSP）可描述为：给定一个工件的集合和一个机器的集合，每个工件包括多道工序，每道工序需要上非间断的在一台给定的机器加工一段时间；每台机器一次最多只能加工一道工序；调度就是把工序分配给机器上的一个时间段。问题的目标是找到最小时间长度的调度。
其数学模型可描述如下：给定3个操作集合：O为操作集 ，M是在不同机器上的操作的子集合的集合， J是不同工件上操作的子集合的集合
O={O1，O2，…，Oo}
M={M1，M2，M3，…，Mm}其中Mi 表示在第i台机器上的操作集合
J={J1，J2，…，Jj}其中Ji 表示属于第i个工件的操作集合
JSP可以用图的形式表现出来。构建图除了包括代表每个操作的结点外，还有两个额外的结点作为起始结点和终结点。通常，这些结点之间都是完全连接的。给定一个JSP的实例，可以构建出图G=（V，A，E），其中，V是点的集合，对应着所有操作以及一个起点和一个终点；A是实线弧，表示的是属于同一个工件的操作之间用有向实线连接；E是虚线弧，表示的是同一台机器上执行的操作之间用不带方向的虚线连接。问题的一个可行解就是给图中的无向边选择方向，使得结果图中不带回路。虚线弧确定了方向，也就决定了相对应的机器加工操作的顺序。
三、ACO-TS-JSP算法
蚁群算法的提出借鉴和吸收了现实世界中蚂蚁种群的行为特征：蚂蚁在食过程中能分泌一种称之为信息素(pheromone)的物质，并能利用信息素的轨迹(trail)作为媒介与其它的蚂蚁进行信息沟通．一条路径上留下的信息素轨迹的多少与这条路径上通过的蚂蚁数成正比，当通过的蚂蚁越多，则留下的信息素轨迹就越多，从而导致后来蚂蚁选择该条路径的概率提高．这样，没有视觉能力的蚂蚁在上述过程中展现出了一种协作的自催化行为能力，蚂蚁正是基于此建立最短的移动路径．
本文在对蚁群算法进行改进，将禁忌搜索熔入到蚁群算法中，求解JSP问题，提出了ACO-TS－JSP算法。
（一）初始化阶段
为了减少计算量，我们应用一种简单的静态规则(总机器负载TML规则)来区分瓶颈机器[5]，总机器负载可以提前计算出来。TML规则定义如下:
其中，π（m）是机器m的排序标签。在这一步，对所有的路径赋予初始信息素τ0，τ0是一个相对较小的值。
（二）构建解阶段
1．信息素结构定义
在应用ACO算法之前，一个重要的问题是对信息素进行定义。传统的构建方法是在每一次构建中，只有当一个操作所有之前的操作都已被排程，才会考虑该操作，我们不使用这种方法，我们采用一种分解策略来构建一次排程，这一方法是受SB方法启发得到的。事实上，这种分解方法经常用于JSP问题中。
在我们的方法中，一个|M|×|J|的JSP问题被分解成|M|个独立的SMP，对于其中的每一个，一只蚂蚁逐步构建工序的排列，直到所有的机器都排程完毕。因此，我们对于每一个机器定义了一个|J|×|J|的信息素矩阵。每一个信息素矩阵使用信息素轨迹的绝对位置来定义。（例如，信息素轨迹和一次操作到一个位置的分配相关联），这一方法通常应用于SMP中，并且得到了很好的结果。
2．状态转移规则
在构建阶段，每一只人工蚂蚁在未排程的机器中选择一台具有最高TML的机器。然后，从可行集OV中选择下一步操作，而不是从OM中选择，OV的确定将在下边3.2.3节中详细介绍。我们应用下边的状态转移规则选择下一步操作：
上式中τm（p，j）为从信息素矩阵m中得到的将工序j放到位置p的信息素，是 的贪婪启发式期望值。参数q0（0≤q0≤1）决定了开发与探索之间的相对频率，参数β决定了启发式信息的影响。φ是根据下式给出的概率分布产生出来的一个随机变量：
（1）式和（2）式中的状态转移规则称为伪随机比例规则。这一规则有利于选择具提有提高信息素水平的路径。
3．延迟优先约束
在SB方法中，当几台机器已经被排程了，在给定的未排程的机器上的操作将受到特定的优先约束。这是由于在一台特定机器上的某项操作可能只有当在该机器上的某些相关操作完成后，才可以被排程。ACOFT使用了相似的构建方法因此也遇到了同样的问题。为了保证可行性，我们应用延迟优先约束进行解决，方法如下：在对一台机器m进行排程之前，我们使用深度优先搜索方法得到suc（ ），即所有的 的后继集。如果存在一项操作属于suc（ ），我们就得到一项延迟优先约束（ ）。因此，只有当 被排程了， 才能够被加入到Ov中。
4．贪婪规则
应用状态转移规则时，以下的两步贪婪启发规则应用到启发式信息η（σmj）上：
（1）最大工作剩余（MWR）：这一静态方法选择属于一个工件的具有最大剩余操作时间的操作。
（2）时间剩余（TR）：这一动态方法选择与最终结点之间具有最长路径的操作
静态方法与动态方法的一个明显的区别是前者需要提前计算，而后者必须在运行的过程计算，而这样是很耗时的。再者，为了保证构建的排程是动态排程，我们使用插入技术。当人工蚂蚁选择了σmj，我们检验这一操作在机器m上，是否可以在不延迟任何其它操作的基础上尽可能早的被排程。
5．局部信息素更新规则
当一只人工蚂蚁完成了一台机器m的排程后，相应的信息素矩阵应用下式的局部信息素更新规则进行更新：
上式中，τ0是初始信息素值，ρ（0<ρ<1）是信息素挥发因子。局部信息素转移规则的作用是使得其它的码蚁将工序j放到位置p上的可能性减少，以达到多样性。因此，这一机制有利于开发不同的排程。实验证明，不使用这一规则所有的码蚁会在之前最优排程的狭窄的邻域内搜索。
（三）局部搜索阶段
TS启发式算法：TS算法，是由Glover提出的，是用于解决组合优化问题的一种成功的局部搜索算法，简单介绍如下：TS算法从一个初始解开始。在每一次迭代都向邻域中最好的解移动，尽管该解并不一定优于当前解。该算法应用短期记忆存储禁忌表来避免重复，禁忌表用于记录当前移动的固定数字。禁忌表的应用避免了返回到已经访问过的局部最小值。此外，另一种记忆结构长期记忆被用于改进多样性。
（四）全局信息素更新阶段
这一过程在所有的蚂蚁都完成了它们的排程之后进行。为了使搜索更直接，全局信息素更新规则使更好的排程获得更多的信息素。
这一阶段大部分的研究使用精华策略，只允许对当前迭代最优路径释放信息素；但是，这一策略可能不是最好的规则。我们的实验结果显示精华策略可能不适用于JSP。精华策略只适用于少规模的问题，只对最优排程更新常常使的结果不易于收敛，这也就意味着需要高速信息素挥发参数。我们提出了对一系列好的排程（如：前5）进行信息素更新的方法。一旦当前最优排程在局部搜索阶段被改进了，新的最好解将被保存在全局信息素更新队列中。
对全局信息素更新规则下义如下：
上式中，△τm（p，j）是由人工码蚁添加到τm（p，j）上的信息素总量，参数α（0＜α≤1）是信息素挥发率，用于避免信息素无限制地累加并且使得算法能够使得最差的信息素信息消失。R被设为|J|，以从全局信息素更新队列中的排程区分出来。OptValue是优总工期（或最好上界）。
四、仿真实验
本文实验的运行环境是：操作系统为Windows XP，512MB主存，CPU 2.4GHz。程序设计语言为C语言。
试验中均采取30只蚂蚁共循环100次。采取在不同问题下对是否采取局部搜索策略，是否采取启发式信息等情况分别记录，记录数据如表1所示：
五、结论
蚁群算法是一个处于研究初期尚不成熟的算法，很多尝试改进都在不断的进行。这些包括对信息素，启发式信息，状态转移规则，局部搜索算法，信息素更新规则等的改进。实验证明，这些改进对基本算法本身收敛速度慢和早熟等现象都有改善。
本文在参阅前辈的改进意见的基础上，对信息素，启发式信息，状态转移规则，局部搜索算法，信息素更新规则都作了全面的改进，实验结果证明本文进行的改进很好地提高了基本蚁群算法的寻最优解的能力，并很好的改善了蚁群算法易陷入局部最优的情况。
参考文献：
[1]Garey M， Johnson D， Sethi R. The complexity of flow shop and job shop scheduling. Mathematics of Operations Research[J]. 1976， 24(1): 117~129.
[2]Balas E，Vazacopoulos A. Guided local search with shifting bottleneck for job shop scheduling. Management Science 1998;44:26275.
[3]Dorndorf U，Pesch E. Evolution based learning in a job shop scheduling environment. Computers and Operations Research 1995;22:2540.
[4]Colorni A，Dorigo M. The ant system:optimization by a colony of cooperating agents[J].IEEE Transaction on Systems，Man &Cybernetics B， 1996，26(2):29~41.
[5]Michael Pinedo. Scheduling: Theory Algorithms,and Systems[M].Pearson Education，Inc.2000.
[6]Adams J， Balas E， Zawack D. The shifting bottleneck procedure for job shop scheduling. Management Science 1988;34:391401.
作者简介：
于沛欣，男，硕士研究生，山东青岛，主要研究方向：人工智能技术 蚁群算法；丁香乾，男，博士生导师，山东青岛，教授，主要研究方向：制造业信息化技术，计算智能，物流技术。
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”