362759 Resource-Task Network Continuous-Time Formulation for Crude Oil Blending Operations

Thursday, November 20, 2014: 1:33 PM
406 - 407 (Hilton Atlanta)
Pedro M. Castro, Centro de Investigação Operacional, Faculdade de Ciências, Universidade de Lisboa, Lisbon, Portugal and Ignacio E. Grossmann, Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, PA

Every refinery has an optimization opportunity associated with better crude oil blend scheduling that can reach multimillion dollars per year [1]. From the crude oil purchases perspective, the faster the ability to assess whether a particular spot oil purchase will result in a feasible operation, the better the refinery can capitalize on short-term market opportunities. From the operational perspective, variation in crude oil mixture quality and flowrate charged to the distillation columns affects downstream production units and is perhaps the single most influential disturbance to a refinery. Overall, crude oil blend scheduling optimization is a relatively inexpensive and timely way to improve performance.

Early works on crude oil scheduling with mathematical programming techniques employed discrete-time formulations [2,3]. In particular, Lee et al. [3] proposed a MILP for the system comprised of storage tanks receiving crude from marine vessels, charging tanks and crude distillation units. It can be viewed as a relaxation of the non-convex MINLP model that is required to ensure that there are no discrepancies in crude compositions inside tanks with respect to their outlet streams.

The turn of the millennium saw increased emphasis on continuous-time models. Jia et al. [4] proposed a State-Task Network, unit-specific formulation. A two-stage MILP-NLP solution procedure was proposed to tackle the MINLP, featuring in the first stage a relaxed MILP model without the complex, bilinear blending constraints. After fixing the binary variables, a near optimal solution to the original problem was then found in the second stage. A more rigorous model with respect to the synchronization of time events with material balances is given in [5]. The unit-specific MINLP model of Li et al. [10] is for marine-access refineries and is tackled through a spatial branch-and-bound optimization algorithm that on each node uses the MILP-NLP procedure. Rather than removing the blending constraints, a tighter MILP relaxation was created through piecewise McCormick envelopes [11]. Overall, the integer feasible solutions obtained for a set of test cases from the literature were guaranteed to be within 2% of global optima.

Moro and Pinto [6] opted for a single time grid MINLP continuous-time formulation that was tackled with the augmented penalty version of the outer-approximation method. Sharing the time representation concept and the inability to provide global optima, Reddy et al. [7] proposed a MILP relaxation along the lines of [3] combined with a rolling-horizon algorithm to eliminate the composition discrepancy.

Mouret et al. [8] considered yet another type of continuous-time formulation, called single operation sequencing model, which represents a schedule as a sequence of priority slots. Nonlinearities where handled by the two stage procedure of [4]. Later, the part of the model without the blending constraints (MILP) was compared to models relying on different time representation concepts, with continuous-time scaling better with problem size and hence outperforming its discrete-time counterpart [8].

In this work, we approach the solution of the crude oil scheduling problem with the Resource-Task Network based single time grid, continuous-time formulation of Castro et al. [12]. Contrary to most scheduling problems that feature a fixed recipe with known proportions of input materials to a processing task, the main goal of crude oil scheduling is to identify the optimal mix of low-cost and premium crudes that maximizes profit while meeting operational constraints. The main novelty is thus related to extending the generality of the formulation to handle variable recipe tasks with multiple input materials, of which crude oil blending is a particular case. While doing so, we also show how to derive a RTN superstructure that implicitly meets the logistic constraint of no simultaneous inlet and outlet streams from a storage/charging tank. The third novelty is related to the use of multiparametric disaggregation [13,14] for the relaxation of the bilinear blending constraints that: (i) is known to be tighter than the one resulting from the standard McCormick relaxation; (ii) scales more favorably than piecewise McCormick relaxation [14], often leading to lower optimality gaps.

