Alur/Trivedi/Wojtczak: Optimal Scheduling for Constant-Rate Multi-Mode System.

Optimal Scheduling for Constant-Rate Multi-Mode System

Rajeev Alur, Ashutosh Trivedi, and Dominik Wojtczak

Constant-rate multi-mode systems are hybrid systems that can switch freely among a finite set of modes, and whose dynamics is specified by a finite number of real-valued variables with mode-dependent constant rates. The schedulability problem for such systems is to design a mode-switching policy that maintains the state within a specified safety set. The main result of the paper is that schedulability can be decided in polynomial time. We also generalize our result to optimal schedulability problems with average cost and reachability cost objectives. Polynomial-time scheduling algorithms make this class an appealing formal model for design of energy-optimal policies. The key to tractability is that the only constraints on when a scheduler can switch the mode are specified by global objectives. Adding local constraints by associating either invariants with modes, or guards with mode switches, lead to undecidability, and requiring the scheduler to make decisions only at multiples of a given sampling rate, leads to a PSPACE-complete schedulability problem.

Proceedings of the 15th ACM international conference on Hybrid Systems: Computation and Control, HSCC 2012, Pages 75-84, ACM.