Article Preview
Top1. Introduction
A good critical resources management on oil industries is a way to obtain competitive advantages. When we consider onshore oil wells, it is important to use rationally the scarcest resources for an effective, safe and profitable extraction.
Onshore oil wells use artificial lift methods performed by expensive equipments operating under hard conditions for a long time. Eventually, these equipments need maintenance services (cleaning, reinstatement and stimulation) to keep the best exploitation as possible. For these maintenance services, companies also use expensive equipments called workover rigs or just rigs.
Given a set of oil wells need of maintenance services, we must schedule all rigs to attend all of them as soon as possible, avoiding a production loss. Figure 1 shows an example with nine wells and two rigs with a possible solution. We know in advance when a well will reduce its production and, dependent on the service required (cleaning, reinstatement and stimulation), there is a time limit for the service. So, in real cases, there is a time window for the service associated for each well.
Figure 1. Workover Rig Scheduling (WRS) problem: (a) nine wells and two rigs (b) a possible solution
According to Aloise et al. (2006), the production loss of each idle well is evaluated as its average daily flow rate under regular operation, multiplied by the number of days that its production is interrupted.
Thus, the Workover Rig Scheduling (WRS) problem consists of finding the best sequence of wells for each workover rig, minimizing the production loss associated with the wells waiting for maintenance service and respecting all required constraints.
This paper proposes a Greedy Randomized Adaptive Search Procedure (GRASP) with Path-Relinking (PR) to find optimal or near-optimal solutions for hard instances proposed in the literature for WRS problem. Our computational results show that GRASP+PR generate better solutions than other approaches reported in the literature.
The paper is organized as follows: WRS problem is briefly reviewed in Section 2. The 0-1 integer linear programming model proposed by Costa and Ferreira Filho (2004, 2005) is presented in Section 3. GRASP+PR is presented in Section 4. In Section 5 we present computational results followed by our conclusions summarized in Section 6.
Top2. Brief Literature Review Of The Wrs Problem
If a WRS instance has only one rig, Smith (1956) showed that the optimal sequencing of wells is obtained when they are in non-increasing order according to the values of 
, where Pi is the production loss per day for the well i and 
is the estimated maintenance service time for the well i. He called this sequence of natural order.
The WRS problem is similar to the scheduling problem of n independent tasks (wells) on m processors (rigs) to minimize the total weighted tardiness counted from the beginning of the time windows (Drozdowski, 1996; Du & Leung, 1990). For just one processor, the problem is strongly NP-hard (Du & Leung, 1990) even for delays with the same weights (wells with the same production loss in our case). The result of Smith (1956) concerns the case without time windows and for this case, the WRS problem is easy.
Noronha et al. (2001) proposed a greedy heuristic algorithm for a variant of the WRS problem. They consider priorities for the well based on production loss and environmental risks corresponding to the service. Thus, the greedy heuristic builds a solution using the priority of each request as greedy criterion. The algorithm was adapted to be inserted in a GRASP.