Drilling Rig Scheduling Problem with Budget Constraints: exact and heuristic solutions

In the oil industry, the discovery of new hydrocarbon accumulations requires selecting exploratory projects and scheduling drilling rigs to execute them. Project selection and rig scheduling are usually handled separately, which may lead to portfolios that are infeasible from an operational perspective. This paper integrates project selection, scheduling, and rig routing in the Drilling Rig Scheduling Problem with Budget Constraints. We present two mixed-integer linear programming formulations and a GRASP-based metaheuristic with RVND local search. Computational results show that exact methods are suitable for small instances, but their performance deteriorates for larger cases. In such instances, the proposed heuristic finds high-quality solutions in short computational times, outperforming CPLEX in all large instances evaluated.