In this paper, we analyse a railway industry driven scheduling problem concerning monthly assignment of jobs to vehicles in a given time horizon to optimize cost criteria implied by cyclic preventive maintenance activities. Due to the intractability of the problem and the immense search space cardinality of practical instances, we propose local metaheuristic algorithms that are based on various local search techniques. To verify their efficiency, we perform the number of simulation experiments relying on real-life data revealing the high accuracy of our implementations in decreasing costs and increasing revenue in reference to fixed assignments, thereby having a potential to be applied in industry.