Optimal scheduling for constant-rate multi-mode systems
Optimal scheduling for constant-rate multi-mode systems
复制标题
恒定速率多模系统的优化调度
DOI：
10.1145/2185632.2185647
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Alur R
中科院分区：
文献类型：
--
作者：
Alur R
恒速率多模系统是可以在有限模态间自由切换的混合系统，其动力学由有限数量的与模态相关的恒速率实值变量来表示。这类系统的可调度性问题是设计一种模式切换策略，使状态保持在指定的安全集中。本文的主要结果是可调度性可以在多项式时间内确定。我们还将结果推广到具有平均成本和可达性成本目标的最优可调度性问题。多项式时间调度算法使该类成为能源优化策略设计的一个吸引人的正式模型。可跟踪性的关键在于，调度程序何时可以切换模式的唯一约束是由全局目标指定的。通过将不变量与模式关联，或将保护与模式开关关联来添加局部约束，会导致不可判定性，并要求调度器仅以给定采样率的倍数做出决策，从而导致pspace完全可调度性问题。
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.
克罗诺斯
DOI：
10.1163/2452-3054_dnpo5_com_0076
发表时间：
1978
期刊：
Cahiers jungiens de psychanalyse
影响因子：
--
作者：
James Hillman;M. Salzmann
通讯作者：
M. Salzmann
尽可能便宜地维持生命
DOI：
--
发表时间：
2004
期刊：
International Conference on Hybrid Systems: Computation and Control
影响因子：
--
作者：
P. Bouyer;E. Brinksma;K. Larsen
通讯作者：
K. Larsen
矩形混合自动机的离散时间控制
DOI：
10.1016/s0304-3975(99)00038-9
发表时间：
1997
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
T. Henzinger;P. Kopke
通讯作者：
P. Kopke