(103c) Two-Level Algorithm for Gasoline Blend Planning Using Inventory Pinch Points to Reduce Number of Blend Recipes

We consider the problem of multiple blend recipes arising from multi-period blend models.  Experience shows that the multi-period model solutions vary not only from one period to another, but also (for the same set of data) from one solver to another.  Moreover, some solvers produce different solutions.  Such solutions are awkward to apply in practice, since practitioners know intuitively that the same grade of gasoline can be blended by the same recipe for extended lengths of time.

Above behavior has been observed even with linear and nonlinear quality constraints.  Recently introduced complex EPA formulations for gasoline quality constraints complicate the picture further, since they are highly nonlinear and require highly specialized algorithms to be solved.  Solving multi-period MINLP model with these constraints remains in the domain of very specialized experts.

This work presents a two-level composite algorithm to solve the gasoline blend planning optimization problem while reducing the number of blend recipes.  The first level deals with optimization of the blend recipes and in the second level production volumes and inventory profiles are computed.  The first level is formulated as a multi-period NLP and the second level as a multi-period MILP; the time grids of both models are partially synchronized.  In this way, after computing the lowest cost blend recipes, according to the problem instance and without the assumption of linear blending properties, a production plan that uses these optimal recipes is calculated.  The algorithm (i) computes the blend plan that keeps the blend recipes as constant as possible along the blending horizon, (ii) avoids the need to use multi-period MINLP models, and (iii) computes the solutions that have the same cost as the multi-period MINLP optimum.

A pinch point on the cumulative total demand (CTD) curve is a point where cumulative average production (CAP) curve is tangent to the CTD curve and if we extrapolate the CAP curve from this point onward it will not cross the CTD curve.  In other words, the inventory pinch points are defined by peaks on the cumulative total demand profile and they indicate time intervals where one recipe can be used without incurring in inventory infeasibilities.  The inventory infeasibilities are defined as the missing volume to fulfill the demand of one or more products by using only the fixed recipes and the available amount of blending components.  The inventory pinch points delineate the time periods in the recipe optimization problem.  The planning horizon in the second level is divided in a fixed number of time periods and an integer number of these are contained in each one of the time periods of the recipe optimization level.  The blend recipes and target inventories from the first level are fixed in their corresponding time periods in the second level. 

Sometimes, inventory infeasibilities may still appear in the planning level when using the blend recipes from the first level.  These infeasibilities are encountered because: (i) the recipe optimization problem has multiple global optimal solutions and not all of them can be used in the planning level, (ii) some logistic constraints (e.g., specific production sequences) may reduce the degrees of freedom to compute a production plan with a fixed recipe, or (iii) the presence of large variations on the blending components supply profiles.  An iterative procedure based on the inventory infeasibilities and the time when they occur is used to generate a feasible plan.  Slack variables are introduced in the model to detect the inventory infeasibilities, as well as in the objective function to minimize, multiplied by penalty coefficients which are larger than the blending components costs.  In order to extend the use of a blend recipe, the penalty coefficients decrease with time, moving the infeasibilities as late as possible in the planning horizon.  When inventory infeasibilities are found in the second level, the corresponding first-level time periods are divided at the same point in time where the first infeasibility appears.  Then, new blend recipes are computed and used to calculate the production plan.  The procedure repeats until no infeasibilities are found, or if infeasibilities appear in the first level which means that there are not enough blending components available to blend according to the demand and product specifications.

The results obtained with the two-level algorithm are very close to those provided by the corresponding multi-period MINLP model, the difference is less than 0.01%.  In addition, the number of different blend recipes computed by our algorithm is less than the number given by the MINLP solution.  The number of iterations is usually small and the algorithm is not affected by the blending components supply profile.

By decomposing the problem into two levels and using the inventory pinch point concept, complex rigorous nonlinear models can be used to compute optimal blend recipes without being solved at each time period of the production planning or scheduling horizon, avoiding the use of MINLP models and reducing the computational requirements to solve the overall problem without incurring in a great deviation from the optimal solution.