In this paper we study the periodic maitenance problem (PMP). The problem is to determine, for a set of m machines and a period of T units of time, a maintenance schedule which will be indefinitely repeating itself. At each period, at most one machine can be serviced. However for any cycle, all the machines must be serviced at least once. In each period the machine M[i] generates a servicing cost b[i] or an operationg cost a[i] which depends on the last period M[i] was serviced. The operating cost of M[i] in a period equals ai times the number of periods since the last servicing of that machine. We study the problem of scheduling maintenance services. The main objective is to find a cyclic maintenance schedule of a periodicity T that minimizes total cost. We propose a new formulation of this problem and a heuristic solution based on General Variable neighbourhood search (GVNS). The performance of this heuristic is shown through an extensive experimentation on a diverse set of problem instances.