论文摘要
流水作业是许多实际生产调度问题的简化模型,也是一类典型的NP完全问题。经典流水作业问题研究已经取得大量的研究成果,但这都是基于静态的确定性问题模型,由此造成理论研究同生产实际的巨大差异。本文针对不确定流水作业问题的重调度方法进行了研究,并对影响调度策略的两个核心要素进行了重点探讨。首先,结合调度研究的发展历程系统介绍多种调度求解技术,指出快速的启发式调度策略依然是研究的重点。其次,分析了动态调度理论研究的体系架构,对动态调度策略的核心问题进行分析。针对不确定流水作业问题,结合经典插入启发式算法和事件驱动策略构造了扩展算法。通过仿真,发现优化能力突出的启发式方法在面对不确定问题时可能出现性能的急剧劣化,并指出动态调度策略的关键在于重调度原则和重调度方法。随后,针对重调度原则的研究发现,重调度周期同工件到达的快慢紧密相关,由此给出了重调度周期的设计方法。针对重调度方法,提出了基于工件插入的若干启发式求解策略。通过与常用优先级规则策略的仿真分析,所提方法无论从优化质量还是计算速度方面都取得不错的效果。最后,对全文进行总结,并指出不确定流水调度研究未来可能的研究方向。