基于EDA的流水车间调度研究

《基于EDA的流水车间调度研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于EDA的流水车间调度研究摘要：在介绍分布式估计算法以及流水车间调度的基础上，利用二次编码方法，提出基于分布式估计算法的流水车间调度算法，并介绍了算法的计算过程，最后给出实例验证。关键词：分布式估计算法；流水车间调度；启发式算法ResearchonFlowShopProblemBasedonEstimationofDistributionAlgorithmsAbstract:OnthebasisofbriefintroductionofEstimationofDistributionAlgorithmsandFlowShopProble

2、m,akindofEDA-basedHowshopalgorithmisproposedthrowthesecondencodingmethod.Anexampleisgiventoexplainthismethodanddemonstratethealgorithmatlast.Keywords:EstimationofDistributionAlgorithms；FlowShopProblem；HeuristicAlgorithms1.引言口从Johnsonl954年发表第一篇关于流水车间调度问题(FPS)的文章以來,FPS引起了许多

3、学者的关注。在过去的儿十年，许多学者对纯流水车间调度问题作了深入的研究，但还没冇一个求解的简明算法。已经证明，3台以上机器的流水布间调度问题就是NP完全问题，至今没有一个多项式复杂性的全局优化算法。已有求解流水车间调度问题的方法一般分为精确方法、构造型方法、改进型方法和神经网络等。整数规划和分支定界技术是寻求流水车间调度问题最优解的常用方法，然而，难以解决一些大规模甚至中等规模的调度问题⑴。2.分布式估计算法分布式估计算法⑵(Estimationofdistributionalgorithms,EDAs)的概念最初在1996年提出，在20

4、00年前后迅速发展，成为当前进化计算领域前沿的研究内容,2005年在进化计算领域的权威国际期刊EvolutionaryComputation上出版了分布式估计算法的专刊，近年来国际上进化计算领域的各大学术会议，如ACMS1GEVOIEEECEC等，都将分布式佔计算法作为重要的专题予以讨论。分布式估计算法提出了一种全新的进化模式。在传统的在传统的遗传算法屮，川种样表示优化问题的一组候选解，种群中的每个个体都冇相应的适应值，然后进行选择、交叉和变异等模拟白然进化的操作，反复进行，对问题进行求解.而在分布估计算法中，没有传统的交叉、变异等遗传操

5、作，取而代之的是概率模型的学习和采样.分布估计算法通过一个概率模型描述候选解在空间的分布，采用统计学习手段从群体宏观的角度建立一个描述解分布的概率模型，然后对概率模型随机采样产牛新的种群，如此反复进行，实现种群的进化，肓到终止条件。根据概率模型的复杂程度以及不同的采样方法，分布佔计算法发展了很多不同的具体遗传算法EDA算法图1GA和EDA的基木流程Fig.lThebasicproceduresofgeneticalgorithmandEDA实现方法，但是都可以归纳为下面两个主要步骤⑶:1)构建描述解空间的概率模型。通过对种群的评估，选择优

6、秀的个体集合，然后采用统计学习等手段构造一个描述当前解集的概率模型。2)由概率模型随机采样产生新的种群。一般的，采用蒙特卡罗方法，对概率模型采样得到新的种群。图1大体归纳了一般分布估让算法的过程⑷，并与遗传算法进行了对比。在分布估计算法中，没有遗传算法中的交叉和变界等操作，而是通过学习概率模型和采样操作使群体的分布朝着优秀个体的方向进化。从生物进化角度看，遗传算法模拟了个体Z间微观的变化，而分布佔计算法则是对生物群体整体分布的建模和模拟。EDA的算法流程如图2所示：图2EDA流程图Fig.2TheproceduresofEDA3.基于ED

7、A的flowshop调度方法研究3.1flowshop简介Flowshop问题是确定性同序作业调度的问题，他研究在寻求全部工件最大完成时间(Fmax)为最小的条件下如何确定n个工件都按同样的工艺顺序经过m台机床的排序,一般记为n/m/P/Fmax,P为I［件在机器上的加工时间。其满足的约束条件如下：(1)一个工件不能同时在不D0的机器上加工；(2)所有的工件在加工过程屮采取平行同顺序的方式移动，即当上一•道工序完成后立即送到下一道工序进行加工；(3)某个工件加工过程中不允许有中断;(4)允许工件在工序之间等待，允许及其在工作上为到达时处于

8、空闲状态；(5)工件的加工时间与加工顺序无关；(6)所有工件在各台机器上的加工顺序相同；(7)每台机器同时只能加工一个工件，不允许多个工件同时在同一台机器上加工；(8)每到工序只能在一台机器上