We present deterministic and stochastic programming models for the workover rig problem, one of the most challenging problems in the oil industry. In the deterministic approach, an integer linear programming model is used to determine the rig fleet size and schedule needed to service wells while maximizing oil production and minimizing rig usage cost. The stochastic approach is an extension of the deterministic method and relies on a two-stage stochastic programming model to define the optimal rig fleet size considering uncertainty in the intervention time. In this approach, different scenario-generation methods are compared. Several experiments were performed using instances based on real-world problems. The results suggest that the proposed methodology can be used to solve large instances and produces quality solutions in computationally reasonable times.