(434a) A Decomposition Framework for Scheduling of Refinery Operations Including Logistics

When faced with large-scale problems, decomposition is a best way of dealing with them. In oil refineries, an integrated approach for scheduling of production units, blend units, and end product distribution gives rise to a large scale mixed integer model. The integrated refinery operations scheduling problem becomes even more complex when we include logistics details, such as sequence dependent switchovers, multipurpose product tanks and blender units, minimum run-length requirements, fill-draw-delay, one-flow out of blender, maximum heel quantity, and downgrading product to lower quality. These logistics requirement are associated with blending problem. The variables associated with logistics details are the mostly binary variables that have one-to-one correspondence with quantity sizing variables. This combinatorial characteristic of the logistics problem makes the optimization problem NP hard. Even with today's efficient commercially available optimization software tools (CPLEX, XPRESS), simultaneous solution of logistics, quantity and quality aspects for large-scale problems is not possible in reasonable time (Kelly and Mann, 2003ab).

To overcome computational challenge posed by large scale model, decomposition is used to obtained smaller sub-problems that are relatively easier to solve than one intractable problem. For example, the scheduling problem can be decomposed spatially by exploiting special structure of the refinery (Jia and Ierapetritou, 2003; Shah, Saharidis et al., 2009). Luo and Rong, 2007 proposed a hierarchical approach for large scale refinery scheduling problem where upper level is optimized using aggregated product tanks and lower level uses heuristics and rules in stimulation system. A specialized outer approximation algorithm is proposed by Karuppiah, Furman et al., 2008 for crude-oil scheduling problem. They use spatial decomposition to obtain sub-problems and then lagrangian relaxation is used to derive valid cuts for the sub-problems. These cuts added to the relaxation of original problem to obtain tight and rigorous lower bound. Saharidis, Minoux et al., 2010 applied benders decomposition to crude oil scheduling problem where the relaxed master problem deals with loading and unloading of the available tanks and primal problem deals with schedule of flow between the tank and upstream and downstream systems. Another approach is to decompose the original problem in hierarchical manner: upper level problem addresses decisions regarding assignment and sizing and lower level address sequencing decisions (Maravelias, 2006).

In our work, we address a large-scale realistic refinery scheduling problem that includes logistics details. The case study studied in this work has parallel units, multipurpose blend units and product tanks. Different decomposition methodologies are considered and compared for the solution of this problem. These methodologies include spatial decomposition, mathematical decomposition involving specialized benders decomposition, and Lagrangian decomposition. In spatial decomposition approach, the problem is decomposed at multipurpose blend units because logistics details are associated with blending and distribution problem. The resulting sub-problems are solved to obtain feasible changeovers assignment and to identify any infeasible assignment for multipurpose blend unit. The obtained changeovers assignments are also valid for the overall problem, and can be included to improve the solution time. Another decomposition approach we used is Lagrangian decomposition, where we introduce two set of duplicating variables pertaining to the flow and times variables in the network that have been split by spatial decomposition. These duplicating variables are related to each other by equality constraints in the original problem and to obtain decomposed systems via lagrangian relaxation, equality constraints are dualized and transferred to the objective function. Classical benders algorithm (Benders, 1962) is used to solve refinery operations scheduling problem. However, classical benders algorithm generates low-density cuts resulting in high computational time. To reduce the number of iterations and to improve solution time, we apply covering cut bundle strategy for benders algorithm proposed by Saharidis, Minoux et al., 2010. Detailed analysis and results of the different decomposition methods will be presented.

References

Benders, J. F. (1962). "Partitioning Procedures for Solving Mixed-Variables Programming Problems." Numerische Mathematic 4: 238-252.

Jia, Z. and Ierapetritou, M. (2003). "Mixed-Integer Linear Programming Model for Gasoline Blending and Distribution Scheduling." Industrial & Engineering Chemistry Research 42(4): 825-835.

Karuppiah, R., Furman, K. C. and Grossmann, I. E. (2008). "Global optimization for scheduling refinery crude oil operations." Computers & Chemical Engineering 32(11): 2745-2766.

Kelly, J. D. and Mann, J. L. (2003a). "Crude-oil blend scheduling optimization: An application with multi-million dollar benefits: Part I." Hydrocarbon Processing(June): 47-53.

Kelly, J. D. and Mann, J. L. (2003b). "Crude-oil blend scheduling optimization: An application with multi-million dollar benefits: Part II." Hydrocarbon Processing(July): 72-79.

Luo, C. and Rong, G. (2007). "Hierarchical Approach for Short-Term Scheduling in Refineries." Industrial & Engineering Chemistry Research 46(11): 3656-3668.

Maravelias, C. T. (2006). "A decomposition framework for the scheduling of single- and multi-stage processes." Computers & Chemical Engineering 30(3): 407-420.

Saharidis, G. K. D., Minoux, M. and Ierapetritou, M. G. (2010). "Accelerating Benders method using covering cut bundle generation." International Transactions in Operational Research 17(2): 221-237.

Shah, N., Saharidis, G. K. D., Jia, Z. and Ierapetritou, M. G. (2009). "Centralized-decentralized optimization for refinery scheduling." Computers & Chemical Engineering 33(12): 2091-2105.