基于自然启发式算法的作业车间调度问题理论与应用研究

摘要

调度是影响制造业生产效率的关键因素。采用合理的调度可以缩短工期、减少库存、按时交货和提高信誉。随着全球市场竞争的加剧、客户需求的多样化和个性化，制造系统的调度问题日益受到广泛的重视。
　　 生产调度问题种类繁多，方法多样，其中单件车间调度(Job-Shop SchedulingProblem)是最基本、最著名的机器调度问题，同时也是最困难的NP-hard组合优化问题之一。人们为解决这一难题已经付出几十年的努力，但至今最先进的算法仍很难得到规模较小问题的最优解。近十几年来，通过模拟自然界中生物、物理过程和人类行为过程而发展的元启发式算法，如遗传算法、禁忌搜索、模拟退火、粒子群优化算法、蚁群优化算法等，为解决调度问题提供了新的思路和手段，引起了国内外学者广泛的兴趣。遗传算法和局部搜索算法是目前主要应用于调度的元启发式算法。遗传算法所具有的只根据个体的适应度值进行搜索、较少需要问题相关具体领域知识的特点使遗传算法在生产调度等问题中得到非常广泛的应用。本文改进传统的遗传算法，提出以下三点来解决Job-Shop 问题：一是提出一种全主动调度类型，进一步缩小搜索的解空间；
　　 二是提出了一种基于工序编码的交叉算子POX (Precedence Operation Crossover)，使子代能更好地继承父代的优良特征；三是为克服传统遗传算法存在的早熟收敛问题，设计了一种改进子代产生模式的遗传算法。用基准实例测试改进的遗传算法，试验结果显示该算法能比其他遗传算法更有效地解决调度问题。接着本文研究了局部搜索算法，特别是禁忌搜索算法，在Job-Shop 调度问题中的运用。禁忌搜索算法的优化效率依赖于问题模型，邻域结构和移动评价策略是影响算法搜索效率和解质量的关键因素。本文提出一种新的高效邻域结构，结合适当的移动评价策略和禁忌搜索参数，设计了一种动态强化的禁忌算法。使用该算法对大量的基准实例进行测试，试验结果显示对于矩形基准实例，该算法在质量和效率上可以超越目前其他算法。
　　 最近的许多研究显示单一算法较难解决复杂的调度问题，混合优化算法能提供更强大的搜索能力。然而，到目前为止混合算法仍是一种艺术。调度问题的解空间结构属于非常复杂的“大山谷”(Big Valley)拓扑结构，为了更好地探索调度问题复杂的空间结构、弥补单一算法的不足，本文提出应用自然规律来混合算法，将不同算法进行有机和谐地结合，设计了两种混合优化算法，使算法更深刻地反映问题的本质。应用提出的混合优化算法求解著名Job-Shop 调度基准问题，取得了迄今为止最好的结果，达到了国际水平的前沿。在ABZ、YN、SWV、TA和DMU基准问题的106个未解决实例中，改进了84个实例的当前最好解，有3个实例证明达到最优解。对于最著名的TA基准实例，发布的最好解已被作为最新结果在国外专业网站上公布。通过与已正式发表最好的算法进行比较可看出，对于极困难的Job-Shop 调度问题，混合优化算法在解的质量方面超过目前最先进的算法。
　　 在实际生产环境中，调度问题具有多目标性、多资源性、动态性和随机性等特点。
　　 基于研究传统Job-Shop 调度问题的成功经验，本文对实际生产中广泛存在的调度问题进行了深入研究，在性能指标方面，研究了总拖期时间最小、提前/拖期惩罚代价最小等性能指标；在生产模式方面，研究了柔性作业车间调度问题(Flexible Job-ShopScheduling Problem)、动态调度(Dynamic Scheduling)，并设计了相应的优化算法，如针对柔性作业车间调度问题的特点，提出了一种双层子代产生模式的改进遗传算法；将静态调度问题的成功经验扩展到动态调度问题，提出了一种基于改进遗传算法的滚动调度策略。基于这些研究成果开发出动态调度原型系统，使理论研究能应用于企业创造价值。
　　 作业车间调度是车间制造执行系统(MES)的核心功能之一，合理、有效的作业调度是MES在离散制造业成功应用的关键。在研究车间作业调度问题理论和应用的基础上，本文对单件小批量生产方式的车间作业计划与调度方面的实现方法进行了深入的研究，结合协作企业的应用背景，开发出敏捷化车间制造执行系统(AMES V1.0)，并将AMES与其它的制造资源集成，创建了一个敏捷网络化制造系统集成平台。