• 主题
高级搜索  >
历史搜索 清空历史
首页> 中文学位 >最小化总完工时间的差异平行机批调度算法研究
【6h】

最小化总完工时间的差异平行机批调度算法研究

代理获取
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

生产调度问题是一个相对复杂的组合优化问题，存在于许多应用领域，如铸造业、金属加工业、物流业、通信业等。生产调度的主要任务是在生产过程中通过合理地分配资源，从而提升资源利用率以及生产效率。随着时代发展和技术革新，生产调度问题变得越来越复杂，针对此类问题的研究逐渐拓展到批调度问题。 批调度问题是经典调度问题的拓展，其复杂性在于批处理机一次可以加工多个工件。虽然在批调度问题的求解过程中需要同时考虑工件的分组与调度，增加了问题求解难度，但这极大地提高了生产系统的生产率。 本文首先简单介绍了生产调度问题的相关研究背景，然后按照批调度问题的机器运行环境进行分类介绍，并简要介绍了求解批调度问题的常用算法，包括精确求解算法、启发式算法和元启发式算法。 本文接着针对在差异容量的并行批处理机上加工差异尺寸工件的问题进行研究，以最小化工件的总加权完工时间。在描述所研究问题后给出问题的混合整数规划模型，随后提出了一个求解下界的算法，以评价算法的有效性，并提出了一个启发式算法对问题进行求解。然后，分别基于蚂蚁系统和最大最小蚂蚁系统设计改进算法来解决该问题。在蚂蚁构建解的过程中，采用基于工件权重的首工件选择策略，同时为了降低解构建过程的复杂度，根据当前批的剩余容量构建候选列表以缩小搜索范围。为了有效地指导蚂蚁搜索解，本文基于已构建的候选列表设计了一种新的启发式信息。对于蚂蚁构建解，利用提出的邻域搜索策略进行优化，进一步提高解的质量。 大量的仿真实验对本文提出的算法进行验证，并与两种已有的元启发式算法即随机密钥遗传算法(Random keys genetic algorithm，RKGA)和粒子群算法(Particle swarm optimization，PSO)，进行对比。为了比较机器容量设置对算法性能的影响，本文分别在两种和三种不同机器容量的测试实例上对算法性能进行测试。然后在三种容量的机器上，针对不同容量的机器数组合进行测试，以分析机器容量的分布对算法性能的影响。此外，仿真实验对所提算法中采用的不同策略的有效性进行了验证。 最后对本文的研究工作进行总结，并对未来开展的研究工作做了进一步展望。

著录项

相似文献

  • 中文文献
  • 外文文献
  • 专利
代理获取

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号