Optimal Control of Multi-Stage Discrete Event Systems With Real-Time Constraints

We consider Discrete Event Systems involving tasks with real-time constraints and seek to control processing times so as to minimize a cost function subject to each task meeting its own constraint. When tasks are processed over a single stage, it has been shown that there are structural properties of the optimal state trajectory that lead to very efficient solutions of such problems. When tasks are processed over multiple stages and are subject to end-to-end real-time constraints, these properties no longer hold and no obvious extensions are known. We consider such a multi-stage problem with not only stage-dependent but also task-dependent cost functions over all tasks at each stage and derive several new optimality properties. These properties lead to the idea of introducing virtual deadlines at each stage except the last one, thus partially decoupling the stages so that the known efficient solutions for single-stage problems can be used. We prove that a sequence of solutions to single-stage problems with virtual deadlines updated at each step converges to the global optimal solution of the multi-stage problem. This leads to a Virtual Deadline Algorithm (VDA) which is scalable in the number of processed tasks. We illustrate the scalability and efficiency of the VDA through numerical examples.