Solution methods for scheduling of heterogeneous parallel machines applied to the workover rig problem

A novel mathematical model for the workover rig scheduling.Identifying several classes of valid inequalities.Developed a very efficient hyper-heuristic method.Developed a branch, price and cut algorithm for the problem.Work is based on a case study of Petrobras, Brazilian petroleum company. We take into account a parallel heterogenous machine scheduling problem arising in maintenance planning of heterogeneous wells. This problem particularly arises in the context of workover rig scheduling. The oil wells need regular maintenance to ensure an optimal level of production. After oil production being decreased at some wells, appropriate workover rigs with compatible service capacity, are deployed to serve the wells at discrete locations. Every well needs a certain level of maintenance and rehabilitation services that can only be offered by compatible workover rigs. A new mixed integer linear programming model is propose for this problem that is an arc-time-indexed formulation. We propose a heuristic selection type hyper-heuristic algorithm, which is guided by a learning mechanism resulting in a clever choice of moves in the space of heuristics that are applied to solve the problem. The output is then used to warm start a branch, price and cut algorithm. Our numerical experiments are conducted on instances of a case study of Petrobras, the Brazilian National Petroleum Corporation. The computational experiments prove the efficiency of our hyper-heuristic in searching the right part of the search space using the right alternation among different heuristics and confirms the high quality of solutions obtained by our hyper-heuristic.