Overall, the new formulation has the advantage of avoiding computationally inefficient big-M constraints, unlike previously proposed unit-specific and priority-slot based models. Through the solution of a set of test problems from the literature, we show that the resulting MINLP problems can be solved closed to global optimality by the commercial solver GloMIQO [16] for the objective of gross margin maximization but not for operating cost minimization. We also show that adopting a two-step MINLP algorithm where the MILP relaxation is derived from multiparametric disaggregation, can reduce the optimality gap by orders of magnitude.


Financial support from the Luso-American Foundation under the 2013 Portugal-U.S. Research Networks Program, from Fundação para a Ciência e Tecnologia (FCT) through the Investigador FCT 2013 program, and from FEDER (Programa Operacional Factores de Competitividade-COMPETE) and FCT through project FCOMP-01-0124-FEDER-020764. 


[1] Kelly, J.D.; Mann, J.L. Crude oil blend scheduling optimization: an application with multimillion dollar benefits-Part 1. Hydrocarbon Processing 2003, 82(6), 47.

[2] Shah, N. Mathematical Programming Techniques for Crude Oil Scheduling. Comput. Chem. Eng. 1996, 20, S1227.

[3] Lee, H.; Pinto, J. M.; Grossmann, I. E.; Park, S. Mixed-integer linear programming model for refinery short-term scheduling of crude oil unloading with inventory management. Ind. Eng. Chem. Res. 1996, 35, 1630.

[4] Jia, Z.; Ierapetritou, M.; Kelly, J. D. Refinery Short-term Scheduling Using Continuous Time Formulation: Crude-Oil Operations. Ind. Eng. Chem. Res. 2003, 42, 3085.

[5] Furman, K.; Jia, Z.; Ierapetritou, M.G. A Robust Event-Based Continuous Time Formulation for Tank Transfer Scheduling. Ind. Eng. Chem. Res. 2007, 46, 9126.

[6] Moro, J.F.L.; Pinto, J.M. Mixed-integer Programming Approach for Short-Term Crude Oil Scheduling. Ind. Eng. Chem. Res. 2004, 43, 85.

[7] Reddy, P.C.P.; Karimi, I.A.; Srinivasan, R. A new continuous-time formulation for scheduling crude oil operations. Chem. Eng. Sci. 2004, 59, 1325.

[8] Mouret, S.; Grossmann, I. E.; Pestiaux, P. A novel priority-slot based continuous-time formulation for crude-oil scheduling problems. Ind. Eng. Chem. Res. 2009, 48, 8515.

[9] Mouret, S.; Grossmann, I.E.; Pestiaux, P. Time representations and mathematical models for process scheduling problems. Comput. Chem. Eng. 2011, 35, 1038.

[10] Li, J.; Misener, R.; Floudas, C.A. Continuous-Time Modeling and Global Optimization Approach for Scheduling of Crude Oil Operations. AIChE J. 2012, 58, 205.

[11] Karuppiah, R.; Grossmann, I.E. Global optimization for the synthesis of integrated water systems in chemical processes. Comput. Chem. Eng. 2006, 30, 650.

[12] Castro, P. M.; Barbosa-Póvoa, A. P.; Matos, H. A.; Novais, A. Q. Simple Continuous-Time Formulation for Short-Term Scheduling of Batch and Continuous Processes. Ind. Eng. Chem. Res. 2004, 43, 105.

[13] Teles, J. P.; Castro, P. M.; Matos, H. A. Multiparametric disaggregation technique for global optimization of polynomial programming problems. Journal of Global Optimization 2013, 55, 227.

[14] Kolodziej, S.; Castro, P. M.; Grossmann, I. E. Global optimization of bilinear programs with a multiparametric disaggregation technique. Journal of Global Optimization 2013, 57, 1039.

[15] McCormick, G. P. Computability of global solutions to factorable nonconvex programs. Part I. Convex underestimating problems. Mathematical Programming 1976, 10, 147.

[16] Misener, R.; Floudas, C.A. GloMIQO: Global mixed-integer quadratic optimizer. Journal of Global Optimization 2013, 57, 3.

Extended Abstract: File Uploaded
See more of this Session: Planning and Scheduling I
See more of this Group/Topical: Computing and Systems Technology Division