● 摘要
本文以面向实际车间调度问题算法研究为目的，在对车间调度问题的背景，国内外研究现状和车间调度问题的特点进行分析的基础上，提出采用基于ILOG平台，采用约束规划、关键路径、禁忌搜索和任务分派规则相结合的混合算法求解车间调度问题的算法，为求解车间调度问题作出探索。首先，指出车间调度问题的特点。车间生产过程是动态的、非平衡不稳定的，主要表现在生产的零件任务是变化的，车间的设备的运行状态是动态变化的，目标也是多样性的，在生产排成问题中属于NP-Hard难题。传统的方法，比如仿真，遗传算法等等都不能很好的完成对实际车间调度问题给出一个很好的可行解。对动态作业调度的相关理论、方法、模型和工具等进行了详细的论述。参考Jobshop调度问题的数学模型，将本课题的动态特性体现到模型中去。参考国内外对调度问题的诸多研究成果，通过用排队理论、计算复杂度来对各种求解算法进行分析和设计，设计和开发了一种以约束规划为算法主框架，综合关键路径、禁忌搜索和任务分派规则的混合调度算法。然后，基于车间调度的特点和综合国内外研究的方法，考虑到在面向动态作业系统的调度不仅需要在有限的时间内求得高质量的调度结果，并且还需要考虑了零件拖期费用，本文采用基于ILOG的约束规划+关键路径+禁忌搜索+启发式任务分派规则算法框架。并叙述在此求解思路上如何利用ILOG平台进行软件实现，提出数据模型，对象模型和算法框架。最后，通过某航空工厂的数据进行实例验证，通过不同算法对同一试验样本进行调度的结果对比，证明了本文算法在模型、调度策略和算法的正确性和实验系统的有效性。最后对全文进行了总结，并给出下一步研究的方向。