×

zbMATH — the first resource for mathematics

Genetic algorithms for task scheduling problem. (English) Zbl 1233.68077
Summary: The scheduling and mapping of the precedence-constrained task graph to processors is considered to be the most crucial NP-complete problem in parallel and distributed computing systems. Several genetic algorithms have been developed to solve this problem. A common feature in most of them has been the use of chromosomal representation for a schedule. However, these algorithms are monolithic, as they attempt to scan the entire solution space without considering how to reduce the complexity of the optimization process. In this paper, two genetic algorithms have been developed and implemented. Our developed algorithms are genetic algorithms with some heuristic principles that have been added to improve the performance. According to the first developed genetic algorithm, two fitness functions have been applied one after the other. The first fitness function is concerned with minimizing the total execution time (schedule length), and the second one is concerned with the load balance satisfaction. The second developed genetic algorithm is based on a task duplication technique to overcome the communication overhead. Our proposed algorithms have been implemented and evaluated using benchmarks. According to the evolved results, it has been found that our algorithms always outperform the traditional algorithms.

MSC:
68M14 Distributed systems
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
Software:
Hypertool
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] I. Ahmad, Y. Kwok, A new approach to scheduling parallel programs using task duplication, in: Proceeding of the 23rd International Conf. on Parallel Processing, August 1994, North Carolina State University, NC, USA, 1994
[2] Ahmad, I.; Kwok, Y.: Benchmarking and comparison of the task graph scheduling algorithms, J. parallel distrib. Comput. 95, 381-422 (1999) · Zbl 0958.68020
[3] Ahmed, I.; Dhodhi, M. K.: Task assignment using a problem-space genetic algorithm, Concurrency, pract. Exp. 7, 411-428 (1995)
[4] Akl, S. G.: Parallel computation: models and methods, (1997)
[5] S.M. Alaoui, O. Frieder, T.A. EL-Ghazawi, Parallel genetic algorithm for task mapping on parallel machine, in: Proc. of the 13th International Parallel Processing Symposium & 10th Symp. Parallel and Distributed Processing IPPS/SPDP Workshops, April 1999, San Juan, Puerto Rico, 1999
[6] S. Ali, S.M. Sait, M.S.T. Benten, GSA: Scheduling and allocation using genetic algorithm, in: Proceedings of the Conference on EURO-DAC with EURO WDHL 1994, Grenoble, 1994, pp. 84–89
[7] Back, T.; Hammel, U.; Schwefel, H. -P.: Evolutionary computation: comments on the history and current state, IEEE trans. Evol. comput. 1, 3-17 (1997)
[8] Blickle, T.; Thiele, L.: A mathematical analysis of tournament selection, (1995)
[9] Bouvry, P.; Chassin, J.; Trystram, D.: Efficient solutions for mapping parallel programs, (1995)
[10] Corman, T. H.; Leiserson, C. E.; Rivests, R. L.: Introduction to algorithms, (1990)
[11] El-Rewini, H.; Lewis, T. G.; Ali, H. H.: Task scheduling in parallel and distributed systems, (1994) · Zbl 1049.68528
[12] A.T. Haghighat, M. Nikravan, A hybrid genetic algorithm for process scheduling in distributed operating systems considering load balancing, The IASTED Conference on Parallel and Distributed Computing and Networks PDCN, Innsbruck, Austria, 2005
[13] Holland, J. H.: Adaptation in natural and artificial systems, (1975) · Zbl 0317.68006
[14] Hou, E. H.; Ansari, N.; Ren, H.: A genetic algorithm for multiprocessor scheduling, IEEE trans. Parallel distrib. Syst. 5, 113-120 (1994)
[15] S. Kumar, U. Maulik, S. Bandyopadhyay, S.K. Das, Efficient task mapping on distributed heterogeneous systems for mesh applications, in: Proceedings of the International Workshop on Distributed Computing, Kolkata, India, 2001
[16] Yu. Kwok, High performance algorithms for compile-time scheduling of parallel processors, Ph.D. Thesis, Hong Kong University, 1997
[17] Kwok, Y.; Ahmad, I.: Dynamic critical path scheduling: an effective technique for allocating task graphs to multi-processors, IEEE trans. Parallel distrib. Syst. 7, 506-521 (1996)
[18] Kwok, Y.; Ahmad, I.: Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM comput. Surv. 31, 406-471 (1999)
[19] D. Levine, A parallel genetic algorithm for the set partitioning problem, Ph.D. Thesis in Computer Science, Department of Mathematics and Computer science, Illinois Institute of Technology, Chicago, USA, 1994
[20] Omara, F. A.; Allam, A.: An efficient tasks scheduling algorithm for distributed memory machines with communication delays, J. inf. Technol. 4, 326-334 (2005)
[21] Palis, M. A.; Liou, J. C.; Rajasekaran, S.; Shende, S.; Wei, S. S. L: Online scheduling of dynamic trees, Parallel process. Lett. 5, 635-646 (1995)
[22] Radulescu, A.; Van Gemund, A. J. C: Low cost task scheduling for distributed memory machines, IEEE trans. Parallel distrib. Syst. 13, 648-658 (2002)
[23] Sih, G. C.; Lee, E. A.: A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures, IEEE trans. Parallel distrib. Syst. 4, 75-87 (1993)
[24] Srinivas, M.; Patnaik, L. M.: Adaptive probabilities of crossover and mutation in genetic algorithm, IEEE trans. Syst. man cybern. 24, No. 4, 656-667 (1994)
[25] E.G. Talbi, T. Muntean, A new approach for the mapping problem: A parallel genetic algorithm, www.citessr.ist.psu.edu/, 1993
[26] Tsuchiya, T.; Osada, T.; Kikuno, T.: Genetic-based multiprocessor scheduling using task duplication, Microprocess. microsyst. 22, 197-207 (1998)
[27] Wilkinson, B.; Allen, M.: Parallel programming: techniques and applications using networked workstations and parallel computers, (2005)
[28] Wu, M.; Gajski, D. D.: Hypertool: A programming aid for message-passing systems, IEEE trans. Parallel distrib. Syst. 1, 381-422 (1990)
[29] Wu, A. S.; Yu, H.; Jin, S.; Lin, K. -C.; Schiavone, G.: An incremental genetic algorithm approach to multiprocessor scheduling, IEEE trans. Parallel distrib. Syst. 15, 824-834 (2004)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.