基于蚁群优化算法的批调度问题研究

摘要

批调度问题是一类重要的现代生产调度问题。在理论上，批调度问题突破和扩展了经典调度理论，它打破了经典调度中对机器加工工件数目的约束，是一种新型的生产调度研究方向。在生产实践中，批调度问题是从半导体生产过程的最后阶段提炼出来的新型调度问题，具有极强的应用背景。同时批调度问题也是一类经典的NP-难问题。因此，设计一种简单高效的求解算法是批调度问题研究的重要方面。
　　 蚁群优化算法是近年来提出的一种有效的求解组合优化问题的元启发式算法。它是一种基于构建性的元启发式算法，在搜索过程中通过不断向部分解添加符号定义的解成分从而构建出一个完整解。从这个意义上说，批调度问题的分批特性非常适合蚁群优化算法求解。除此之外，蚁群优化算法还是基于种群的和具有记忆存储的元启发式算法，这些特征的组合使得蚁群优化算法在理论上求解批调度问题具有独特的优势。但在实际应用上，蚁群优化算法也出现了运算时间较长、易陷入局部最优等缺点。因此本文基于对批调度问题的结构分析，提出了进一步改善算法性能的策略与技术，从而提高了蚁群优化算法求解批调度问题的质量和效率。
　　 本文以批调度问题为研究对象，以设计求解该类问题的有效算法为研究重点，提出了求解不同类型的批调度问题的蚁群算法。具体的说，本文的主要研究内容及创新点包括：
　　 1.研究了蚂蚁系统（ant system，AS）算法在差异工件单机批调度问题中的应用。首先建立了差异工件单机批调度问题的数学模型，并给出了已有的启发式算法和问题下界。针对不同的编码方式，提出了基于工件序列和基于批序列的两种蚂蚁系统算法。考虑目标为总完工时间的特点，引入批权重的概念构建蚂蚁系统算法的启发式信息；同时通过设置不同的信息素初始值，采用局部优化技术等改进措施，克服传统蚂蚁系统算法收敛速度慢，易陷入局部最优的缺点。通过全面的对比实验，结果表明了算法的有效性，尤其是基于批序列的蚁群算法效果更优。2.研究了最大最小蚂蚁系统（max-min ant system，MMAS）算法在工件含不同到达时间的单机批调度问题中的应用。首先建立了问题的混合整数数学模型。针对工件到达时间不同的特点，在算法构建可行解的阶段，依据是否延迟当前批的加工提出了两种候选列表，并给出了延迟当前批加工的约束条件。同时考虑不同候选列表中的工件对解的构造具有不同的影响，分别针对各自候选列表设计了相应的启发式信息。通过与标准蚂蚁系统算法以及带不同候选列表的最大最小蚂蚁系统算法的对比实验，验证了提出的带候选列表的算法的有效性。
　　 3.研究了蚁群系统（ant colony system，ACS）算法在含不同到达时间差异工件单机批调度问题中的应用。首先建立了该问题的混合整数数学模型，并使用运筹学软件CPLEX对该模型进行求解。通过分析工件到达时间和工件尺寸对优化目标的影响，提出了空闲空间的概念，并证明极小化批序列空闲空间等价于极小化批序列最大完工时间。基于此设计了ACS 算法的动态启发式信息以更精确的指导蚂蚁行为。同时引入候选列表策略，有效地优化蚂蚁的寻优空间，提高算法收敛速度。通过与CPLEX软件、遗传算法的对比分析，实验结果表明了算法的有效性，本文提出的算法可在合理的时间范围内取得满意解。
　　 4.研究了多目标蚁群优化(multiple objective ant colony optimization,MOACO)算法在平行机批调度问题中的应用。首先建立了多目标平行机批调度问题的数学模型；针对极小化最大完工时间和极小化最大延误时间两个优化目标，分别提出了空闲空间和延误空间的概念，并基于此设计了MOACO 算法的启发式信息和候选列表。在解的构建阶段，利用MOACO 算法构建性的特点，设计了一种新的构建可行解的机制，该机制使得分批、分机器以及批排序等三个步骤简化到一个步骤，提高了算法的优化效率。通过对Pareto 解的质量、多样性以及算法时间性能等多方面的实验评估，验证了算法的有效性。
　　 总之，批调度问题研究不仅在理论上还是在实践中都有重要的意义。由于本文研究的批调度问题均是NP-难问题，因此对它的求解算法的研究非常重要。在本文中，首先研究了差异工件、工件含不同到达时间等约束条件下的单机批调度问题，之后将单机单目标批调度问题扩展到更复杂也更接近实际生产环境的平行机多目标批调度问题。对于不同类型的批调度问题，首先建立批调度问题的数学模型，提出批调度问题的有效下界，并设计高效合理的蚁群优化算法进行求解。针对传统蚁群优化算法搜索时间较长，易陷入局部最优等缺点，本文在深入分析批调度问题结构的基础上，通过设计合理的信息素和启发式信息，构建基于约束条件和优化目标的候选列表，改进信息素的更新方式，加入局部搜索等优化策略，提高了蚁群优化算法的求解质量和效率。可见，本文的研究内容是相互联系逐步递进的，本文的研究成果为批调度问题的研究提供了一些新的理论和方法，同时也拓展了蚁群优化算法的理论研究和应用研究的领域。

目录

文摘

英文文摘

声明

第1章绪论

第2章蚁群优化算法

第3章差异工件单机批调度问题的蚂蚁系统算法设计

第4章含到达时间批调度的最大最小蚂蚁系统算法设计

第5章含到达时间差异工件批调度的蚁群系统算法设计

第6章平行机批调度问题的多目标蚁群优化算法设计

第7章总结与展望

参考文献

致谢

在读期间发表的学术论文与取得的其他研究成果