Scheduling acyclic branching programs on parallel machines

In this paper we address the following problem: given an acyclic program scheme with if-then-else control structures, together with the duration of each procedure, and given an architecture consisting of n identical processors, compute offline a scheduling policy that guarantees minimal execution time (in the worst-case) for the entire program on this architecture. Since this is a problem of scheduling under uncertainty (the results of the branching decisions are not known in advance) it cannot be solved in a satisfactory manner using static or fixed priority schedulers but rather requires a state-dependent scheduling strategy. We use timed automata technology to derive such strategies using algorithms for finding shortest paths on game graphs.