Methods, systems, and computer-readable storage media for resource-efficient generation of a workover rig schedule by receiving well data and workover rig data for wells, each well producing oil, determining sets of schedules by, for each schedule in a set of schedules, incrementally: calculating a virtual gain for each well in a set of remaining wells, each virtual gain being a function of a production gain for a respective well, a travel time of a workover rig to travel from a current well to the respective well, a workover time for the respective well, a first parameter applied to the workover time, and a second parameter applied to the travel time, and selecting a well as a next well in a schedule based on a respective virtual gain; identifying, from the sets of schedules, a schedule having a maximum cumulative gain, and outputting the schedule as an optimal schedule.