An ILS heuristic for the ship scheduling problem: application in the oil industry

• Author: Iuri Santos,Silvio Hamacher,Luciana Pessoa,Victor Cunha
• DOI: http://doi.org/10.1111/itor.12610
• Published date: 01 January 2020
• Date: 01 January 2020

Intl. Trans. in Op. Res. 27 (2020) 197–218

DOI: 10.1111/itor.12610

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

An ILS heuristic for the ship scheduling problem: application

in the oil industry

Victor Cunha, Iuri Santos, Luciana Pessoa and Silvio Hamacher

Industrial Engineering Department/DEI/Puc-Rio, Marquˆ

es de S˜

ao Vicente, 225 – G´

avea, Rio de Janeiro22430-060, Brazil

E-mail: victor.cunha@tecgraf.puc-rio.br [Cunha]; iuri.santos@tecgraf.puc-rio.br [Santos];

lucianapessoa@puc-rio.br [Pessoa];hamacher@puc-rio.br [Hamacher]

Received 31 October 2017; receivedin revised form 16 July 2018; accepted 17 October 2018

Abstract

This paper addresses a real-life rescheduling problem of a pipe-laying support vessel (PLSV) fleet in charge

of subsea oil well connections. The short-term schedule of these vessels is subject to uncertainties inherent

to its operations, resulting in ships idleness or delays in oil production. The objective of this study is to

develop methods to support a Brazilian oil and gas company in overcoming impacts caused by operational

disruptions, while reaching its planned production level. The PLSV rescheduling problem was treated as an

identical parallel machine scheduling problem, where the machines represent the vessels and the jobs are the

activities for the subsea well connections. We propose a mathematical programming model and a method

based on the iterated local search (ILS) metaheuristic to solve the problem. This paper contributes to this by

considering simultaneously setup times, machine eligibility, release dates, due dates, and machine availability.

Both methods were applied on 10 instances based on real PLSV data. Taking into account an objective

function that measures the operational impact on schedules, the ILS provided an average improvement

above 91% in schedules when compared to the initial solution provided by the studied company. The ILS

outperformed a mathematical programming model for the problem, in eight instances, within a 30-minute

execution time limit, fitting to the company process.

Keywords:oil industry; ship scheduling; iterated local search; metaheuristics; mixed integer linear programming

1. Introduction

The offshore oil and gas exploration and production (E&P) presents a challenging problem due

to the factors such as climatic conditions in the marine environment and long distances between

the platforms and maritime terminals. These factors are more critical in Brazil’s pre-salt layer

exploration, which operates within water depths more than 2000 m (Morais, 2013). Furthermore,

uncertainties related to oil demands,prices in domestic and international markets, and in production

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

198 V.Cunha et al. / Intl. Trans. in Op. Res. 27 (2020) 197–218

capacity have a huge impact on the operational decisions involving the entire oil production supply

chain (Oliveira and Hamacher, 2012).

In offshore operations, oil and gas are drained to surface platforms through production lines,

or pipelines, connected to submarine wells (Speight, 2014). Pipe-laying support vessels (PLSVs)

are responsible for transporting, laying out, and connecting these pipelines (Serpa, 2012). Such

connections represent one of the most important tasks that surrounds the offshore oil and gas E&P,

because it is the last step to be carried out before a well starts its operation. Delays at the start of

the well production lead to financial impacts that can reach one million dollars per day.

The dynamic environment where these operations occur creates process disruptions that affect

the PLSV schedule, when compared to the original planning developed by the company. In this way,

rescheduling is necessary in order to minimize the cost impact caused by these disruptions.

The motivationfor this research comes from a real ship rescheduling problemof a Brazilian oil and

gas company, which needs to reschedule a PLSV fleet operating on the pre-salt basin. The objective

is to minimize the impacts caused by operational disruptions, thus maximizing its production of

oil and gas, according to an original annual schedule. The available fleet is chartered from different

outsourced companies, through long-term contract agreements, responsible for managing sets of

vessels, according to the schedule informed by the company.

The current PLSV scheduling process is done manually by specialists from the company without

any decision support tool. The operationof an entire year is originally scheduled, and the production

start dates of the wells are defined based on it. The rescheduling is done weekly and deals with

the short-term operation, which considers the three months subsequent to the analyzed week. We

propose a mathematicalmodel and a heuristic based on the iterated local search (ILS) metaheuristic

(Lourenc¸o et al., 2010) for rescheduling the PLSVs efficiently so that the wellsmeet their production

start dates based on the original schedule, while avoiding idleness time, respecting the availability

of each vessel, and keeping most of its allocation characteristics.

Queiroz and Mendes (2011) and Moura (2012) addressed the PLSV scheduling problem, mod-

eling it as a parallel machine scheduling problem. Our approach differs from the previous ones

mainly by considering the real problem that the company has to deal with. In this way, the vessel

availability,capacity, and eligibility constraints were considered together with activitypriority rules,

their respective release dates, and setup times to be considered before their execution.

The remainder of this paper is organized as follows. In Section 2, the problem is described.

In Section 3, a mathematical model is presented and an ILS-based heuristic is customized for the

studied problem. In Section 4, the computationalexperiments are detailed. Initially the results of the

mathematical programming are displayed, followed by the parameterization stage of the proposed

ILS, and then its final results. A comparison between the results obtained by the heuristic and exact

method is also done in this section. Finally, Section 5 contains the conclusion of the paper.

2. Problem description

The PLSV rescheduling problem can be modeled as an identical parallel machine scheduling prob-

lem (Pm),which consists of njobs (1≤j≤n)tobeprocessedinmmachines (2≤i≤m), so that each job

is performed only once in one of the availablemachines (Mokotoff, 2001). In our work, the machines

are equivalent to the vessels, while the jobs are the activities for the subsea well connections. For a

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies