A genetic algorithm for robust hybrid flow shop scheduling

Abstract

Most of scheduling methods consider a deterministic environment for which the data of the problem are known. Nevertheless, in reality, several kinds of uncertainties should be considered, and robust scheduling allows uncertainty to be taken into account. In this article, we consider a scheduling problem under uncertainty. Our case study is a hybrid flow shop scheduling problem, and the processing time of each job for each machine at each stage is the source of uncertainty. To solve this problem, we developed a genetic algorithm. A robust bi-objective evaluation function was defined to obtain a robust, effective solution that is only slightly sensitive to data uncertainty. This bi-objective function minimises simultaneously the makespan of the initial scenario, and the deviation between the makespan of all the disrupted scenarios and the makespan of the initial scenario. We validated our approach with a simulation in order to evaluate the quality of the robustness faced with uncertainty. The computational results show that our algorithm can generate a trade off for effectiveness and robustness for various degrees of uncertainty.