An evolutionary approach to multiprocessor scheduling of dependent tasks

The scheduling of application tasks is a problem that occurs in all multipr ocessor systems. This problem has been shown to be NP-hard if the tasks are not independent but are interrelated by mutual exclusion and precedence co nstraints. This paper presents an approach for pre-runtime scheduling of periodic task s on multiple processors for a real-time system that must meet hard deadlin es. The tasks can be related to each other by mutual exclusion and preceden ce forming an acyclic graph. The proposed scheduler is based on genetic alg orithms, which relieves the user from knowing how to construct a solution. Consequently, the paper focuses on the problem encoding, i.e., the represen tation of the problem by genes and chromosomes, and the derivation of an ap propriate fitness function. The main benefit of the approach is that it is scalable to any number of processors and can easily be extended to incorpor ate further requirements. (C) 1998 Elsevier Science B.V. All rights reserve d.