Robust job shop scheduling with machine unavailability due to random breakdowns and condition-based maintenance

Abstract

This paper presents a novel solution approach for a variant of the job shop scheduling problem with machine unavailability due to both condition-based preventive maintenance and corrective maintenance following random breakdowns. We first provide an exact mathematical formulation of the problem under simplifying assumptions, namely that the number of breakdowns for each job position on each machine is known, the degradation rates are fixed, and the preventive and corrective maintenance durations are deterministic parameters. Moreover, to handle the more realistic case of stochastic machine degradation, random breakdowns, and uncertain maintenance durations, a simulation-optimisation algorithm is proposed. The real makespan function is first approximated using multiple surrogate measures, which are optimised through independent genetic algorithms. Then, the fittest solutions obtained from these surrogate measures are simulated, and the best among them is added to an elite list, which is included in the genetic algorithms' populations for the next iteration. Schedule robustness is ensured by using an objective function that consists of the weighted average of the expected makespan and its 90th percentile. Furthermore, to reduce the likelihood of falling into a local optimum, a stopping criterion based on simulated annealing is implemented. Numerical experimentation on extended benchmark instances confirmed the validity of the mathematical formulation and the favourable performance of the proposed simulation-optimisation algorithm in terms of computational time and solution quality.

KEYWORDS:

• Robust job shop scheduling
• condition-based maintenance
• random breakdowns
• surrogate functions
• genetic algorithm
• simulation-optimization

Data Availability Statement

The data that support the findings of this study are available from the corresponding author, upon reasonable request.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Notes on contributors

Md Hasan Ali

Md Hasan Ali earned his Bachelor of Science in Industrial & Production Engineering from Khulna University of Engineering and Technology. He was working as a lecturer in the Department of Industrial and Production Engineering at Bangladesh Army University of Science and Technology, Bangladesh. In 2022, he graduated from Dalhousie University with a Master of Applied Science in Industrial Engineering. His research interests include optimisation, scheduling, and maintenance planning.

Ahmed Saif

Dr. Ahmed Saif, P.Eng, Ph.D., is an Associate Professor in the Department of Industrial Engineering at Dalhousie University. He received his Ph.D. in Management Sciences from the University of Waterloo, M.Sc. in Engineering Systems and Management from Masdar Institute of Science and Technology, Abu Dhabi, UAE, MBA from New York Institute of Technology and B.Sc. in Production Engineering from Alexandria University. His research interests include large-scale optimisation, robust optimisation and data analytics methods and their applications in hybrid renewable energy systems and sustainable supply chain problems.

Alireza Ghasemi

Dr. Alireza Ghasemi P.Eng, Ph.D., is an Associate Professor at the Department of Industrial Engineering of Dalhousie University, Halifax, Canada. He holds a Ph.D. in Industrial Engineering from École Polytechnique de Montréal in Canada. He also holds a M.Sc. degree from École Polytechnique de Montréal, a M.Sc. Degree from Sharif University of Technology in Iran, and a B.Sc degree from Isfahan University of Technology in Iran, all in Industrial Engineering. His research field is planning, scheduling and optimisation of Condition Based Maintenance.