A scheduling algorithm for multi-processor real-time systems with relative timing constraints and resource restrictions
Atsushi Togawa, Eiji Okubo · Systems and Computers in Japan · 1997
In this paper, a scheduling algorithm for multi-processor real-time systems with relative timing constraints and resource constraints is proposed. The proposed algorithm has the capability to satisfy any timing constraints expressed as inequalities in two variables and a constant. This implies that scheduling problems imposed on various timing constraints such as end-to-end timing constraints and/or relative timing constraints, which are known to be difficult to handle, can be solved. Since the problem addressed in this paper is a generalization of some NP-complete problems, it is difficult to solve efficiently. Thus, the goal of the authors is to derive a heuristic algorithm which performs well on many instances of the problem, although in some cases it will take enormous space and time. Experimental results show that the proposed algorithm achieves a success rate of 80% in 3 minutes of computation time. © 1997 Scripta Technica, Inc. Syst Comp Jpn, 28(3): 52–61, 1997