Scheduling with timed automata

In this work, we present timed automata as a natural tool for posing and solving scheduling problems. We show how efficient shortest path algorithms for timed automata can find optimal schedules for the classical job-shop problem. We then extend these results to synthesize adaptive scheduling strategies for problems with uncertainty in task durations.

Authors

• Yasmina Abdeddaı¨m
• Eugene Asarin
• Oded Maler

Keywords

• Scheduling
• Verification and synthesis
• Timed automata