(629d) Scheduling under Uncertainty Using Parametric Programming

The consideration of uncertainty in process scheduling is of great importance to preserve plant feasibility during operations. Due to uncertainty in most of the parameters involved in the description of the scheduling problems, such as processing time, prices and demands, the optimal schedule of deterministic model could become suboptimal or even infeasible. However, the issue of uncertainty is not well studied for scheduling problems mainly because of the high complexity of the deterministic case.

Existing works on scheduling under uncertainty include different methods. Among them are the work of Honkomp et al. [1], and Vin and Ierapetritou [2] that use reactive scheduling to handle uncertainty by adjusting the schedule upon realization of the uncertain parameters or occurrence of unexpected events. Birge and Dempster [3], Balasubramanian and Grossmann [4] consider uncertain parameters that are described by discrete or continuous probability functions and use stochastic programming to address the parameter variability in process scheduling. The treatment of random parameters as fuzzy numbers and the constraints as fuzzy sets was introduced in scheduling by Ishibuchi et al. [5], and Balasubramanian and Grossmann [6]. Lin et al. [7] recently developed a robust optimization approach for scheduling under uncertainty which produces robust solutions that are immune against uncertainties. Jia and Ierapetritou [8] utilize MILP sensitivity analysis methods to investigate the effects of uncertain parameters and provide a set of alternative schedules.

An alternative approach was introduced recently by Jia and Ierapetritou [9] using the ideas of parametric mixed-integer linear programming. They have developed an approach to deal with uncertainty in product demand by solving the underlying parametric MILP problem with right-hand-side uncertainty. The proposed approach uses a new algorithm of multiparametric linear programming (mpLP) that avoids the use of the LP tableaus. Moreover, the new method solves the mpLP at only the leaf nodes in the B&B tree instead of every node during the branch and bound procedure, so it reduces the computational complexity of the parametric MILP problem significantly.

In this work the previously developed framework for uncertainty analysis of scheduling problems [9] is further extended in two fundamental directions. The first one addresses the issue of infeasibility by providing a description of the feasible region prior to the implementation of the parametric MILP algorithm, and the second one is the consideration of uncertainty in the objective function coefficients and problem constraints.

Current approaches for scheduling under uncertainty are commonly considering uncertain parameters that are described by given bounds. Although these bounds are generally derived from prior information, many times they incorporate infeasible points due to plant capacity limitations, recipe and timing constraints. This causes an extra complexity in the parametric analysis since it gives rise to infeasibilities. To avoid this problem the previous developed algorithm relies on reducing the uncertainty space, thus decreasing the flexibility of plant operations. In this work, we develop a pre-processing step that enables the consideration of wide uncertainty range by exploiting the idea of projection [10] into the constraint set. The inequality constraints of the relaxed LP problem in the parametric analysis process are all linear, so a convex polytope can be formed with the given bounds for uncertain parameters. Based on this idea, we determine the feasible region using a projection algorithm, which maps the space into the subspace spanned by uncertain parameters [10]. Thus we determine the complete description of the feasible region before solving the parametric MILP.

Additional work has been performed to expand the uncertain analysis to include the objective function coefficients such as prices and costs and the constraint parameters such as processing times and yields so as to completely describe all various types of uncertainty. For the case of uncertain objective function coefficients, the mpLP procedure is similar to the case of uncertainty in RHS parameters using the basic duality concepts. Considering the uncertain constraint coefficients gives rise to linear bilevel programming problem (BPP). Bilevel programming has been proved to be NP-hard problem. The most popular method for solving the linear BPP is ?Kuhn-Tucker? approach [11], which replaces the lower-level problem with ?Karush?Kuhn?Tucker? (KKT) optimality condition and adds it to the upper-level problem. When uncertainties exist in objective function, constraint coefficients, and RHS parameters at the same time, a BPP problem is also formed. In this case the objective functions in both upper and lower problems of this BPP are nonlinear. For such nonlinear bilevel programming problems, the KKT optimality conditions become only necessary since nonconvexities are involved in the lower level problem. Global optimization approaches [12,13] are then utilized to solve the nonlinear bilevel problems which involve twice differentiable functions.

Finally, the current parametric analysis method [9] requires manually retrieving and storing the required dual information in the mpLP solution process. Thus an automated technique is developed to improve the efficiency of the proposed parametric MILP approach. The proposed framework is applied on different scheduling problems to further clarify the steps of the approach and illustrate its applicability.

References [1] S.J.Honkomp, L.Mockus, and G.V.Reklaitis. A framework for schedule evaluation with processing uncertainty. Comput. Chem. Eng. 1999, 23, 595 [2] J.P.Vin and M.G.Ierapetritou. A new approach for efficient rescheduling of multiproduct batch plants. Ind. Eng. Chem. Res., 2000, 39, 4228 [3] J.R.Birge and M.A.H.Dempster. Stochastic programming approaches to stochastic scheduling. J. Global. Optim. 1996, 9, 417 [4] J.Balasubramanian and I.E.Grossmann. A novel branch and bound algorithm for scheduling flowshop plants with uncertain processing times. Comput. Chem. Eng. 2002, 26, 41 [5] H.Ishibuchi, N.Yamamoto, T.Murata and Tanaka H. Genetic algorithms and neighborhood search algorithms for fuzzy flowshop scheduling problems. Fuzzy Sets Syst. 1994, 67, 81 [6] J.Balasubramanian and I.E.Grossmann. Scheduling optimization under uncertainty- an alternative approach. Comput. Chem. Eng. 2003, 27, 469 [7] X.Lin, S.L.Janak, and C.A.Floudas. A new robust optimization approach for scheduling under uncertainty ? I. bounded uncertainty. Comput. Chem. Eng. 2004, 28, 2109 [8] Z.Jia and M.G.Ierapetritou. Short-term Scheduling under Uncertainty Using MILP Sensitivity Analysis. Ind. Eng. Chem. Res. 2004, 43, 3782 [9] Z.Jia and M.G.Ierapetritou. Uncertainty Analysis on the Right-Hand-Side for MILP problems AIChE J., To appear, 2006 [10] K. Fukuda and A. Prodon. Double description method revisited. In M. Deza, R. Euler, and I. Manoussakis, editors, Combinatorics and Computer Science, volume 1120 of Lecture Notes in Computer Science, pages 91?111. Springer-Verlag, 1996 [11] Fortuny-Amat, J., McCarl, B. A representation and economic interpretation of a two-level programming problem. Journal of Operational Research Society 1981, 32, 783 [12] Gumus, Z.H., Floudas, C.A. Global optimization of nonlinear bilevel programming problems. Journal of Global Optimization 2001, 20,1 [13] Sahinidis, N.V. BARON: A general purpose global optimization software package. Journal Global Optimization. 1996, 8, 201