|
Description:
|
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 % . |