An efficient scheduling algorithm for distributed real-time systems with end-to-end timing constraints

This paper proposes an efficient scheduling algorithm for distributed real-time systems with such timing constraints as jitter and end-to-end timing. Conventionally, backtrack searching and annealing methods have been used for scheduling problems when timing constraints are complicated. These methods, however, need a lot of computation. This paper proposes a heuristic scheduling method which solves the problem without backtrack scheduling. The proposed method has the merit that the constraints applied to processor scheduling can also be applied to network scheduling. Furthermore, the proposed method can be applied to a network system which is not provided with real-time communications functions, because the proposed method arbitrates communications at a scheduling time. Computer simulations in this paper show that the proposed method provides flexible scheduling capability and can achieve efficient scheduling. © 1999 Scripta Technica, Syst Comp Jpn, 30(13): 43–51, 1999