Multi-heuristic list scheduling genetic algorithm for task scheduling

ABSTRACT

Scheduling tasks on a multi-processor system involves making a choice as to the order in which several tasks can be executed and assigned to processors. The problem is to find a schedule that will minimize the execution time of a program. Because task scheduling on a multi-processor system is known to be an NP-complete problem, many heuristics have been developed, each of which may find optimal or near optimal schedulings under different circumstances. List Scheduling, in particular, employs heuristics to choose among all tasks that are ready to be executed, the combination of tasks that should be scheduled in the next cycle. It does this by keeping a list of "ready" tasks which is prioritized based on a particular heuristic. In this paper, we present four common heuristics used by List Scheduling and compare their performance with that of our multi-heuristic based solution.The proposed solution is to use a genetic algorithm to find a combination of the four heuristics that, for a particular instance of the task scheduling problem, outperforms a scheduling based on only one of the four heuristics. We believe that, by using a mixture of the four heuristics, the size of the subset of all possible schedulings that we search increases and thus we have a higher chance of finding a better scheduling. The results of our experiments show that schedulings found with the proposed multi-heuristic list scheduling genetic algorithm outperforms those found with each one of the four list scheduling heuristics alone.

REFERENCES

• 1: Gary J. Nutt, Centralized and distributed operating systems, Prentice Hall Press, Upper Saddle River, NJ, 1991
• 2: Albert Y. H. Zomaya, Parallel and distributed computing handbook, McGraw-Hill, Inc., New York, NY, 1996
• 3: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 4: Thomas L. Adam , K. M. Chandy , J. R. Dickson, A comparison of list schedules for parallel processing systems, Communications of the ACM, v.17 n.12, p.685-690, Dec 1974 [doi>10.1145/361604.361619]
• 5: Hesham El-Rewini , Theodore G. Lewis , Hesham H. Ali, Task scheduling in parallel and distributed systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 6: Ted G. Lewis , Hesham El-Rewini, Introduction to parallel computing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 7: E. S. H. Hou , N. Ansari , H. Ren, A Genetic Algorithm for Multiprocessor Scheduling, IEEE Transactions on Parallel and Distributed Systems, v.5 n.2, p.113-120, February 1994 [doi>10.1109/71.265940]
• 8: C. L. Chen, C. S. G. Lee, and E. S. H. Hou. Efficient scheduling algorithms for robot inverse dynamics computation on a multiprocessor system. IEEE Trans. Syst., Man, Cybernetics., Vol. 18, 729--743, 1998.
• 9: Yu-Kwong Kwok , Ishfaq Ahmad, Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.7 n.5, p.506-521, May 1996 [doi>10.1109/71.503776]
• 10: Benjamin J. Hellstrom , Laveen N. Kanal, Asymmetric mean-field neural networks for multiprocessor scheduling, Neural Networks, v.5 n.4, p.671-686, July-Aug. 1992 [doi>10.1016/S0893-6080(05)80044-9]
• 11: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 12: Arthur L. Corcoran , Roger L. Wainwright, A parallel island model genetic algorithm for the multiprocessor scheduling problem, Proceedings of the 1994 ACM symposium on Applied computing, p.483-487, March 06-08, 1994, Phoenix, Arizona, United States [doi>10.1145/326619.326817]

INDEX TERMS

Keywords:
genetic algorithms, list scheduling, task scheduling