In this paper, we present a tabu search based heuristic, PM–TABU, for the preventive maintenance (PM) scheduling problem. The PM scheduling problem aims to maximize the total priority of the scheduled tasks subject to resource availability constraints. The heuristic involves three basic moves – adding a PM task to the current schedule, dropping a task from the schedule and swapping craft-combinations assigned to a task. The heuristic also incorporates the probabilistic intensification and diversification feature introduced by Rochat and Taillard. We have tested our heuristic on 60 problems used by Gopalakrishnan, Ahire and Miller in their study. PM–TABU reduces the average optimality gap for the test problems from 2.26 (obtained from Gopalakrishnan et al. in their 1997 paper) to 0.60%.
