Ph. D. Thesis / In order to compute more realistic production plans and schedules, techniques using nonlinear programming (NLP) and mixed-integer nonlinear programming (MINLP) have gathered a lot of attention from the industry and academy. Efficient solution of these problems to a proven ε-global optimality remains a challenge due to their combinatorial, nonconvex, and large dimensionality attributes. The key contributions of this work are: 1) the generalization of the inventory pinch decomposition method to scheduling problems, and 2) the development of a deterministic global optimization method. An inventory pinch is a point at which the cumulative total demand touches its corresponding concave envelope. The inventory pinch points delineate time intervals where a single fixed set of operating conditions is most likely to be feasible and close to the optimum. The inventory pinch method decomposes the original problem in three different levels. The first one deals with the nonlinearities, while subsequent levels involve only linear terms by fixing part of the solution from previous levels. In this heuristic method, infeasibilities (detected via positive value of slack variables) are eliminated by adding at the first level new period boundaries at the point in time where infeasibilities are detected. The global optimization algorithm presented in this work utilizes both piecewise McCormick (PMCR) and Normalized Multiparametric Disaggregation (NMDT), and employs a dynamic partitioning strategy to refine the estimates of the global optimum. Another key element is the parallelized bound tightening procedure. Case studies include gasoline blend planning and scheduling, and refinery planning. Both inventory pinch method and the global optimization algorithm show promising results and their performance is either better or on par with other published techniques and commercial solvers, as exhibited in a number of test cases solved during the course of this work. / Thesis / Doctor of Philosophy (PhD) / Optimal planning and scheduling of production systems are two very important tasks in industrial practice. Their objective is to ensure optimal utilization of raw materials and equipment to reduce production costs. In order to compute realistic production plans and schedules, it is often necessary to replace simplified linear models with nonlinear ones including discrete decisions (e.g., “yes/no”, “on/off”). To compute a global optimal solution for this type of problems in reasonable time is a challenge due to their intrinsic nonlinear and combinatorial nature. The main goal of this thesis is the development of efficient algorithms to solve large-scale planning and scheduling problems. The key contributions of this work are the development of: i) a heuristic technique to compute near-optimal solutions rapidly, and ii) a deterministic global optimization algorithm. Both approaches showed results and performances better or equal to those obtained by commercial software and previously published methods.

<p>Current gasoline blend planning practice is to optimize blend plans via discrete-time multi-period NLP or MINLP models and schedule blends via interactive simulation. Solutions of multi-period models using discrete-time representation typically have different blend recipes for each time period. In this work, the concept of an inventory pinch point is introduced and used it to construct a new decomposition of the multi-period MINLP problems: at the top level nonlinear blending problems for periods delimited by the inventory pinch points are solved to optimize multi-grade blend recipes; at the lower level a fine grid multi-period MILP model that uses optimal recipes from the top level is solved in order to determine how much to blend of each product in each fine grid period, subject to minimum threshold blend size. If MILP is infeasible, corresponding period between the pinch points is subdivided and recipes are re-optimized.</p> <p>Two algorithms at the top level are examined: a) multi-period nonlinear model (MPIP) and b) single-period non-linear model (SPIP). Case studies show that the MPIP algorithm produces solutions that have the same optimal value of the objective function as corresponding MINLP model, while the SPIP algorithm computes solutions that are most often within 0.01% of the solutions by MINLP. Both algorithms require substantially less computational effort than the corresponding MINLP model. Reduced number of blend recipes makes it easier for blend scheduler to create a schedule by interactive simulation.</p> / Master of Applied Science (MASc)