An Efficient Branch-and-Satisfy Technique for Offline Scheduling of Hard Real-time Systems
Vinod C Bhat · OhioLink ETD Center (Ohio Library and Information Network) · 2004
Hard real-time systems require accurate results in a timely fashion.Given the specifications for a hard real-time system one must identify a feasible schedule for the tasks on the specified hardware.Previous research has been done to formulate real-time scheduling problems, develop solution techniques, modify search spaces to improve algorithmic performance, and create new heuristics.Choosing among scheduling techniques like simulated annealing and heuristics requires a trade-off assessment between the computation time and the number of legal schedules tested.This research deals with the static scheduling of hard real-time operators.It presents the application of a Branch-and-Satisfy technique to solve this optimization problem by formulating and solving a series of LP problems by iteratively branching adding disjunctive constraints.This reduces the search space on each iteration which leads to a solution approach with the advantage of being fast while considering the entire search space.