In this work, we focus on the Periodic Preventive Maintenance Problem (PPMP) that can be defined by: 𝑇 a set of cyclic horizon and 𝑀 a set of machines to maintain over 𝑇. The main objective of this problem is to find a maintenance schedule where in each period, only one machine can be maintained. Moreover, all the machines must be maintained at least once over the planning horizon. In each period 𝑡, if the machine 𝑖 is maintained then it generates a servicing cost, otherwise it generates an operating cost. This problem has already been addressed by Grigoriev et al. (2006). However, in our contribution we extend this work by proposing a new model that integrates the spare parts inventory management and the periodic preventive maintenance scheduling. This problem will be studied as “on the joint optimization of the periodic preventive maintenance and the spare parts inventory problem” (PPMSPIP) as defined by Mjirda et al. (2016). This problem is known to be NP-hard. To solve it we propose a new mat-heuristic approach on which the Variable Neighborhood Search (VNS) meta-heuristic is combined with a Mixed-Integer Linear Programming (MILP). A detailed experimental study is performed to illustrate the performance of the proposed approach.