Robust scheduling of a two-stage hybrid flow shop with uncertain interval processing times

Abstract

This paper studies the makespan minimisation scheduling problem in a two-stage hybrid flow shop. The first stage has one machine and the second stage has m identical parallel machines. Neither the processing time nor probability distribution of the processing time of each job is uncertain. We propose a robust (min–max regret) scheduling model. To solve the robust scheduling problem, which is NP-hard, we first derive some properties of the worst-case scenario for a given schedule. We then propose both exact and heuristic algorithms to solve this problem. In addition, computational experiments are conducted to evaluate the performance of the proposed algorithms.

Keywords:

• hybrid flow shop scheduling
• makespan minimisation
• min–max regret
• uncertain processing times

Additional information

Funding

This work was partially supported by the National Natural Science Foundation of China [grant number 71172189], [grant number 71071123] and [grant number 61221063]; Program for Changjiang Scholars and Innovative Research Team in University [No. IRT1173], New Century Excellent Talents in University [NCET-12-0824], DHU Distinguished Young Professor Program [number A201305] and the Fundamental Research Funds for the Central Universities.