(745d) Robust Recursive Feasibility for Closed-Loop (Online) Scheduling

In closed-loop or online scheduling, the realization of uncertainty in plant operations is addressed in real-time though consistent and frequent reoptimization and rescheduling (Gupta and Maravelias, 2016). This frequent rescheduling, however, introduces complex dynamics into the facility's operation and may render the dynamic behavior of closed-loop scheduling difficult to interpret or quantify for a general scheduling problem. This complexity persists even in the nominal scenario, i.e., no disturbances and a perfect model. By representing the production scheduling problem in a state-space formulation, closed-loop scheduling can be cast as an economic model predictive control (MPC) problem (Subramanian et al., 2012). This approach allows us to leverage the results developed in the MPC community to provide insights and theoretical guarantees for the dynamic behavior of closed-loop scheduling.

A particularly useful theoretical result from the economic MPC literature is the nominal performance guarantee afforded by terminal equality constraints. By constraining the individual open-loop optimizations to terminate along a reference trajectory, we can guarantee that the nominal closed-loop cost is no worse than that of the reference trajectory. Furthermore, we can guarantee that the optimization problem is recursively feasible, i.e., the optimization problem remains feasible along any potential nominal closed-loop trajectory. This terminal equality constraint, unfortunately, reduces the flexibility of the optimization problem and provides no guarantees of robust recursive feasibility, i.e., recursive feasibility for the closed-loop trajectory subject to relevant disturbances. In practice, terminal constraints are often omitted or approximated to ensure robust recursive feasibility and the nominal performance guarantee no longer applies.

In this work, we develop a formulation for general production scheduling problems that ensures robust recursive feasibility and maintains the desired nominal performance guarantee. We achieve this goal by first identifying the state variables in the scheduling problem formulation responsible for infeasible optimization problems. Through small modifications to the scheduling problem formulation, we improve the controllability of these variables. We use this additional controllability to systemically construct an expanded terminal constraint and corresponding terminal cost that still ensure the same nominal performance guarantee.

To ensure robust recursive feasibility, we first identify the types of constraints and state variables that create infeasible optimization problems. We note that state and input constraints in scheduling problems, aside from the terminal constraint, exist only to enforce physically realistic decisions, e.g., no negative inventory. Thus, disturbances cannot force violations of these constraints and we instead focus on the terminal constraint. For production scheduling, we partition the state variables into three types: (1) facility variables, (2) inventory, and (3) backlog. Facility variables (e.g. task progression, operational levels) are bounded and, with reasonable horizon lengths, can be driven to any point on the reference trajectory from any initial condition. Thus, we maintain the terminal equality constraint for these variables. Inventory and backlog states, however, cannot always be driven to the reference trajectory and are the main cause of infeasible optimization problems. For example, if backlog becomes significantly large, due to increased demand or production delays, we may not be able to remove this large backlog and reach the reference trajectory by the end of the horizon. Increasing the horizon length may solve this problem in practice, but the increase in computational demand is undesirable for online implementations.

In many (economic) MPC implementations, the terminal equality constraint can be expanded to a terminal region with an appropriate terminal cost function (Amrit et al., 2011, Rawlings et al., 2017, s 2.5). Scheduling problems, however, do not inherently satisfy the weak controllabiltiy assumptions required for this approach. Thus, we propose guaranteeing weak controllabiltiy of inventory and backlog state variables by including additional decision variables in the problem formulation. These decisions include disposal of excess inventory and canceling (or outsourcing) of excessive backlog. Both of these options are assessed a sufficient cost and are bounded in the optimization problem. We use these additional decision variables to systematically construct an appropriate terminal cost and expand the terminal constraint to include all nonnegative values of storage and backlog. This terminal cost ensures that the nominal performance guarantee holds, and the expanded terminal constraint ensures robust recursive feasibility of the optimization problem.

These modifications allow closed-loop scheduling implementations to ensure robust recursively feasibility without sacrificing the nominal performance guarantee. Thus, the algorithm guarantees performance under nominal conditions, but remains feasible when disturbances occur. Furthermore, by ensuring robust recursive feasibility we can derive a performance guarantee for even the perturbed system, i.e., a robust performance guarantee. Through several examples, we demonstrate the benefits and implications of these modifications, particularly for short horizons and facilities operating near maximum capacity.

References

Amrit, R., Rawlings, J.B., and Angeli, D., 2011, Economic optimization using model predictive control with a terminal cost. Annual Rev. Control. 35, 178-186.

Angeli, D., Amrit, R., and Rawlings, J.B., 2012. On average performance and stability of economic model predictive control. IEEE Trans. Auto. Cont. 57, 1615-1626.

Gupta, D. and Maravelias, C., 2016. On deterministic online scheduling: Major considerations, paradoxes and remedies. Comput. Chem. Eng. 94, 312-330.

Rawlings, J.B., Mayne, D.Q., and Diehl, M.M., 2017. Model Predictive Control: Theory, Design, and Computation. Nob Hill Publishing, Madison, WI, 2nd edition.

Subramanian, K., Maravelias, C.T., and Rawlings, J.B., 2012. A state-space model for chemical production scheduling. Comput. Chem. Eng. 47, 97-160.