(761f) Adjustable Robust Optimization for Multi-Tasking Scheduling with Reprocessing of Imperfect Tasks

Lappas, N., Carnegie Mellon University
Fukasawa, R., University of Waterloo
Ricardez-Sandoval, L. A., University of Waterloo
Gounaris, C. E., Carnegie Mellon University
The optimal scheduling of operations has progressively become more challenging due to the ever-increasing complexity of production networks and the agile competition that necessitates the transition to more versatile production schemes [1]. Therefore, a variety of short-term, multi-purpose process scheduling models have been proposed in the literature [2]–[4] that are pertinent to numerous real-life production environments. One of the cases that up until recently had not been investigated pertains to multi-tasking, where multiple tasks are being processed simultaneously by the same processing unit.

Multi-tasking scheduling is vital for the analytical services industry (ASI), where samples originating from different orders must undergo a number of processing steps (tasks) that are typically order-specific. These tasks are executed by processing units that are capable of handling samples from different orders, giving rise to a multi-tasking scheduling problem. Recent works have treated this as a multi-commodity flow problem with a discrete time grid [5], and later as a special case of multi-purpose environment [6] using a modified continuous time, slot-based formulation [7]. In both cases, however, parameter uncertainty was not considered.

Uncertainty is of paramount importance in process scheduling, since optimization under nominal conditions can lead to suboptimal, or even infeasible solutions, in view of the actual realized values of the uncertain parameters [8]. Some of the main sources of uncertainty, also relevant to ASI, are variations in raw materials specifications, or fluctuations in operating conditions of the processing units that may result to imperfect products requiring reprocessing to meet the standards.

To address reprocessing of imperfect tasks, we present a systematic way of modeling it via the introduction of recycle streams in conjunction with uncertain variability in the associated production yields. To that end, we introduce a State-Task-Network representation for multi-tasking environments with recycles. This representation also allows the utilization of any multi-purpose scheduling model with only minor adaptation of the material balance and state level related constraints. Using a global event based model [9], we show the application of the multi-stage Adjustable Robust Optimization framework [10] and its ability to overcome the limitation of traditional Robust Optimization by obtaining solutions that maintain their feasibility, despite the existence of uncertainty in the production yields of imperfect tasks. Finally, we present a comprehensive computational study across multi-tasking scheduling benchmark problems for various levels of uncertainty, which allows us to assess both the quality of the robust solutions as well as the computational effort required to obtain those.


[1] I. Harjunkoski, C. T. Maravelias, P. Bongers, P. M. Castro, S. Engell, I. E. Grossmann, J. Hooker, C. A. Méndez, G. Sand, and J. M. Wassick, “Scope for industrial applications of production scheduling models and solution methods,” Comput. Chem. Eng., vol. 62, pp. 161–193, 2014.

[2] C. A. Méndez, J. Cerdá, I. E. Grossmann, I. Harjunkoski, and M. Fahl, “State-of-the-art review of optimization methods for short-term scheduling of batch processes,” Comput. Chem. Eng., vol. 30, no. 6–7, pp. 913–946, 2006.

[3] C. A. Floudas and X. Lin, “Mixed Integer Linear Programming in Process Scheduling: Modeling, Algorithms, and Applications,” Ann. Oper. Res., vol. 139, no. 1, pp. 131–162, 2005.

[4] M. Baldea and I. Harjunkoski, “Integrated production scheduling and process control: A systematic review,” Comput. Chem. Eng., vol. 71, pp. 377–390, 2014.

[5] B. P. Patil, R. Fukasawa, and L. A. Ricardez-Sandoval, “Scheduling of Operations in a Large-Scale Scientific Services Facility via Multicommodity Flow and an Optimization-Based Algorithm,” Ind. Eng. Chem. Res., vol. 54, no. 5, pp. 1628–1639, 2015.

[6] S. Lagzi, R. Fukasawa, and L. Ricardez-Sandoval, “A multitasking continuous time formulation for short-term scheduling of operations in multipurpose plants,” Comput. Chem. Eng., vol. 97, pp. 135–146, 2017.

[7] S. Gupta and I. A. Karimi, “An Improved MILP Formulation for Scheduling Multiproduct, Multistage Batch Plants,” Ind. Eng. Chem. Res., vol. 42, no. 11, pp. 2365–2380, 2003.

[8] Z. Li and M. G. Ierapetritou, “Process scheduling under uncertainty: Review and challenges,” Comput. Chem. Eng., vol. 32, no. 4–5, pp. 715–727, 2008.

[9] P. M. Castro, A. P. Barbosa-po, H. A. Matos, and A. Q. Novais, “Simple Continuous-Time Formulation for Short-Term Scheduling of Batch and Continuous Processes,” Ind. Eng. Chem. Res., vol. 43, no. 1, pp. 105–118, 2004.

[10] N. H. Lappas and C. E. Gounaris, “Multi-stage adjustable robust optimization for process scheduling under uncertainty,” AIChE J., vol. 62, no. 5, pp. 1646–1667, 2016.