A piecewise McCormick relaxation-based strategy for scheduling operations in a crude oil terminal

•A MINLP scheduling model applied to crude oil terminal operations.•Use of piecewise McCormick envelopes for relaxing bilinear terms.•An iterative two-step MILP-NLP algorithm based on a piecewise McCormick relaxation and a domain-reduction strategy.•Comparative analysis of univariate and bivariate domain partitioning schemes.•A decision-support model for planning daily activities in a crude oil terminal.

The petroleum supply chain can be divided into three segments: upstream, midstream and downstream. This work studies the scheduling of operations in a crude oil terminal within the midstream segment. The first challenge consists in deciding how the crude oil that arrives in vessels should be uploaded to the storage tanks. At the same time, the operations engineer must decide which storage tanks will feed the pipeline connected to the refinery in order to satisfy its demand. This work concerns the crude oil terminal of the national refinery of Uruguay. To schedule terminal operations, this work proposes an iterative two-step MILP-NLP algorithm based on piecewise McCormick relaxation and a domain-reduction strategy for handling bilinear terms. For small instances for which an optimal solution is known, the proposed strategy consistently finds optimal or near-optimal solutions. It also solves larger instances which are, in some cases, intractable by a global optimization solver.