U. Hönig (Germany)
Task Graph, List scheduling, Metaheuristics, Firefly algorithm.
A careful planning is required to facilitate an effective and efficient execution of a program on a parallel computer sys tem. For this purpose, parallel programs are commonly de scribed by means of task graphs whose nodes represent the individual tasks and whose edges comply to the data depen dencies among these tasks. Scheduling task graphs with the objective to minimize the schedules’ lengths is known to be NP-hard. For this reason, a large number of heuristics and metaheuristics have been developed to solve this task graph scheduling problem. Although firefly algorithms were al ready utilized for optimization purposes in general, the here presented FireflyLS-algorithm is to our best knowl edge the first approach that applies the firefly metaheuris tic in the context of task graph scheduling. We compare the proposed approach with some well-known scheduling heuristics by means of a comprehensive test bench with 36000 task graph scheduling problems. Besides the run time of the heuristics, we also analyze the quality of the computed schedules regarding several performance charac teristics. The presented algorithm requires less computing time than all other metaheuristics we have analyzed until now but is nevertheless able to produce competitive results regarding the other performance measures.
Important Links:
Go Back
