CHEMICAL ENGINEERING TRANSACTIONS VOL. 70, 2018 A publication of The Italian Association of Chemical Engineering Online at www.aidic.it/cet Guest Editors: Timothy G. Walmsley, Petar S. Varbanov, Rongxin Su, Jiří J. Klemeš Copyright © 2018, AIDIC Servizi S.r.l. ISBN 978-88-95608-67-9; ISSN 2283-9216 Robust Optimization for Batch Process Scheduling Under Uncertainty Using Piecewise Linear Decision Rule Cen Guo, Fengqi You* Cornell University, 318 Olin Hall, Ithaca, New York 14853, USA fengqi.you@cornell.edu Process scheduling is one key layer of decision hierarchy for process industries to optimize their production schedule in order to gain the long-term economic viability. Besides coordinating limited available resources and satisfying demands on production quantity, quality, and environmental restrictions, the challenge of process scheduling also lies in the treat of uncertainties when approaching the multistage adjustable robust optimization (ARO) of the scheduling problem. In this work, we solve the robust optimization problem for batch process scheduling under uncertainty by using piecewise linear decision rule (PLDR). Based on PLDR and the Dirichlet process Gaussian mixture model (DPGMM) which is for data-driven uncertainty set construction, we demonstrate with an industrial process case study that the combination of the data-driven uncertainty set and the piecewise linear decision rule is capable of generating usually better, at least as good, batch process scheduling optimization solutions in comparison to some conventional ARO approaches. 1. Introduction Process industries are confronted with an increasingly challenging world where competitions motivated by rapidly changing markets, rising material and labour costs, growing complexity of production processes, extending scales of supply chains, and more and more stringent regulatory oversights are unprecedentedly intense and brutal (Chu and You, 2015). It is important for one enterprise to optimize its profit given limited resources and other interior or exterior constraints (Shobrys and White, 2002). Process scheduling is a critical layer of decision hierarchy for batch process enterprises, which has direct influence on process profit and should be considered with full carefulness (Méndez et al., 2006). Accordingly, batch process scheduling optimization is a long-lasting hot topic that receives extensive attention from both industrial community and academic community (Chu et al., 2015). An important feature of process scheduling that has gained much focus recently is process uncertainty. Uncertainty in batch processes could be caused by various factors, such as lack of accurate process models, variability of process and environment data, unpredictable product demands, etc. (Shang et al. 2018). With uncertainty being present, not only do the prevalent deterministic optimization methods for batch process scheduling suffer from performance deterioration, but the implementation of approaches that address static or two-stage robust optimization is also prevented given their inability of dealing with multistage problems (Bertsimas et al., 2011a). The state-of-the-art approach for multistage decision making under uncertainty is the multistage adjustable robust optimization (ARO) (Bertsimas et al., 2009). It is flexible enough to model sequential uncertainty and tractable in terms of achieving feasible solutions (Bertsimas et al., 2011b). However, multistage ARO is too complicated to be directly solved by any off-the-shelf solver (Ning and You, 2017a). Thus, algorithms and strategies to generate optimal solutions for multistage ARO problems have become quite popular in optimization realm for recent years (Shang et al., 2017). Despite prosperous researches on multistage ARO theories, the applications of this modern optimization modelling technique on real-world problems are not common, especially for batch process scheduling (Ning and You, 2017b). Two main reasons could account for this: (1) the formulation of uncertainty set in practical scenarios is always difficult, since uncertainties are caused by various known and unknown factors and cannot be well described by some normal sets of fixed shapes, for example, the box set and the budget set; and (2) the common method for solving multistage optimization problems is the linear decision rule (LDR) which trades DOI: 10.3303/CET1870286 Please cite this article as: Guo C., You F., 2018, Robust optimization for batch process scheduling under uncertainty using piecewise linear decision rule , Chemical Engineering Transactions, 70, 1711-1716 DOI:10.3303/CET1870286 1711 quality of the optimal solution for tractability of the optimization problem and therefore does not always lead to desired results. Given this situation, there is great necessity and benefit to investigate new techniques to approach the multistage ARO for batch process scheduling (Lorca et al. 2016). In this work, we propose to implement the multistage ARO to model a batch process and use Dirichlet process Gaussian mixture model (DPGMM) to formulate the data-driven uncertainty set. Subsequently, the piecewise linear decision rule (PLDR) is adopted for solving the multistage optimization problem with bearable computational complexity. The performance of the proposed method that combines PLDR and the data-driven uncertainty set is demonstrated on a real process scheduling problem. Through comparison with other related approaches, we conclude that the presented general method is adaptive for addressing multistage problems, inexpensive in terms of computational cost, and reliable with respect to generating high-quality solutions. 2. Process scheduling model The multistage ARO formulation of batch process scheduling considered in this work is elaborated as follows, where upper case symbols correspond to variables and lower-case ones correspond to parameters. The objective function of the scheduling model is to maximize the revenue of product sales subtracted from raw material cost as  0, , , , max s.t. Constraints(2) (14) s sN sW T B S G s P S S     S (1) where 𝑠 indicates resources, 𝑆 represents the resource set of materials, 𝑃𝑠 is the price of resource 𝑠, and 𝑆𝑠𝑛 corresponds to the amount of resource 𝑠 at event point 𝑛. The scheduling problem is subject to  ( ) ( ) , , , j n n i inn i inn n i T a T a a W b B j n n               I J N N (2) min max , , ,i inn inn i inn nB W B B W i n n            I N N (3)    1 , , : 1 j jn n jn inn in nj n i in n G G W W j n n                   I IN N J N (4)   out in out in 1 , , s n s n sn is in n is inns n i n i n S S q B q B s n                    I N I N S N (5) 1 0T  (6) NT H (7) 0 1,  ,jnG j n     J N (8) 0, jNG j  J (9) max0 ,  ,sn sS S s n     S N (10) , sN sS d s  S (11) 0,  , , \inn nB i n n         I N N N (12) 0,  , , \inn nW i n n         I N N N (13)  0,1 ,  , ,innW i n n       I N N (14) Specifically, constraint Eq(2) restricts that the time interval between two event points should cover the processing time in each processing unit, where 𝑇𝑛 is the time at the event point 𝑛, 𝐼𝑗 is the set of tasks associated with unit 𝑗, 𝑊𝑖𝑛𝑛’ is a binary variable, as indicated by Eq(14), which equals 1 when task 𝑖 starts at event point 𝑛 and ends before event point 𝑛’, 𝐵𝑖𝑛𝑛’ denotes the batch size, and 𝑎𝑖 and 𝑏𝑖 are the fixed and variable processing time of task 𝑖, respectively. Besides, the set of event points which are after point 𝑛 but within a range of 𝜁 points is represented by 𝑁𝑛 + and those before point 𝑛 and within a range of 𝜁 points are included in the set 𝑁𝑛 −; 𝜁 is a user-defined parameter that should be specified according to the process of concern. Constraint Eq(3) specifies the upper bound and the lower bound of the batch size for each task, with the two bounds being 𝐵𝑖 min and 𝐵𝑖 max. Eq(4) and Eq(5) serve to track the utilization of the processing unit and guarantee material balance, in which 𝐺𝑗𝑛 indicates whether or not the equipment resource 𝑗 is used at event point 𝑛, 𝐼𝑠 in and 𝐼𝑠 out are the sets of tasks 1712 which utilize resource 𝑠 as input and output, and 𝑞𝑠 in and 𝑞𝑠 out are the coefficients for consumption and generation rates of resource 𝑠 by task 𝑖. Constraints Eq(6) and Eq(7) fix the start time and the end time of process scheduling to be 0 and 𝐻. Constraints Eq(8) and Eq(9) constitute explicit bounds for the utilization variable 𝐺𝑗𝑛 and restrict all the equipment to be released at the end of the scheduling. Constraints Eq(10) and Eq(11) indicate that the resource at each event point is bounded above by maximum storage capacity 𝑆𝑠 max and demand for material 𝑠, 𝑑𝑠, should be met at the end of the scheduling horizon. Finally, constraints Eq(12) and Eq(13) prohibit tasks which are instantaneous, have the start time past their end time, or last more than 𝜁 event points. In this work, it is considered that the fixed processing time 𝑎 in Eq(2) is uncertain and 𝑇𝑛 is the recourse decision to be made depending on 𝑎. It has been applied PLDR on 𝑇𝑛 subsequently. 3. Piecewise Linear Decision Rule for Batch Process Scheduling Model Piecewise linear decision rule is one kind of simple but effective decision rule. It limits recourse variables to be piecewise linearly affine in uncertainties and is therefore able to achieve computationally-inexpensive approximation of optimization solutions. The advantage of PLDR is that it allows to implement different linear affine rules for positive and negative perturbations of uncertainties. The cost that comes with this flexibility includes the more complicated decision rule expression and additional effort in lifting the uncertainty set compared with linear decision rule (Georghiou et al., 2015). Moreover, it should be noted that PLDR does not guarantee to lead to better optimization solutions in comparison with LDR, and yet its solutions are at least as good as those obtained by LDR since LDR is one special case of PLDR (Gorissen et al 2015). The LDR and PLDR for the batch process scheduling problem are expressed as 0[ ] [ ] (LDR)n n n i n i n i n T T T a         I N (15) 0[ ] [ ] [ ] [ ] (PLDR)n n n i n i n n i n i n n i n i n i n i n i n T T T a T a T a                                 I N I N I N (16) where [𝑇𝑛]0 is a vector variable and [𝑇𝑛]𝑖′𝑛′′ , [𝑇𝑛]𝑖′𝑛′′ + , and [𝑇𝑛]𝑖′𝑛′′ − are coefficient matrices. The uncertain parameter 𝑎 in PLDR is expanded into (𝑎𝑖′𝑛′′ , 𝑎𝑖′𝑛′′ + , 𝑎𝑖′𝑛′′ − ). For simplicity concern, we give only the data-driven uncertainty set which corresponds to PLDR and is obtained by applying Dirichlet process Gaussian mixture model (Gorur and Rasmussen, 2010) as   ' 1 2 01 , , , , j jn n Ki n i n n i n i i n n i i n i nn n z z lift i n i n n i cc c i n i n i n W a W a j U s n z U U U i n                                                                                      I N I NN N J N Z I N (17) where  , , 0, 0 k k k k k k k k k k k c i n i n i ni n c c i n i n i n c c c i n i n i n i ni n i n i n c c c i n i n i n c c i n i n a a a a a U a a a a                                                                                  (18) In Eq(17) and Eq(18), �̅� represents the nominal value of 𝑎, 𝜎 indicates the magnitude of perturbation, and 𝛿 is a support variable. Besides, 𝑎𝑖′ 0 and 𝜙𝑖’ in the uncertainty set are known process parameters; Θ𝑛′′ and Γ𝑖′𝑛′′ 𝑐𝑘 are the uncertainty budget specified by the decision maker; 𝑈𝑖′𝑛′′ 𝑐𝑘 is the data-driven uncertainty subset corresponding to task 𝑖’ and event point 𝑛’’, which is obtained by DPGMM; its index 𝑐𝐾𝑖′𝑛′′ indicates the quantity of data-driven subsets and varies over 𝑖′ and 𝑛’’; at last, 𝑍 represents the set of permutations, denoted by 𝑧, of uncertainty subsets in different tasks and different periods. Based on constraint Eq(2), Eq(16), Eq(17), and Eq(18), dual constraint formulation is obtained as Eq(19-26). 1713    0 0 0 1 [ ] [ ] , j j jnn z jnn z jnn z jnn z jnn zz z z z z i i i n i n i n i n n i nj i n i n i n i n n j i n i n n i n n i inn i a S Q a R a M O T T b B z                                                                  J I N I N N I I Z (19)  , 1 [ ] [ ] , ,, j jnn z jnn z jnn z i n n n i n n i nj i n i n i n i n n j S R M W T T i n z                                  I J I N Z (20) , ,[ ] [ ] , , jnn z jnn z jnn z jnn zz i n n i n n i ni n i n i n n i i i Q R M O T T i n z                                     I I N Z (21) , ,[ ] [ ] , , jnn z jnn z jnn z jnn zz i n n i n n i ni n i n i n n i i i Q R M O T T i n z                                     I I N Z (22) 1 , ,, , n jnn z jnn z i n n j i n j n W S P j i n z                          N J I N Z (23) ,0 0 ,, , n jnn z i n n j i n n W S j i n z                        N J I N Z (24) ,, ,, jnn z jnn z j i n jS P j i n z                 J I N Z (25) , , , , , ,, 0 , , jnn jnn jnn jnn jnn jnn z i n i n i n j i n i n nP Q R S M O j i n z                             J I N Z (26) where 𝑀, 𝑂, 𝑃, 𝑄, and 𝑅 are dual variables and 𝑆 is a support variable as '' ' ' ' ' '' ' ''' '' ' ''' , , , , n jnn z jnn z j i n i n n j n S W j iP n z                      N J I N Z (27) Till now, the multistage ARO for process scheduling can be directly solved by common optimization solvers. 4. Case study An industrial multi-purpose batch process in The Dow Chemical Company (Chu et al., 2013) is considered to demonstrate the effectiveness and efficiency of the proposed multistage ARO approach. As shown in Figure 1, the batch process is constituted by one preparation task, three reaction tasks, two packing tasks, and two drumming tasks, which are processed through four equipment units, namely, one mixer, one reactor, one finishing system, and one drumming system (Chu et al., 2014). Four raw material (M1-M4), six intermediates (I1-I6), and four products (P1-P4) are involved, and the mass balance coefficients are given in Figure 1. The scheduling horizon is 168 h, and the fixed processing time of each task is subject to uncertainty. Figure 1: Batch process network structure 1714 Following the multistage ARO framework, we solve the scheduling problem for this batch process with different approaches. The Gantt charts obtained by LDR with the common box-budget uncertainty set, PLDR with the common box-budget uncertainty set, LDR with the data-driven uncertainty set construction, and PLDR with the data-driven uncertainty set construction are shown in Figure 2 to Figure 3. All computations are performed using CPLEX 12 in GAMS on a desktop computer with Intel Core i7-6700 processor at 3.40 GHz and 32 GB of RAM. Figure 2: Scheduling Gantt chart by using LDR (left) and PLDR (right), respectively, with the box-budget uncertainty set Figure 3: Scheduling Gantt chart by using LDR (left) and PLDR (right), respectively, with the data-driven uncertainty set According to these results, PLDR has the same optimal objective function value as LDR if they are applied with the same uncertainty set (17,546.939 for the box-budget uncertainty set and 18,220.195 for the data-driven uncertainty set), which, considering the simplicity of the uncertainties involved in this case, is quite reasonable. The improvement in flexibility for PLDR does not necessarily lead to better optimality, but, as mentioned, it is certain that the optimal solution obtained by PLDR is at least as good as that obtained by LDR. Besides, although LDR and PLDR lead to the same optimal objective function value, their solutions are different as shown by the Gantt charts in Figure 2 and Figure 3. Specifically, each block in the Gantt charts represents a task processed by a corresponding equipment unit. The block location indicates the start and the end time points of the task, while the block width shows the task processing time. Regardless of the type of decision rules and uncertainty sets, scheduling optimization solutions all suggest that the batch process begins with a preparation task at time point 0 and stops after the end of a drumming task at time point 168. Since the objective of batch process scheduling is to maximize the net revenue as indicated by Eq(1), the difference between scheduling solutions which have the same objective function value is not important with respect to achieving the highest production profit. From the perspective of computational complexity, PLDR is much more efficient and takes far less computing time than LDR, especially for the cases in which data-driven uncertainty sets are used (computing time is 112,441.28 s for LDR and 3,656.94 s for PLDR). The reason behind is that PLDR can easily handle positive and negative perturbations involved in the batch process scheduling model while LDR is not flexible enough to match with PLDR in this aspect according to Eq(15) and Eq(16). On the other hand, the advantage of employing the data-driven uncertainty set is rather remarkable, as the increase in production profit is around 4 % compared with the case where a general box and budget uncertainty set is implemented. This is mainly because DPGMM could obtain a union of several convex uncertainty subsets, each of which is expressed by 𝑙-1 norm and 𝑙-infinity norm constraints, and thus narrow the size of the overall uncertainty set in comparison with the common box-budget set (Ning and You, 2018). It is notable that the 1715 computational complexity is also increased when using the data-driven uncertainty set according to the computing time, and yet the processing time for PLDR with the data-driven set construction is durable in general. 5. Conclusions Batch process scheduling under uncertainty is a critical and challenging problem that can be formulated with the multistage adjustable robust optimization model. Given that the conventional box and budget uncertainty sets and approximation approaches such as the linear decision rule could, especially in practical cases, lead to over-conservative and unreliable optimization solutions, in this work, we introduced the Dirichlet process Gaussian mixture model to construct the data-driven uncertainty set and employ piecewise linear decision rule for addressing the multistage ARO of batch process scheduling. We demonstrated with a real industrial case the power of the data-driven uncertainty set and the utilization of PLDR in terms of the quality of the optimal solution and computational complexity. Future work will be focused on studying advanced data-driven uncertainty set construction methods and implementing more generalized piecewise linear decision rules in batch process scheduling optimization. References Bertsimas D., Iancu D.A., Parrilo P.A., 2009, Optimality of affine policies in multi-stage robust optimization, in Proceedings of the IEEE Conference on Decision and Control, 1131-1138. Bertsimas D., Brown D.B., Caramanis C., 2011a, Theory and applications of robust optimization, SIAM Review, 53, 464-501. Bertsimas D., Iancu D.A., Parrilo P.A., 2011b, A hierarchy of near-optimal policies for multistage adaptive optimization, IEEE Transactions on Automatic Control, 56, 2809-2824. Chu Y., Wassick J.M., You F., 2013, Efficient scheduling method of complex batch processes with general network structure via agent-based modeling. AIChE Journal, 59, 2884-2906. Chu Y., You F., Wassick J.M., 2014, Hybrid method integrating agent-based modeling and heuristic tree search for scheduling of complex batch processes. Computers & Chemical Engineering, 60, 277-296. Chu Y., You F., 2015, Model-based integration of control and operations: Overview, challenges, advances, and opportunities. Computers & Chemical Engineering, 83, 2-20. Chu Y., You F., Wassick J.M., Agarwal A., 2015, Integrated planning and scheduling under production uncertainties: Bi-level model formulation and hybrid solution method, Computers and Chemical Engineering, 72, 255-272. Georghiou A., Wiesemann W., Kuhn D., 2015, Generalized decision rule approximations for stochastic programming via liftings, Mathematical Programming, 152, 301-338. Gorissen B. L., Yanıkoğlu İ., den Hertog D., 2015, A practical guide to robust optimization, Omega, 53, 124- 137. Gorur D., Rasmussen C.E., 2010, Dirichlet process gaussian mixture models: Choice of the base distribution, Journal of Computer Science and Technology, 25, 653-664. Lorca T., Sun A., Litvinov A., Zheng E., 2016, Multistage Adaptive Robust Optimization for the Unit Commitment Problem, Operations Research, 64, 32-51. Méndez C.A., Cerdá J., Grossmann I.E., Harjunkoski I., Fahl M., 2006, State-of-the-art review of optimization methods for short-term scheduling of batch processes. Computers & Chemical Engineering, 30, 913-946. Ning C., You F., 2017a, Data-driven adaptive nested robust optimization: General modeling framework and efficient computational algorithm for decision making under uncertainty, AIChE Journal, 63, 3790-3817. Ning C., You F., 2017b, A data-driven multistage adaptive robust optimization framework for planning and scheduling under uncertainty, AIChE Journal, 63, 4343-4369. Ning C., You F., 2018, Data-driven stochastic robust optimization: General computational framework and algorithm leveraging machine learning for optimization under uncertainty in the big data era. Computers & Chemical Engineering, 111, 115-133. Ning C., You F., 2018, Data-driven decision making under uncertainty integrating robust optimization with principal component analysis and kernel smoothing methods. Computers & Chemical Engineering, 112, 190- 210. Shang C., Huang X., You F., 2017, Data-driven robust optimization based on kernel learning. Computers & Chemical Engineering, 106, 464-479. Shang C., You F., 2018, Distributionally robust optimization for planning and scheduling under uncertainty. Computers & Chemical Engineering, 110, 53-68. Shobrys D.E., White D.C., 2002, Planning, scheduling and control systems: why cannot they work together. Computers & Chemical Engineering, 26, 149-160. 1716