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

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.