Matheuristics for a parallel machine scheduling problem with non-anticipatory family setup times: Application in the offshore oil and gas industry

In this paper, we address a variant of a batch scheduling problem with identical parallel machines and non-anticipatory family setup times to minimize the total weighted completion time. We developed an ILS and a GRASP matheuristics to solve the problem using a constructive heuristic and two MIPbased neighborhood searches, considering two batch scheduling mathematical formulations. The problem derives from a ship scheduling problem related to offshore oil & gas logistics, the Pipe Laying Support Vessel Scheduling Problem (PLSVSP). The developed methods overcome the current solution approaches in the PLSVSP literature, according to experiments carried out on a benchmark of 72 instances, with different sizes and characteristics, in terms of computational time and solution quality. New best solutions are provided for all medium and large-sized instances, achieving a reduction of more than 10% in the objective function of the best case. (c) 2020 Elsevier Ltd. All rights reserved.

Automated summary

This paper addresses a variant of a batch scheduling problem with identical parallel machines and non-anticipatory family setup times. New methods have been developed to overcome current solution approaches and provide improved results for ship scheduling problems, achieving a reduction of more than 10% in the objective function.