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

作     者：Cunha, Victor Santos, Iuri Pessoa, Luciana Hamacher, Silvio 

作者机构：Pontificia Univ Catolica Rio de Janeiro DEI Ind Engn Dept 225 Gavea BR-22430060 Rio de Janeiro Brazil 

出 版 物：《INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH》 (国际运筹学汇报)

年 卷 期：2020年第27卷第1期

页      面：197-218页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：PUC-Rio Coordenacao de Aperfeicoamento de Pessoal de Nivel Superior - Brasil (CAPES) CNPq Tecgraf 

主　　题：oil industry ship scheduling iterated local search metaheuristics mixed integer linear programming 

摘      要：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.