• CN:11-2187/TH
  • ISSN:0577-6686

机械工程学报 ›› 2015, Vol. 51 ›› Issue (11): 99-108.doi: 10.3901/JME.2015.11.099

• 数字化设计与制造 • 上一篇    下一篇

考虑工时不确定的混合流水车间滚动调度方法

张洁, 秦威, 宋代立   

  1. 上海交通大学机械与动力工程学院
  • 出版日期:2015-06-15 发布日期:2015-06-15
  • 基金资助:
    国家自然科学基金资助项目(51275307)

Rescheduling Algorithm Based on Rolling Horizon Procedure for a Dynamic Hybrid Flow Shop with Uncertain Processing Time

ZHANG Jie, QIN Wei, SONG Daili   

  1. School of Mechanical Engineering, Shanghai Jiao Tong University
  • Online:2015-06-15 Published:2015-06-15

摘要: 针对加工时间不确定的混合流水车间动态调度问题,提出一种基于滚动窗口的改进蚁群算法。为实现对事件驱动机制下重调度发生频率的有效缓冲,设计基于交货期偏差容忍度的滚动调度策略。同时为提高调度算法的计算效率,以应对现实生产中工时偏差的频繁发生,在滚动时域分解方法框架下提出一种改进的蚁群算法。一方面,通过压缩蚂蚁可选路径限制其移动范围,在缩短蚂蚁搜索周期的同时寻求新的解;另一方面,通过适当刺激蚂蚁尝试具有较弱信息素路径,提高所得解的全局性。通过实例仿真,分别对滚动调度策略和动态调度算法性能进行分析验证,得出较优的滚动调度策略参数,并验证了算法的优越性。最后给出实际生产算例,验证了滚动调度方法的有效性。

关键词: 工时不确定, 滚动调度, 混合流水车间, 蚁群算法

Abstract: To solve the rescheduling problem of dynamic hybrid flow shop with uncertain processing time, an effective algorithm based on the rolling horizon procedure is proposed. In order to reduce the frequency of rescheduling, a rolling horizon driven strategy based on due date deviation tolerance is designed. As the uncertain processing time is a frequent event, the computational efficiency of the scheduling algorithm is necessarily high. Based on the rolling horizon procedure, an improved ant colony optimization is proposed. On one hand, a strategy of reducing the available routes of ants is used to restrict their movement so as to reduce ants’ searching cycle and find new solutions. On the other hand, illuminating function in state transfer possibility is improved to facilitate the exploration of low pheromone trail. Performance of rolling horizon procedure and rescheduling algorithm are evaluated respectively through simulations, the results show the best parameters of rolling horizon procedure and demonstrated the feasibility and efficiency of rescheduling algorithm. An example from the practical production is addressed to verify the effectiveness of the proposed approach.

Key words: ant colony optimization, hybrid flow shop, rolling horizon procedure, uncertain processing time

中图分类号: