یک جستجوی اکتشافی ممنوعه برای برنامه ریزی نگهداری و تعمیرات پیشگیرانه

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 (J. Heuristics, 1 (1995) 147). We have tested our heuristic on 60 problems used by Gopalakrishnan, Ahire and Miller (Manag. Sci., 43 (1997) 827) in their study. PM_TABU reduces the average optimality gap for the test problems from 2.26 (obtained from Gopalakrishnan et al., Manag. Sci., 43 (1997) 827) to 0.60%.

Maintenance management is a key function used by industrial systems that deteriorate and wear with usage and age. The primary objective of maintenance management is to increase equipment availability and overall effectiveness. Preventive maintenance (PM), a major part of maintenance management, deals with analyzing current equipment to determine the best methods to prevent failure and to reduce repair times. The dynamic nature of an operating environment, such as machine utilization and breakdown frequency, results in changing PM needs for manufacturing equipment. The typical PM problem is to decide which PM tasks to do and when, subject to certain resource constraints. Hence, PM can be classified as a resource allocation and scheduling problem. The literature on PM falls into the following dichotomy: (i) studies focussing on inspection and replacement intervals and (ii) studies that address equipment improvement (McKone & Weiss, 1998). Seminal surveys by McCall, 1965, Pierskalla and Voelker, 1976 and Valdez-Flores and Feldman, 1989 address the first aspect of the dichotomy. Here, the equipment is assumed to fail stochastically and based on whether the actual state is known or not, policies for inspection and replacement are developed. Most of the models consider strictly periodic policies that are optimal only when the planning time horizon is infinite. On the other hand, sequential policies that recalculate the replacement intervals at each inspection/replacement epoch have also been developed for the finite time horizon. The second aspect of PM deals with lengthening the equipment life by being proactive, i.e. intervening before the actual failure/breakdown occurs. The available literature on discrete time maintenance models predominantly treats an equipment deterioration process as a Markov chain. For example, Pate-Cornell, Lee and Tagras (1987) use a semi-Markov model to characterize the deterioration process in a machine shop environment. They consider two types of basic maintenance policies — scheduled PM procedures performed on the process at fixed intervals, and maintenance on demand (i.e. repair) performed based on the signals revealing problems with machines. They analyze the performance of the policies and derive long-run disutilities. Similar approaches have also been discussed in other application environments. For instance, Davis and Carnahan, 1987 and Golabi et al., 1982 discuss the development of maintenance systems for road surface maintenance. Most of these Markov-based approaches predict the future state of equipment based only on the current condition without much regard to past trends in breakdown, usage and maintenance activities. However, Gopalakrishnan, Ahire and Miller (1997) present an approach that uses the historical data on machine utilization, PM, and machine breakdowns to calculate machine failure probabilities and task priorities. They have incorporated these priorities into a task rescheduling binary integer programming (BIP) model to generate an adaptive schedule that maximizes PM effectiveness while satisfying workforce constraints. They have also developed four different local heuristics to yield good solutions to large-scale versions of this scheduling problem. This paper proposes a tabu search based solution procedure, PM_TABU for the PM scheduling problem. Tabu search is a meta-heuristic that makes use of memory structures and exploration strategies based on information stored in memory to search beyond local optima (Glover & Laguna, 1993). The procedure repeatedly moves from a solution to the best among its neighboring solutions. To prevent cycling, the procedure stores recently visited solutions in a continuously updated ‘tabu list’ for a given number of iterations, and does not visit them as long as they are in the list. Several strategies such as diversification and intensification are used to make tabu search an effective and robust procedure (Glover et al., 1998, Glover et al., 1993 and Rochat and Taillard, 1995). Researchers have successfully developed tabu search heuristics for combinatorially difficult problems in several domains such as vehicle routing and flow shop scheduling (Dell'Amico and Trubian, 1993 and Gendreau et al., 1994). PM_TABU moves from one solution to another using one of the three basic moves. The three moves involve adding a PM task to the 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 (1995). We have tested our heuristic on 60 problems used by Gopalakrishnan et al. (1997) in their study. PM_TABU reduces the average optimality gap for the test problems from 2.26 (Gopalakrishnan et al., 1997) to 0.60%. The rest of the paper is organized as follows. In Section 2, we provide a brief description of Gopalakrishnan et al.'s (1997) PM scheduling model and their heuristics. In Section 3, we describe the various components of PM_TABU, and provide a detailed description of the heuristic. Section 4 presents the results of the computational study. Section 5 provides the conclusion.

In this paper, we developed a tabu search heuristic for the PM scheduling problem. The heuristic consists of three basic moves and the concept of probabilistic diversification and intensification. We tested the heuristic on 60 problems from an earlier study and compared the results with the corresponding results obtained using local heuristics. PM_TABU reduces the average optimality gap from 2.26 (obtained using the local heuristics) to 0.60%.