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

《智能算法在柔性车间调度中的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、智能算法在柔性作业车间调度中的应用摘要：为提高企业生产效率，合理的流水车间生产调度显得尤为重要。本文介绍了三种智能算法（蚁群算法、遗传算法、改进粒子群算法）在车间生产调度中的应用，主要介绍了算法的基本思想、模型结构、算法实现以及运用前景。对智能算法在生产调度中的应用做出总结。关键字：智能算法；蚁群算法；遗传算法；改进粒子群算法；生产调度0.前言柔性作业车间调度问题(Flexiblejob-shopsche-dulingproblem,FJSP)是传统作业车间调度问题的扩展，是实际生产中迫切需要解决的

2、一类问题。在传统的作业车间调度问题中，工件的每道工序只能在一台确定的机床上加工。而在柔性作业车间调度问题中，每道工序可以在多台机床上加工，并且在不同的机床上加工所需时间不同。柔性作业车间调度问题减少了机器约束，扩大了可行解的搜索范围，增加了问题的难度。作业车间的主要特点是：n个工件需要在m台机器上进行加工，每个工件都有其独特的加工步骤，但无明显的顺序约束，并且加工时间是已知的，调度的目标是在不允许两个工件同时在同一台机器上加工的前提下，如何安排工件在每台机器上的加工顺序使这些工件能够尽快加工完毕[1

3、]。1.蚁群算法在作业车间的应用[2]以3个工件2台机器的问题作为例子，如图1。图1三个工件两台机器的JSP问题为确定先对哪个工件进行加工，需要设置一个初始节点O0，所有的蚂蚁最初都放置在O0。图1中除与O0相连的有向弧表示同一个工件的加工顺序，工件必须按照该顺序进行加工。其它则为无向弧。每个弧与表示节点间信息素的量和启发式距离的一对值{αij,dij}有关。dij通常为对节点j的第i步操作的加工时间，τij使用蚁周方式进行更新：其中，ρ是个系数，1−ρ表示在时间t和t+1之间信息素的蒸发，Q为常数

4、，Tk为完成所有加工步骤后最短的总加工时间。初始时刻τij(0)=c（c为常数）。这个规则包含了两个方面：(1)图1中所有边缘上的信息素都要蒸发；(2)完成所有的加工后要将该解的效果加到各边缘上。蒸发可以防止搜索局限在局部最小的邻域中，另一方面又能根据已有解的效果好坏来更新信息素，进行增强学习。另一个关键的问题就是如何保证蚂蚁按照工件的工艺路线产生一组可行解。这里用到3个集合：对每个蚂蚁k，首先要有集合Gk，表示没有访问过的节点集合；Sk表示根据技术路线下一步允许访问的节点集合；还需要一个禁忌表，存

5、放已经访问过的节点。在我们的例子中，Gk={1，2，3，4，5，6}，Sk={1，2，3}。转移概率是通过下式计算的：Tij为工件i在机器j上的加工时间。每选择一个节点，该节点就被追加到禁忌表中并从Gk和Sk中删除；如果被选的节点不是工件的最后一步，那该工件中紧邻的下一个节点会被加到Sk中。该过程一直重复到Gk=φ。最后禁忌表中得到的节点的排列顺序就是蚂蚁k找到的解。参数α和β决定了算法的收敛速度并对解的性能好坏有重要影响，同时蒸发常数也需要进行适当的调整以使搜索能在好的搜索空间中进行，并防止陷入局

6、部最优的邻域中。蚁群算法已经被成功地运用于10个工件、10台机器和10个工件、15台机器的JSP例子中，该算法总能得到最优解的10%以内的解，只是该方法的计算复杂性占用了部分执行时间，但我们仍可以认为这是一个比较有希望的结果。2.遗传算法在作业车间调度中的应用2.1遗传算法编码和解码[3]编码与解码是指染色体和调度解之间进行相互转换，是遗传算法成功实施优化的首要和关键问题。对于传统的作业车间调度问题，大多数研究采用基于工序的编码。但是柔性作业车间调度问题不仅要确定工序的加工顺序，还需为每道工序选择一

7、台合适的机器，仅采用基于工序的编码方法不能得到问题的解。因此，对于柔性作业车间调度问题，遗传算法的编码由两部分组成，第一部分为基于工序的编码，用来确定工序的加工先后顺序；第二部分为基于机器分配的编码，用来选择每道工序的加工机器。融合这两种编码方法，即可得到柔性作业车间调度问题的一个可行解。2.1.1基于工序的编码这部分编码染色体的基因数等于工序总数，每个工件的工序都用相应的工件序号表示，并且工件序号出现的次数等于该工件的工序数。根据工件序号在染色体出现的次序编译，即从左到右扫描染色体，对于第k次出现

8、的工件序号，表示该工件的第k道工序。对表1所表示的柔性作业车间调度问题，一个基于工序编码的基因串可以表示为[12213123]，其中1表示工件J1，2和3意义相同。基因串中的3个1依次表示工件J1的3个工序，分别为工序1、工序2和工序3。2.1.2基于机器分配的编码设工序总数为l，工序号分别用1,2,3,⋯,l表示。对于这l道工序，形成l个可选择机器的子集{S1,S2,S3,⋯,Sl}，第i个工序的可加工机器集合表示为Si，Si中元素个数为ni，表示为{mi1,mi2