Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
As Soon as Probable: Optimal Scheduling under Stochastic Uncertainty
verfasst von : Jean-François Kempf, Marius Bozga, Oded Maler
Erschienen in: Tools and Algorithms for the Construction and Analysis of Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper we continue our investigation of stochastic (and hence dynamic) variants of classical scheduling problems. Such problems can be modeled as duration probabilistic automata (DPA), a well-structured class of acyclic timed automata where temporal uncertainty is interpreted as a bounded
uniform distribution
of task durations [18]. In [12] we have developed a framework for computing the expected performance of a
given
scheduling policy. In the present paper we move from
analysis
to
controller synthesis
and develop a dynamic-programming style procedure for automatically synthesizing (or approximating)
expected time optimal
schedulers, using an iterative computation of a
stochastic time-to-go
function over the state and clock space of the automaton.