2004 · 52 citations · 10 references
ComputingComputer EngineeringComputer ScienceParallel ComputingReal-time SystemsSchedulingAutomata TheoryDeadline AnalysisReal-time SchedulingSchedulability AnalysisTask ModelsTask SchedulingReal-time System VerificationReal-time Task SchedulingScheduling ProblemsScheduling With DeadlinesTask Graph ModelsTask Graph SchedulingTask GraphsTimed Automata
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.
10
Rajeev Alur, David L. Dill · Theoretical Computer Science · 1994 · 6.5K citations
A Decomposition Theorem for Partially Ordered Sets
R. P. Dilworth · Annals of Mathematics · 1950 · 987 citations
Model-checking for real-time systems
Rajeev Alur, Costas Courcoubetis, David L. Dill · 2002 · 894 citations
Symbolic Model Checking for Real-Time Systems
Thomas A. Henzinger, Xavier Nicollin, Joseph Sifakis et al. · Information and Computation · 1994 · 830 citations · Full text