(468b) A Novel Multiparametric Programming Framework And Its Application In Scheduling Under Uncertainty

In real plants uncertainty is a very important concern that is coupled with the scheduling process since many of the parameters that are associated with scheduling are not known exactly. Parameters like raw material availability, prices, machine reliability, and market requirements vary with respect to time and are often subject to unexpected deviations. Having ways to systematically consider uncertainty is as important as having the scheduling model itself.

There are a number of approaches to address the problem of scheduling under uncertainty including reactive scheduling, stochastic scheduling and robust scheduling. A recent review is given by Li and Ierapetritou (2007). As an alternative way to address uncertainty in scheduling and in a general optimization problem, parametric programming has a unique advantage since it results in the full characterization of the entire range of solution space and provides a complete map of the various alternatives in the face of uncertainty. In the literature, multiparametric linear programming (mpLP) and multiparametric quadratic programming (mpQP) problems are well studied, while the general multiparametric nonlinear programming (mpNLP) has not been efficiently addressed due to problem complexity. For problems that include integer variables, the existing methods for multiparametric mixed integer linear and quadratic programming (mpMILP/mpMIQP) are generally based on the solution of mpLP or mpQP subproblems (Acevedo and Pistikopoulos, 1997, Dua and Pistikopoulos, 1999, Dua, Bozinis and Pistikopoulos, 2002). Most of the existing approaches however can address problems of relatively small size, limiting the applicability of the parametric approaches to handle uncertainty in realistic problems of scheduling.

A typical multiparametric programming problem to describe process scheduling will involve uncertainties in the objective coefficients (price), right hand side of constraints (demand) and constraint matrix coefficients (processing time, recipe, etc.). In such a case, the problem is modeled as mpMIQP or multiparametric mixed integer nonlinear programming (mpMINLP) problem. In this work, we proposed a framework to perform multiparametric programming analysis for the mixed integer programming problem describing the scheduling problem. The proposed framework is general to handle the mpMILP problem and some special cases of mpMIQP problem. It provides an efficient way for analyzing not only the uncertain scheduling problem but also other process design/operation problem under uncertainty. Moreover, the framework is specially designed to address large scale problems, as the scheduling application illustrated in this work.

The main idea of the proposed framework is to decompose the problem into a series of smaller problems, each of them producing the parametric information around a given parameter value. Using the nominal parameter values t0, the mpMILP problem is first relaxed into MILP problem by fixing the integer variables. Using linear programming optimality conditions, the critical region and the optimal parametric objective function is determined. Then, a mixed integer quadratically constrained programming (MIQCP) problem is formulated, which aims to obtain an integer solution with better objective. This is achieved by introducing the following parametric cut: z <=z*-e, where z is the performance measure function (e.g. profit), z* is the optimal objective function corresponding to the critical region that cover the point t0, e is a small number to ensure that better objective is found. Note that this problem is not solved to optimality since a feasible solution suffices, thus increase the efficiency of the proposed approach. For a given critical region, a series of MIQCP problems are solved to identify the points that have better objective function values. By comparing the parametric solution of those points, the critical region is continuously updated until the MIQCP problem becomes infeasible.

The main advantages of the proposed method comparing to the existing techniques are that: a) the method is easy to be implemented; b) it can produce useful information to the decision maker even without resolving the whole parameter space; and c) it is computationally more efficient since it is not necessary to get the optimal solution of a MINLP problem. Several problems are solved to illustrate the effectiveness of the proposed multiparametric programming method in addressing uncertain scheduling problems.

Reference:

Li, Z. and M. G. Ierapetritou, Process scheduling under uncertainty: Review and challenges, Computers and Chemical Engineering, doi:10.1016/j.compchemeng. 2007.03.001

Acevedo, J. and E. N. Pistikopoulos (1997). A multiparametric programming approach for linear process engineering problems under uncertainty. Industrial and Engineering Chemistry Research 36(3): 717-728

Dua, V. and E. N. Pistikopoulos(1999). Algorithms for the solution of multiparametric mixed-integer nonlinear optimization problems. Industrial and Engineering Chemistry Research 38: 3976 - 3987

Dua, V., N. A. Bozinis and E. N. Pistikopoulos(2002). A multiparametric programming approach for mixed-integer quadratic engineering problems. Computers and Chemical Engineering, 26: 715-733