A hybrid genetic algorithm for stochastic job-shop scheduling problems
Open Access
- 11 July 2023
- journal article
- research article
- Published by EDP Sciences in RAIRO - Operations Research
- Vol. 57 (4) , 1617-1645
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.Keywords
This publication has 104 references indexed in Scilit:
- A fast multicriteria decision-making tool for industrial scheduling problemsInternational Journal of Production Economics, 2013
- IFSJSP: A novel methodology for the Job-Shop Scheduling Problem based on intuitionistic fuzzy setsInternational Journal of Production Research, 2013
- Multicriteria optimisation and simulation: an industrial applicationAnnals of Operations Research, 2007
- A genetic algorithm and the Monte Carlo method for stochastic job‐shop schedulingInternational Transactions in Operational Research, 2003
- A Genetic Algorithm Approach to Solving Stochastic Job‐shop Scheduling ProblemsInternational Transactions in Operational Research, 2002
- The Lack of A Priori Distinctions Between Learning AlgorithmsNeural Computation, 1996
- A comparative study of some priority dispatching rules under different shop loadsProduction Planning & Control, 1995
- An evaluation of the interaction between dispatching rules and truncation procedures in job-shop schedulingInternational Journal of Production Research, 1993
- OR-Library: Distributing Test Problems by Electronic MailJournal of the Operational Research Society, 1990
- Due date selection procedures for job-shop simulationComputers & Industrial Engineering, 1983