The application of mathematical programming for scheduling preventive maintenance in railways is relatively new. This paper presents a stochastic mathematical model designed to optimize and to predict tamping operations in ballasted tracks as preventive condition-based maintenance. The model is formulated as a mixed 0–1 nonlinear program that considers real technical aspects as constraints: the reduction of the geometrical track quality over time is characterized by the deterioration rate of the standard deviation of the longitudinal level; the track layout; the dependency of the track recovery on its quality at the moment of the maintenance operation; the limits for preventive maintenance that depend on the maximum permissible train speed. In the model application, a railway stretch with 51.2 km of length is analysed for a time period of five years. The deterioration model is stochastic and represents the reduction of the standard deviation of the longitudinal level over time. The deterioration rate of the standard deviation of the longitudinal level is simulated by Monte Carlo techniques, considering the three parameters Dagum probabilistic distribution fitted with real data (Vale, Simões 2012). Two simulations are performed and compared: stochastic simulation in space; stochastic simulation in space and time. The proposed condition-based maintenance model is able to produce optimal schedules within appropriate computational times.