A Grasp with Path-Relinking for the Workover Rig Scheduling Problem

A Grasp with Path-Relinking for the Workover Rig Scheduling Problem

Alexandre Venturin Faccin Pacheco (Federal University of Espírito Santo – UFES, Brazil), Glaydston Mattos Ribeiro (Federal University of Espírito Santo – UFES, Brazil) and Geraldo Regis Mauri (Federal University of Espírito Santo – UFES, Brazil)
Copyright: © 2012 |Pages: 14
DOI: 10.4018/978-1-4666-1574-8.ch005
OnDemand PDF Download:
No Current Special Offers


Onshore oil wells depend on special services like cleaning, reinstatement and stimulation. These services, which are performed by a short number of workover rigs, are important to keep oil production as optimum as possible. Consequently, scheduling must be determined, where several factors interfere, such as production, service to be performed on each well, and time windows for each service. When a well needs service, its production is interrupted. In this regard, the workover rig scheduling problem consists of finding the best sequence of wells, which minimizes the production loss associated with the wells waiting for maintenance. In this paper, the authors present a Greedy Randomized Adaptive Search Procedure (GRASP) with Path-Relinking (PR) to solve this problem. Computational results are obtained from real problems of a Brazilian oil field.
Chapter Preview

1. 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.


2. 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 978-1-4666-1574-8.ch005.m01, where Pi is the production loss per day for the well i and 978-1-4666-1574-8.ch005.m02 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.

Complete Chapter List

Search this Book: