An improved hybrid metaheuristics and rule-based approach for flexible job-shop scheduling subject to machine breakdowns

This article proposes an improved hybrid heuristic algorithm to handle the flexible job-shop scheduling problem subject to machine breakdowns. An initial prescheduling sequence is generated by a genetic algorithm. In the rescheduling process, the generated sequence with an uncertain repair time is modified by three typical adjustments of the route-change and the right-shift: (1) the route-change and the right-shift are combined to gain the best improvement; (2) one operation can be inserted after the last operation on any machine that has no impact on the related operations to improve the final solution; and (3) the lowest cost modification option is chosen to generate a new schedule to adapt to breakdown. The objective of these adaptive methods is to reduce the makespan and idle time of each machine when a random failure happens. Experimental results are evaluated to confirm the advantages of the developed algorithm.