Scheduling pipe laying support vessels with non-anticipatory family setup times and intersections between sets of operations

Abstract

In this paper, we deal with a problem that arises from the oil industry with the need to schedule a pipe laying support vessel fleet responsible for connecting oil wells to production platforms. We model it as an identical parallel machine scheduling problem, considering a particular case where jobs are composed of intersecting sets of operations and with operations partitioned into families. A non-anticipatory family setup time is incurred on three occasions: when a machine changes the execution of operations from one family to another, when the machine reaches its capacity, and before the first operation on each machine. These considerations, along with other scheduling features, make the problem more challenging and attractive to the scheduling literature. We propose three mathematical formulations to solve 72 generated instances, based on actual data, with up to 50 operations to schedule. Among the formulations, the Batch Scheduling presents better results with the smallest gaps, when compared to the best lower bounds obtained. This formulation considers a dispatching rule to sequence operations within batches, generating better solutions in 22 of the 24 largest instances, dominating the other formulations. A Brazilian oil company currently uses this approach in a production system for its tactical planning.

Keywords:

• Identical parallel machine scheduling
• family scheduling problem
• offshore resource management
• non-anticipatory setup times
• ship scheduling

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This study was financed in part by PUC-Rio, by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior – Brasil (CAPES) – Finance Code 001 and by the Conselho Nacional de Desenvolvimento Científico e Tecnolóogico (CNPq) under Grant numbers 403863/2016-3, 306802/2015-5, 425962/2016-4 and 313521/2017-4.

Notes on contributors

Victor Abu-Marrul

Victor Abu-Marrul is a Ph.D. student at the Industrial Engineering department from Pontifical Catholic University of Rio de Janeiro (PUC-Rio). He is also a researcher at Tecgraf institute (PUC-Rio) since 2016, working with applied scheduling problems to an oil and gas company operating in the Brazilian offshore basin. He is a member of a 3-year collaborative project between a Norwegian and a Brazilian university to develop research and advanced studies in the oil and gas industry logistics.

Rafael Martinelli

Rafael Martinelli is an Operations Research professor at the Industrial Engineering Department of the Pontifical Catholic University of Rio de Janeiro (PUC-Rio). His published research includes papers in different fields, such as Engineering, Mathematics, Computer Science, and Decision Sciences. He has experience solving industry problems, working on multiple projects from different companies.

Silvio Hamacher

Silvio Hamacher is an associate professor of Operations Research at the Industrial Engineering from Pontifical Catholic University of Rio de Janeiro (PUC-Rio). He has published more than 150 full papers on international journals, book chapters, or conferences proceedings. He was the president and member of the board of SOBRAPO (Brazilian Operations Research Society). He is also the manager of the Supply Chain and Optimization Area at Tecgraf Institute (PUC-Rio), where has overseen more than 20 large industrial contracts.