(520g) A Hybrid Approach for Process Scheduling Under Uncertainty

In this work a novel hybrid methodology to address process scheduling problems under bounded uncertainty is proposed. A MILP formulation for short-term scheduling of batch processes is adopted [1]. We assume that the model is contaminated with uncertain data in the objective function (OFC), the right-hand side constraint vector (RHS) and in the constraint matrix (LHS), introduced by price, demand, and processing time or conversion rate uncertainty respectively.

Multi-parametric programming is a powerful tool to account for the presence of uncertainty in mathematical models and has previously contributed to proactive scheduling. Multi-parametric programming algorithms aim to derive the optimal solution as a function of the varying parameters without exhaustively enumerating the parameter space. However, not all types of uncertainty in MILP models can be addressed alike and, unlike OFC- and RHS-uncertainty, LHS-uncertainty still poses a major challenge. 

In order to deal with all types of parameter variation in the scheduling model, we apply a combined robust optimization/multi-parametric programming procedure for its approximate solution [2]. In the first step a partial immunization of the model against LHS-uncertainty is performed embedding the worst-case oriented approach [3] and, alternatively, an approach that allows to control the degree of conservatism of the solutions [4], whereas in the second step explicit solutions of the partially robust counterpart are derived using a recently proposed state-of-the art mp-MILP algorithm [5].

We demonstrate that this hybrid approach is computationally efficient, and that it is an attractive alternative to the rigorous robust optimization approach employed in process scheduling under uncertainty ([6,7]) in terms of providing a tight estimate of the overall profit of the scheduling problem. We obtain piecewise affine partially robust scheduling policies and when the true values of the parameters are known the optimal policy is determined via simple function evaluation. 

References

[1].	Ierapetritou, M.G., Floudas, C.A. Effective continuous-time formulation for short-term scheduling. 1. Multipurpose Batch Processes. Industrial & Engineering Chemistry Research, 37, 4341-4359 (1998).
[2].	Wittmann-Hohlbein, M., Pistikopoulos, E.N.  A robust optimization based approach to the general solution of mp-MILP problems. Accepted in Proceedings of 21st European Symposium on Computer Aided Process Engineering.
[3].	Ben-Tal, A., Nemirovski, A. Robust solutions of linear programming problems contaminated with uncertain data. Mathematical Programming 88, 411 (2000).
[4].	Bertsimas, D., Sim, M. Robust discrete optimization and network flows. Mathematical Programming, 98, 49-71 (2003).
[5].	Faísca, N.P., Kosmidis, V.D., Rustem, B., Pistikopoulos, E.N. Global optimization of multi-parametric MILP problems. Journal of Global Optimization 45, 131–151 (2009).
[6].	Lin, X., Janak, S.L., Floudas, C.A. A new robust optimization approach for scheduling under uncertainty: I. Bounded uncertainty. Computers & Chemical Engineering, 28, 1069-1085 (2004).
[7].	Li, Z., Ierapetritou, M.G. Robust Optimization for process scheduling under uncertainty. Industrial & Engineering Chemistry Research, 47, 4148-4157 (2008).