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