(425g) Production Planning and Scheduling Integration through Multiparametric Bilevel Mixed-Integer Optimization

Planning and scheduling optimization problems with seasonal demand variability can be often expressed within a hierarchical structure, where optimal decisions at an aggregate upper level (planning) provide constraints for the detailed decision making (scheduling) at a lower level, typically posed as bilevel optimization problems [1-4]. Since discrete decisions are involved most likely at both levels, the resulting formulations typically correspond to bilevel mixed-integer linear programming problems (B-MILP). The solution of these problems is very challenging, and typically requires the use of global optimization techniques, even for the derivation of approximate solutions [5, 6].

In this work, we propose a novel algorithm for the exact and global solution of bilevel planning/scheduling problems. The algorithm is based on multiparametric programming theory and our past work on bilevel programing with continuous variables [7, 8]. The main idea of our approach is to treat the scheduling problem as a multi-parametric mixed-integer linear programming problem (mp-MILP), in which the production targets (optimization variables of the upper level problem) are considered as the parameters for the lower level scheduling problem. The resulting exact parametric solutions are then substituted into the upper level planning problem, which can be solved as a set of single-level deterministic mixed-integer programming problems. The proposed algorithm was applied and tested on a range of planning and scheduling example problems from the literature [2, 3].

References: [1] You, F., Grossmann, I.E. Design of responsive supply chains under demand uncertainty (2008) Computers and Chemical Engineering, 32 (12), pp. 3090-3111. [2] Dogan, M.E., Grossmann, I.E. A decomposition method for the simultaneous planning and scheduling of single-stage continuous multiproduct plants (2006) Industrial and Engineering Chemistry Research, 45 (1), pp. 299-315.

 [3] Li, Z., Ierapetritou, M.G. Integrated production planning and scheduling using a decomposition framework (2009) Chemical Engineering Science, 64 (16), pp. 3585-3597.

 [4] Ryu, J.-H., Dua, V., Pistikopoulos, E.N. A bilevel programming framework for enterprise-wide process networks under uncertainty (2004) Computers and Chemical Engineering, 28 (6-7), pp. 1121-1129.

 [5] Mitsos, A. Global solution of nonlinear mixed-integer bilevel programs (2010) Journal of Global Optimization, 47 (4), pp. 557-582.Global Optimization, 47 (4), pp. 557-582.

 [6] GümüÅ?, Z.H., Floudas, C.A. Global optimization of mixed-integer bilevel programming problems (2005) Computational Management Science, 2 (3), pp. 181-212.

 [7] Faísca, N.P., Saraiva, P.M., Rustem, B., Pistikopoulos, E.N. A multi-parametric programming approach for multilevel hierarchical and decentralized optimisation problems (2009) Computational Management Science, 6 (4), pp. 377-397. [8] Faisca, N.P., Dua, V., Rustem, B., Saraiva, P.M., Pistikopoulos, E.N. Parametric global optimisation for bilevel programming (2007) Journal of Global Optimization, 38 (4), pp. 609-623.