(701c) Adjustable Robust Optimization for Scheduling Multipurpose Batch Plants Under Uncertainty

In this talk we develop a novel methodological framework to take into account parameter uncertainty during the scheduling optimization of multipurpose batch plants. Parameter uncertainty is typical in such a context, where parameters such as processing times, product demands, prices and availability of resources (e.g, equipment, personnel, utilities, storage, raw materials) may not be known with certainty at the time of decision-making.  Deterministic optimization approaches, which operate on nominal (expected) values of uncertain parameters and which do not explicitly take into account parameter variation, may lead to suboptimal or infeasible solutions depending on the actual realization of these parameters. One of the main frameworks for mitigating the risk associated with parameter uncertainty is Robust Optimization (RO) [1,2], which focuses on generating solutions that retain their feasibility as long as the uncertain parameters assume values (i.e., “realize”) from a pre-specified uncertainty set.

The RO approach has been applied on multipurpose batch plant scheduling in a number of recent papers [3-6] with very promising results, demonstrating the suitability of the framework to address parameter uncertainty in this context. In these previous studies, the RO framework was applied in the traditional, “static” manner, which handles all of the decisions as “here-and-now”; that is, as decisions that must be made before the beginning of the time horizon when the model optimization is conducted. As a consequence of this limitation of the static RO approach, one must commit to a solution that may prove suboptimal if a favorable realization of the parameters occurs. This limitation, however, is not motivated by actual practice, where in many cases decisions can be made “last-minute” or changed within the course of the scheduling horizon. Since decisions can in reality be delayed for some later time, when valuable information from the progress of the execution of the schedule will have become available (“wait-and-see”), efficiencies can be exploited and less conservative schedules obtained.

In this work, we extend the static approach and apply the framework of Adjustable Robust Optimization (ARO) [7] in the context of batch plant scheduling. Instead of generating a single “here-and-now” decision, the ARO framework generates a family of solutions (a.k.a., a policy) which adapts to the actual realization of the uncertainty as the latter is gradually revealed during the scheduling horizon. We thus demonstrate how real-time information can be exploited without having to resort to—typically expensive and possibly suboptimal—reoptimization processes (see, e.g., “reactive scheduling”) and without compromising our chosen level of insurance against risk. We also present the concept of decision-dependent uncertainty sets in order to realistically model a typical scheduling environment where assumptions about parameter correlations can only be postulated for scheduling tasks that will in fact occur (as opposed to tasks that were defined for modeling convenience but never chosen).

A comprehensive computational study is presented across literature benchmark examples from which the performance and the value of the proposed framework is assessed. Our results show that the ARO framework can obtain solutions that are less conservative than the solutions obtained by static RO and that closely approach the theoretical limit of “worst-case-deterministic” solutions. In addition to the prevailing solution method that requires a model reformulation, we explore also solution strategies based on a cutting-plane method [8] in order to further enhance computational efficiency.

[1]. Ben-Tal, A., Nemirovski, A. (1999). Robust solutions of uncertain linear programs. Operations research letters, 25(1), 1-13.

[2]. Bertsimas, D., Sim, M. (2004). The price of robustness. Operations research, 52(1), 35-53.

[3]. Vin, J. P., Ierapetritou, M. G. (2001). Robust short-term scheduling of multiproduct batch plants under demand uncertainty. Industrial & engineering chemistry research, 40(21), 4543-4554.

[4]. Lin, X., Janak, S. L., Floudas, C. A. (2004). A new robust optimization approach for scheduling under uncertainty: I. Bounded uncertainty. Computers & chemical engineering, 28(6), 1069-1085.

[5]. Janak, S. L., Lin, X., Floudas, C. A. (2007). A new robust optimization approach for scheduling under uncertainty: II. Uncertainty with known probability distribution. Computers & chemical engineering, 31(3), 171-195.

[6]. Li, Z., Ierapetritou, M. G. (2008). Robust optimization for process scheduling under uncertainty. Industrial & Engineering Chemistry Research, 47(12), 4148-4157.

[7]. Ben-Tal, A., Goryashko, A., Guslitzer, E., Nemirovski, A. (2004). Adjustable robust solutions of uncertain linear programs. Mathematical Programming, 99(2), 351-376.

[8]. Mutapcic, A., Boyd, S. (2009). Cutting-set methods for robust convex optimization with pessimizing oracles. Optimization Methods & Software, 24(3), 381-406.