EVALUATION OF STATIC SCHEDULING HEURISTICS FOR REAL-TIME MULTIPROCESSING
Behrooz Shirazi, Hee Yong Youn, Daniel M. Lorts · Parallel Processing Letters · 1995
Suboptimal solutions to the NP-complete problem of scheduling in a multiprocessing system are achievable with the aid of heuristic methods. Development and evaluation of static scheduling heuristics for real-time multiprocessing systems have inherited techniques from work for non-real-time systems. Unfortunately, the existing techniques compromise the results of the scheduling effort by limiting the scope of the problem. In this paper we present results of experimentation in which the parameters of the Directed Acyclic Graph (DAG) are enhanced to more correctly correspond to those of a real-world application. A method of specifying weighted combinations and priorities of simple scheduling heuristics to the scheduling algorithm is presented. Results of the compound heuristics are compared to the results of previous work in the field with some interesting conclusions.