蚁群优化算法在平行机批调度问题中应用及的研究

《蚁群优化算法在平行机批调度问题中应用及的研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据摘要生产调度问题是一类组合优化问题，应用背景十分广泛，其研究成果已经较为丰富，并且己被应用到许多现实的生产实践中。与经典调度问题不同的是，在批处理机调度问题中，多个工件可以同时在一台机器上加工，只有满足容量约束的工件才能在该机器上加工。所以批调度问题更加接近实际，对批处理机调度问题的深入探索和研究具有十分重要的意义。首先，本文简单介绍了生产调度问题的产生背景、与调度问题有关的概念并简单介绍了调度问题的分类；然后简单介绍了批处理机调度问题、差异工件尺寸的批处理机调度问题及动态环境下差异工件尺寸的批处理机调度问题以及这几类问题的研究现状。第二，本文简单介绍了

2、当前用于求解批处理机调度问题的两种主流方法，即确定性方法和近似性方法，然后对这两种主流方法的特点做了简要的分析并且简单介绍了这两种主流方法的代表性算法及其大致框架。第三，在容量差异的平行批处理机环境下，针对工件带有差异尺寸以及机器适用限制的最小化制造跨度的批调度问题，提出一种有效的蚁群优化(AC01)算法。首先给出了问题假设并且分析了问题的复杂性。为了衡量算法的性能，给出问题的一个有效下界。然后提出基于MultiFit规则的启发式算法以及基于AC01的元启发式算法分别对问题进行求解。在基于AC01的算法中，根据解的浪费空间与问题目标的相关性分析，基于浪费空间定义

3、启发式信息来指导蚂蚁的行为。同时，采用候选集策略来构建解，以减小搜索空间。此外引入一种局部优化方法对蚂蚁所构建的解进行优化，以进一步提高解的质量。最后，通过仿真实验比较所提算法与其他已有算法的性能，实验结果表明所提的AC01算法优于其他算法。第四，在容量不同的平行批处理机环境下，针对工件动态到达且差异工件尺寸以及机器适用限制的最小化制造跨度的批处理机调度问题，提出一种有效的蚁群优化(AC02)算法。除了在静态批调度问题中使用的策略之外，在构建的过程万方数据中采用ERT规则对机器集合中每台机器上已有的批序列排序，从而减少工件到达时问对解的影响。此外引入一种局部优化

4、策略对蚂蚁所构建的解进行优化，以进一步提高解的质量。最后，通过仿真实验比较所提算法与其他已有算法的性能，实验结果表明所提的AC02算法优于其他算法。最后，总结了本文所研究的批调度问题以及所提出的解决方法，然后对本文所研究的批调度问题在未来的更进一步的方向做了展望。关键字：平行批处理机；差异尺寸工件；动态到达；不同机器容量；机器适应限制；蚁群优化算法万方数据AbstractAsatypeofcombinatorialoptimizationproblems，productionscheduling，withplentifulresearchresults，hasb

5、eenwidelyappliedinpractice．Differentfromclassicalschedulingproblem，morethanonejobcanbeprocessedononesinglebatchingprocessingmachine(BPM)atthesametime．AnyjobonlyifsatisfingtheconstraintscanbeprocessedontheBPM．Thus，thebatchingschedulingisclosertothepracticalproductionscheduling．Itisofg

6、reatsignificancetoexploreandinvestigatethebatchingschedulingproblemdeeply．Firstly,thispaperbrieflyintroducesthebackgroundandconceptsassociatedwithproductionschedulingproblems，aswellastheclassificationofschedulingproblems．Then，thebatchingschedulingproblemandthosewithadditionalconstrai

7、nts，suchasnon—identicaljobsizesanddynamicarrivaljobs．Theresearchstatusoftheseproblemsisalsopresented．Secondly,twoprevalentapproachesforbatchingschedulingandtheircharactersticsaredescribed，i．e．，thedeterministicmethodandtheapproximatemethod．Sometypicalalgorithmsandtheirframeworksamongt

8、hetwocategor