Investigation of single machine scheduling with scheduled preventive maintenance

Because preventive maintenance is one of the most important routine activities in all factories, includmg scheduled preventive maintenance in job scheduling research is quite practical and usefiil. This research mvestigates single machine job scheduling with scheduled preventive maintenance. These problems can be categorized into two classes — fixed maintenance schedule and flexible maintenance schedule. For the fixed maintenance schedule problems, the makespan, total flowtime, and weighted total flowtime are investigated with single or double maintenance requirements. A flexible maintenance schedule has the mamtenance starting time flexible within a time window. The flexible maintenance schedule problems deal with the similar cases to fixed maintenance schedule problems except a general cost fimction is considered for each of the problems. For each problem, a dynamic progranmung (DP) algorithm is developed to obtain the optimal solution. In addition to the DP algorithms, we developed two heuristic algorithms for each of the double maintenance requirement problems. There are a total of 12 DP algorithms and 12 heuristic algorithms presented in this research. Only one DP algorithm is based upon the 0-1 knapsack problem. The remaining algorithms were either newly developed or modified from previous research. Experiments were conducted to verify the performance of these heuristic algorithms.

The experiment results show that the heuristic algorithms perform very well. The maximum differences from the optimal solution in average performance measures is about 1%.