节能双目标平行机批调度问题研究

发布时间：2018-05-07 13:51

本文选题：平行批处理机 + 动态到达　；参考：《安徽大学》2017年硕士论文

【摘要】：生产调度问题是一类复杂的组合优化问题,在实际生活中存在于多个领域,如铸造业、金属加工业、物流、通讯等。对生产调度问题进行研究的主要目的是使得资源在使用过程中进行合理分配,从而提高资源的利用率及生产效率,合理的调度方案可以大幅提升企业的竞争力。随着社会的发展,生产调度问题逐渐变复杂,从经典调度发展到一类新型的调度,即批处理机调度。批处理机调度问题(简称批调度问题)区别于传统调度的主要特征是一台机器在同一时刻可以加工多个工件,工件分组成批后以批为单位在机器上进行加工,每个批中有多个工件,批的加工时间定义为批中所有工件的最大加工时间。批处理问题的复杂程度由工件约束、机器约束以及目标函数决定,然而很多甚至是单机环境下的批调度问题已被证明是NP难的,因此研究者已经往往专注于寻找可行并高效的求解算法。本文简单介绍了生产调度问题的研究背景,再分别对其中的批调度问题从单机、多机、动态环境下和考虑能源消耗这几类批调度问题的研究现状进行概述。随后简单介绍了目前用于解决批调度问题的算法,主要包括确定性算法、启发式和元启发式算法三类,包括三类算法的特点、框架及典型算法的描述。接着,本文探讨了考虑工件到达时间、机器能耗以最小化制造跨度和总的电力成本的平行机批调度问题。首先建立该问题的数学模型,然后提出一种基于Pareto的蚁群优化算法PACO来求解问题。通过分析问题的特征,本文提出两种不同的候选列表来减小蚁群的搜索空间,并基于这两种候选列表分别提出动态的启发式信息来指导蚂蚁的搜索行为。此外,引入了两种针对不同目标的局部优化策略对解进行优化,以进一步提高解的质量。最后给出完整的PACO算法描述以及算法流程图。然后通过仿真实验来验证本文所提算法的性能。本文在非支配解集的解个数、覆盖率等7种评价指标下对所提算法PACO的性能与已有的三种多目标优化算法进行比较实验,并分析了实验结果。实验结果表明,本文提出的PACO算法优于其他三种多目标优化算法,而且在大尺寸工件算例上的优势尤其明显。此外,本文还给出了四种算法在部分算例上所找到的非支配解集的分布图。最后,论文对本文所研究的考虑能耗的双目标平行机批调度问题以及所提出的解决方法进行了总结,并简单介绍了未来进一步研究的方向。
[Abstract]:This paper briefly introduces the research background of scheduling problem , and then puts forward a new algorithm for scheduling problem . The paper introduces two kinds of scheduling problems , such as deterministic algorithm , heuristic and meta - heuristic algorithm .

【学位授予单位】：安徽大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TB497

【参考文献】