A tabu search heuristic for preventive maintenance scheduling

In this paper, we present a tabu search based heuristic, PM_TABU, for the p reventive maintenance (PM) scheduling problem. The PM scheduling problem ai ms to maximize the total priority of the scheduled tasks subject to resourc e availability constraints. The heuristic involves three basic moves - addi ng a PM task to the current schedule, dropping a task from the schedule and swapping craft-combinations assigned to a task. The heuristic also incorpo rates the probabilistic intensification and diversification feature introdu ced by Rochat and Taillard (J. Heuristics, 1 (1995) 147). We have tested ou r heuristic on 60 problems used by Gopalakrishnan, Ahire and Miller (Manag. Sci., 43 (1997) 827) in their study. PM_TABU reduces the average optimalit y gap for the test problems from 2.26 (obtained from Gopalakrishnan et ai,, Manag. Sci., 43 (1997) 827) to 0.60%. (C) 2001 Elsevier Science Ltd. All r ights reserved.