基于过滤定向搜索的柔性制造系统动态调度优化

A Filtered-Beam-Search Based Approach for FMS Dynamic Scheduling

针对柔性制造环境中内外扰动的动态随机发生和快速、高效的重调度需求,构建了动态调度决策系统结构模型,提出了一种基于过滤定向搜索的启发式算法作为模型的核心算法.为了更好地搜索调度解空间和更好地集成作业的交货期、优先权重和资源负载平衡,算法改进了节点分枝策略和局部、全局评价函数.以作业交货延迟时间加权平方和最小为性能指标,通过实例仿真,对算法性能进行了分析评价和比较,结果表明了该算法对实现柔性制造系统动态调度的有效性和实用性.

In flexible manufacturing environment, various internal and external disturbances occur stochastically and dynamically and a requirement for fast and effective rescheduling is needed. In such cases, to realize dynamic scheduling effectively, a structure model of dynamic scheduling decision system was presented and a filtered-beam-search based heuristic algorithm was proposed as the kernel of the model. The proposed algorithm makes improvement in the generation procedures of branches and the local/global evaluation functions to search the space solution more effectively, to consider and incorporate the due dates and priority weights of jobs and resource load balance more effectively. Finally, with respect to a due datebased objective （weighted quadratic tardiness）, the performance of the proposed algorithm was evaluated and compared with that of other approaches through simulations, and the results show that the proposed algorithm can generate quite satisfactory reschedule in a very short computational time.