A hybrid genetic algorithm for stochastic job-shop scheduling problems

¹ University of Sciences and Technology USTHB, AMCD-RO, BP32, Bab-Ezzouar 16111, Alger, Algeria
² Polytechnic University Hauts-de-France, CNRS, UMR 8201 – LAMIH, F-59313 Valenciennes, France
³ INSA Hauts-de-France, F-59313 Valenciennes, France

^* Corresponding authors: m.boukedroun@univ-dbkm.dz, mboukedroun@usthb.dz
^** david.duvivier@uphf.fr

Received: 19 March 2020
Accepted: 18 May 2023

Abstract

Job-shop scheduling problems are among most studied problems in last years because of their importance for industries and manufacturing processes. They are classified as NP-hard problems in the strong sense. In order to tackle these problems several models and methods have been used. In this paper, we propose a hybrid metaheuristic composed of a genetic algorithm and a tabu search algorithm to solve the stochastic job-shop scheduling problem. Our contribution is based on a study of the perturbations that affect the processing times of the jobs. These perturbations, due to machine failures, occur according to a Poisson process; the results of our approach are validated on a set of instances originating from the OR-Library (Beasley, J. Oper. Res. Soc. 41 (1990) 1069–1072). On the basis of these instances, the hybrid metaheuristic is used to solve the stochastic job-shop scheduling problem with the objective of minimizing the makespan as first objective and the number of critical operations as second objective during the robustness analysis. Indeed, the results show that a high value of the number of critical operations is linked to high variations of the makespan of the perturbed schedules, or in other words to a weak robustness of the relating GA’s best schedule. Consequently, critical operations are not only good targets for optimizing a schedule, but also a clue of its goodness when considering stochastic and robustness aspects: the less critical operations it contains, the better it is.