Task graph scheduling using timed automata

Yasmina Abdeddaïm, Abdelkarim Aziz Kerbaa, Oded Maler

2004 · 52 citations · 10 references

Concepts

Abstract

In this paper we develop a methodology for treating the problem of scheduling partially-ordered tasks on parallel machines. Our framework is based on the timed automaton model, originally developed for verification of real-time programs and digital circuits and more recently adapted for solving time-optimal scheduling problems. In this framework, the scheduling problem admits a state-space representation and an optimal schedule corresponds to a shortest path in the timed automaton. We check our implementation on numerous benchmarks and show how release times and deadlines can be easily incorporated into the model.

References

10