Genetic list scheduling for soft real-time parallel applications

This paper presents a hybrid algorithm that combines list scheduling with a genetic algorithm for constructing nonpreemptive schedules for soft real-time parallel applications represented as directed acyclic graphs. The execution time requirements of the applications´ tasks are assumed to be stochastic and are represented as probability distribution functions. The approach presented here produces shorter schedules than two popular list scheduling approaches for a majority of sample problems. Furthermore, the stochastic schedules provide a mechanism for predicting the probability of the application completing when the execution time available is less than the worst case requirement.