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

Rahimeh Neamatian Monemi, Kassem Danach, Wissam Khalil, Shahin Gelareh*, Francisco C. Lima, Dario José Aloise

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)4493-4505
Number of pages13
JournalExpert Systems with Applications
Issue number9
Early online date4 Feb 2015
Publication statusPublished - 1 Jun 2015
Externally publishedYes


  • arc-time-index formulation
  • branch, price and cut
  • hyper-heuristics
  • workover rig scheduling


Dive into the research topics of 'Solution methods for scheduling of heterogeneous parallel machines applied to the workover rig problem'. Together they form a unique fingerprint.

Cite this