On Optimal Scheduling under Uncertainty

In this work we treat the problem of scheduling under two types of temporal uncertainty, setbased and probabilistic. For the former we define appropriate optimality criteria and develop an algorithm for finding optimal scheduling strategies using a backward reachability algorithm for timed automata. For probabilistic uncertainty we define and solve a special case of continuoustime Markov Decision Process. The results have been implemented and were applied to benchmarks to provide a preliminary assessment of the merits of each approach