智能算法在柔性车间调度中的应用.doc

智能算法在柔性作业车间调度中的应用
摘要:为提高企业生产效率,合理的流水车间生产调度显得尤为重要。本文介绍了三种智能算法(蚁群算法、遗传算法、改进粒子群算法)在车间生产调度中的应用,主要介绍了算法的基本思想、模型结构、算法实现以及运用前景。对智能算法在生产调度中的应用做出总结。
关键字:智能算法;蚁群算法;遗传算法;改进粒子群算法;生产调度

柔性作业车间调度问题(Flexible job-shop sche- duling problem, FJSP)是传统作业车间调度问题的扩展,是实际生产中迫切需要解决的一类问题。在传统的作业车间调度问题中,工件的每道工序只能在一台确定的机床上加工。而在柔性作业车间调度问题中,每道工序可以在多台机床上加工,并且在不同的机床上加工所需时间不同。柔性作业车间调度问题减少了机器约束,扩大了可行解的搜索范围,增加了问题的难度。
作业车间的主要特点是:n个工件需要在m台机器上进行加工,每个工件都有其独特的加工步骤,但无明显的顺序约束,并且加工时间是已知的,调度的目标是在不允许两个工件同时在同一台机器上加工的前提下,如何安排工件在每台机器上的加工顺序使这些工件能够尽快加工完毕[1]。
蚁群算法在作业车间的应用[2]
以3个工件2台机器的问题作为例子,如图1。
图1 三个工件两台机器的JSP问题
为确定先对哪个工件进行加工,需要设置一个初始节点O0,所有的蚂蚁最初都放置在O0。图1中除与O0相连的有向弧表示同一个工件的加工顺序,工件必须按照该顺序进行加工。其它则为无向弧。每个弧与表示节点间信息素的量和启发式距离的一对值{αij , d ij }有关。dij 通常为对节点 j 的第 i 步操作的加工时间,τij 使用蚁周方式进行更新:
其中,ρ是个系数,1−ρ表示在时间t和t+1之间信息素的蒸发,Q为常数,Tk为完成所有加工步骤后最短的总加工时间。初始时刻τij(0)= c(c为常数)。
这个规则包含了两个方面:(1)图1中所有边缘上的信息素都要蒸发;(2)完成所有的加工后要将该解的效果加到各边缘上。蒸发可以防止搜索局限在局部最小的邻域中,另一方面又能根据已有解的效果好坏来更新信息素,进行增强学****br/> 另一个关键的问题就是如何保证蚂蚁按照工件的工艺路线产生一组可行解。这里用到3个集合:对每个蚂蚁 k,首先要有集合G k,表示没有访问过的节点集合;S k 表示根据技术路线下一步允许访问的节点集合;还需要一个禁忌表,存放已经访问过的节点。在我们的例子中, G k ={1,2 ,3,4,5 ,6},S k ={1,2 ,3}。转移概率是通过下式计算的:
Tij 为工件i在机器j上的加工时间。每选择一个节点,该节点就被追加到禁忌表中并从Gk和 Sk中删除;如果被选的节点不是工件的最后一步,那该工件中紧邻的下一个节点会被加到Sk中。该过程一直重复到Gk = φ。最后禁忌表中得到的节点的排列顺序就是蚂蚁 k 找到的解。
参数α和β决定了算法的收敛速度并对解的性能好坏有重要影响,同时蒸发常数也需要进行适当的调整以使搜索能在好的搜索空间中进行,并防止陷入局部最优的邻域中。
蚁群算法已经被成功地运用于10个工件、10台机器和10 个工件、15台机器的JSP例子中,该算法总能得到最优解的 10%以内的解,