In this research, a model for optimal PM planning based on reliability is developed and solved for multi-component systems. In the proposed model, the type of PM actions for each inspection period is determined in such manner that the total weighted related costs are minimized while a minimum required system reliability is maintained. The planning horizon is divided into some inspections intervals of equal size. In the beginning of each interval, with respect to the system constraints, one of the following PM actions is suggested for each component: 1) inspection and minimal service, 2) preventive repair and 3) preventive replacement. Each of these activities consumes different resources and has different effect on the system reliability. The PM costs include, repair cost, replacement cost, system downtime cost, and random failure cost. In the optimal PM schedule, the PM actions are determined so that a minimum required reliability is obtained with minimum total PM cost. Since the proposed model has a complex structure, Tabu Search and Simulated Annealing are employed to provide quick solutions. The efficiency of these techniques has been demonstrated by solving a PM scheduling problem for a system with 14 components.