This paper solves a new model of preventive maintenance scheduling with novel methodology. The aim of solving this problem is to determine the period for which bag filter should be taken off line for planned preventive maintenance over a specific time horizon and maintain a certain level of reliability with minimal maintenance cost. A mathematical programming method (Benders' decomposition) and a metaheuristic algorithm are presented to provide solutions. The obtained objective value from Benders' decomposition method is considered as the stopping criterion in the metaheuristic algorithm. To demonstrate the significance and originality of the proposed model and the efficiency of the algorithms, computational analysis is provided to realistic bag filters system in the cement factory. The obtained result is a schedule that allows the cement factory to consider the preventive maintenance for bag filters over the time horizon.