不确定流水作业问题的重调度方法研究

发布时间：2018-12-18 03:33

【摘要】：流水作业是许多实际生产调度问题的简化模型,也是一类典型的NP完全问题。经典流水作业问题研究已经取得大量的研究成果,但这都是基于静态的确定性问题模型,由此造成理论研究同生产实际的巨大差异。本文针对不确定流水作业问题的重调度方法进行了研究,并对影响调度策略的两个核心要素进行了重点探讨。首先,结合调度研究的发展历程系统介绍多种调度求解技术,指出快速的启发式调度策略依然是研究的重点。其次,分析了动态调度理论研究的体系架构,对动态调度策略的核心问题进行分析。针对不确定流水作业问题,结合经典插入启发式算法和事件驱动策略构造了扩展算法。通过仿真,发现优化能力突出的启发式方法在面对不确定问题时可能出现性能的急剧劣化,并指出动态调度策略的关键在于重调度原则和重调度方法。随后,针对重调度原则的研究发现,重调度周期同工件到达的快慢紧密相关,由此给出了重调度周期的设计方法。针对重调度方法,提出了基于工件插入的若干启发式求解策略。通过与常用优先级规则策略的仿真分析,所提方法无论从优化质量还是计算速度方面都取得不错的效果。最后,对全文进行总结,并指出不确定流水调度研究未来可能的研究方向。
[Abstract]:Streamline operation is a simplified model for many practical production scheduling problems, and it is also a typical NP complete problem. A great deal of research results have been made on classical flow operation problems, but all of them are based on static deterministic problem models, resulting in great differences between theoretical research and production practice. In this paper, the rescheduling method of uncertain flow operation problem is studied, and the two core elements that affect scheduling policy are discussed emphatically. First of all, combining with the development of scheduling research, this paper systematically introduces various scheduling solving techniques, and points out that fast heuristic scheduling strategy is still the focus of the research. Secondly, the architecture of dynamic scheduling theory is analyzed, and the core problem of dynamic scheduling policy is analyzed. Based on the classical insertion heuristic algorithm and the event-driven strategy, an extended algorithm is proposed to solve the uncertain flow problem. Through simulation, it is found that the heuristic method with outstanding optimization ability may have a sharp deterioration of performance in the face of uncertainty, and points out that the key of dynamic scheduling policy lies in the rescheduling principle and rescheduling method. Then, the rescheduling period is found to be closely related to the speed of the arrival of the workpiece, and the design method of the rescheduling period is given. For rescheduling method, some heuristic solution strategies based on job insertion are proposed. Through the simulation analysis with the common priority rule strategy, the proposed method has achieved good results in terms of both the optimization quality and the calculation speed. Finally, the paper summarizes the whole paper and points out the possible research direction of uncertain pipeline scheduling in the future.
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2011
【分类号】：TH186

【相似文献】