ROBUST OPTIMIZATION ALGORITHMS FOR THE FLOW SHOP AND JOB SHOP SCHEDULING PROBLEMS WITH RANDOM FAILURES AND PREVENTIVE MAINTENANCE

Abstract

Inspired by a real-life problem in the kitchen cabinet manufacturing industry, this thesis proposes a suite of algorithms for solving the flow shop and the job shop scheduling problems (FSP & JSP) with both scheduled (preventive) maintenance and random breakdowns. These algorithms aim at obtaining schedules that strike a good balance between performance quality (i.e., shortest expected makespan) and solution robustness (i.e., least affected by breakdowns).

The proposed scheduling framework approximates the fitness function of the original problem using three surrogate functions. The first considers only the actual jobs, the second adds scheduled maintenances and the third adds both scheduled maintenances and deterministic breakdowns based on the mean time to failure of machines. For the FSP, a local optimum solution of each surrogate problem is found either through a local search heuristic or a simulated annealing algorithm. For the JSP, given the extremely large search space, a genetic algorithm is used to find local optimal solutions. These solutions are then simulated with random breakdowns and the best among them is compared to the incumbent solution of the original problem. In different variants of the algorithm, it either terminates once the new solution is found to be worse than the incumbent, or non-improving solutions are accepted, yet with a decreasing probability, in a simulated annealing style.

The first algorithm of the FSP showed no improvement over the initial solution for the 25-machine, 75-job problem. The second algorithm did not perform well due to premature termination. The third algorithm showed marginal improvement with an average of 1.25% over the initial solution with a much higher average run time. The first algorithm for the JSP showed an average marginal improvement of 5.33% and a quick run time of 10.01 minutes for the 50-job, 15-machine problem. The second algorithm showed good performance with an average improvement of 6.71% in an average time of 5.11 hours. These results show that the proposed framework can generate high-quality schedules while taking scheduled maintenance and random breakdowns into consideration.