Abstract
Until now, several methods have been presented to optimally solve the multiprocessor task scheduling problem that is an NP-hard one. In this paper, a genetic-based algorithm has been presented to solve this problem with better results in comparison with related methods. The proposed method is a bipartite algorithm in a way that each part is based on different genetic schemes, such as genome presentation and genetic operators. In the first part, it uses a genetic method to find an adequate sequence of tasks and in the second one, it finds the best match processors. To evaluate the proposed method, we applied it on several benchmarks and the results were compared with well known algorithms. The experimental results were satisfactory and in most cases the presented method had a better makespan with at least 10% less iterations compared to related works.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Ahmad I., Dhodhi M.K.: Multiprocessor scheduling in a genetic paradigm. Parallel Comput. 22, 395–406 (1996). doi:10.1016/0167-8191(95)00068-2
Ahmad I., Kwok Y.: On exploiting task duplication in parallel program scheduling. IEEE Trans. Parallel Distrib. Syst. 9(9), 872–892 (1998). doi:10.1109/71.722221
Bonyadi, M.R., Rahimi Azghadi, M., Hashemi, S., Ebrahimi Moghadam, M.: A hybrid multiprocessor task scheduling method based on immune genetic algorithm. In: Qshine 2008 Workshop on Artificial Intelligence in Grid Computing (2008). doi:10.4108/ICST.QSHINE2008.4263
Braun T.D., Siegel H.J., Beck N.: A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. J. Parallel Distrib. Comput. 61, 810–837 (2001). doi:10.1006/jpdc.2000.1714
Chen, H.,Cheng, A.K.: Applying ant colony optimization to the partitioned scheduling problem for heterogeneous multiprocessors. Special Issue: IEEE RTAS 2005 Work-in-Progress, vol. 2, issue 2, pp. 11–14 (2005)
Corbalan J., Martorell X., Labarta J.: Performance-driven processor allocation. IEEE Trans. Parallel Distrib. Syst. 16(7), 599–611 (2005). doi:10.1109/TPDS.2005.85
Dhodhi, M.K., Ahmad, I.: A multiprocessor scheduling scheme using problem-space genetic algorithms. In: Proceedings of IEEE International Conference on Evolutionary Computution, pp. 214–219 (1995)
Eiben, A.E., Smith, J.E.: Introduction to Evolutionary Computation, 1st edn. Springer, Natural Computing Series (2003)
Ercan, M.F.: A hybrid particle swarm optimization approach for scheduling flow-shops with multiprocessor tasks. In: International Conference on Information Science and Security, pp. 13–16 (2008)
Hamidzadeh B., Kit L.Y., Lilja D.J.: Dynamic task scheduling using online optimization. IEEE Trans. Parallel Distrib. Syst. 11(11), 1151–1162 (2000). doi:10.1109/71.888636
Holland J.H.: Adaption in Natural and Artificial Systems. University of Michigan Press, Ann Arbor (1975)
Hou E.S.H., Ansari N., Hong R.: A genetic algorithm for multiprocessor scheduling. IEEE Trans. Parallel Distrib. Syst. 5(2), 113–120 (1994). doi:10.1109/71.265940
Hwang J., Chow Y., Anger A., Lee C.: Scheduling precedence graphs in systems with inter-processor communication times. SIAM J. Comput. 8(2), 244–257 (1989). doi:10.1137/0218016
Hwang R., Gen M., Katayama H.: A comparison of multiprocessor task scheduling algorithms with communication costs. Comput. Oper. Res. 35, 976–993 (2008). doi:10.1016/j.cor.2006.05.013
Hwang, R.K., Gen, M.: Multiprocessor scheduling using genetic algorithm with priority-based coding. In: Proceedings of IEEJ Conference on Electronics, Information and Systems (2004)
Jelodar, M.S., Fakhraie, S.N., Montazeri, F., Fakhraie, S.M., Ahmadabadi, M.N.: A representation for genetic-algorithm-based multiprocessor task scheduling. In: IEEE Congress on Evolutionary Computation, pp. 16–21 (2006)
Kafil M., Ahmad I.: Optimal task assignment in heterogeneous distributed computing systems. IEEE Concurr. 6, 42–51 (1998). doi:10.1109/4434.708255
Kasahara H., Narita S.: Practical multiprocessing scheduling algorithms for efficient parallel processing. IEEE Trans. Comput. 33, 1023–1029 (1984). doi:10.1109/TC.1984.1676376
Kermia, O., Sorel, Y.: A rapid heuristic for scheduling non-preemptive dependent periodic tasks onto multiprocessor. ISCA PDCS, pp. 1–6 (2007)
Kruatrachue, B., Lewis, T.G.: Duplication scheduling heuristic, a new precedence task scheduler for parallel systems. Technical Report, Oregon State University (1987)
Lee, Y.H., Chen, C.: A Modified genetic algorithm for task scheduling in multi processor systems. In: The Ninth Workshop on Compiler Techniques for High Performance Computing (2003)
Man, L., Yang, L.T.: Hybrid genetic algorithms for scheduling partially ordered tasks in a multi-processor environment. In: 6th International Conference on Real-Time Computing Systems and Applications (RTCSA ‘99), pp. 382–387 (1999)
Mayez A.: Al-Mouhamed, lower bound on the number of processors and time for scheduling precedence graphs with communication costs. IEEE Trans. Softw. Eng. 16(12), 1390–1401 (1990). doi:10.1109/32.62447
Meijer, M.: Scheduling parallel processes using genetic algorithms. Master thesis in the field of artificial intelligence, University of Amsterdam, February 2004
Montazeri, F., Salmani-Jelodar, M., Fakhraie, S.N., Fakhraie, S.M.: Evolutionary multiprocessor task scheduling. In: Proceedings of the International Symposium on Parallel Computing in Electrical Engineering (PARELEC’06) (2006)
Musnjak, M., Golub, M.: Using a set of elite individuals in a genetic algorithm. In: 26th International Conference on Information Technology Interfaces, pp. 531–536 (2004)
Nissanke N., Leulseged A., Chillara S.: Probabilistic performance analysis in multiprocessor scheduling. J. Comput. Contr. Eng. 13(4), 171–179 (2002). doi:10.1049/cce:20020403
Nossal, R.: An evolutionary approach to multiprocessor scheduling of dependent tasks. Special Issue: Bio-inspired Solutions to Parallel Processing Problems, pp. 383–392 (1998)
Oguz, C., Ercan, M.F.: A genetic algorithm for multi-layer multiprocessor task scheduling. In: TENCON 2004, IEEE Region 10 Conference, vol. 2, pp. 168–170 (2004)
Page, A.J., Naughton, T.J.: Dynamic task scheduling using genetic algorithms for heterogeneous distributed computing. In: Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS) (2005)
Qu, Y., Soininen, J.P., Nurmi, J.: A genetic algorithm for scheduling tasks onto dynamically reconfigurable hardware. In: IEEE International Symposium on Circuits and Systems (ISCAS 2007), pp. 161–164 (2007)
Rechenberg, I.: Cybernetic solution path of an experimental problem. Royal Aircraft Establishment, Library Translation No. 1122, August 1965
Rebreyend P., Sandnes F.E., Megson M.: Static Multiprocessor Task Graph Scheduling in the Genetic Paradigm: A Comparison of Genotype Representations, Parallel Emergent and Distributed Architecture Laboratory (PEDAL). The University of Reading, UK (1998)
Ricardo C.: Corrga, Afonso Ferreira and Pascal Rebreyend, scheduling multiprocessor tasks with genetic algorithm. IEEE Trans. Parallel Distrib. Syst. 10(8), 825–837 (1999). doi:10.1109/71.790600
Rinehart, M., Kianzad, V., Bhattacharyya, S.S.: A modular genetic algorithm for scheduling task graphs. Technical Report UMIACS-TR-2003-66. Institute for Advanced Computer Studies, University of Maryland at College Park (June) (2003)
Ritchie, G.: Static multi-processor scheduling with ant colony optimization & local search. Master of science thesis, artificial intelligence, University of Edinburgh (2003)
Salleh, S.,Zomaya, A.Y.: Multiprocessor scheduling using mean-field annealing. Special Issue: Bio-inspired Solutions to Parallel Processing Problems, vol. 14, issue 5–6, pp. 393–408
Sivanandam S.N., Visalakshi P., Bhuvaneswari A.: Multiprocessor scheduling using hybrid particle swarm optimization with dynamically varying inertia. Int. J. Comput. Sci. Appl. 4(3), 95–106 (2007)
Sutar, S., Sawant, J., Jadhav, J.: Task scheduling for multiprocessor systems using memetic algorithms. In: 4th International Working Conference Performance Modeling and Evaluation of Heterogeneous Networks (HET-NETs ‘06) (2006)
Standard Task Graph Set is available online at: http://www.kasahara.elec.waseda.ac.jp/schedule
Thanalapati T., Dandamudi S.: An efficient adaptive scheduling scheme for distributed memory multicomputer. IEEE Trans. Parallel Distrib. Syst. 12(7), 758–768 (2001). doi:10.1109/71.940749
Tsuchiya T., Osada T., Kikuno T.: Genetics-based multiprocessor scheduling using task duplication. J. Microprocess. Microsyst. 22(3–4), 197–207 (1998)
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(9), 824–834 (2004). doi:10.1109/TPDS.2004.38
Wu M.Y., Gajski D.D.: Hypertool A programming aid for message-passing systems. IEEE Trans. Parallel Distrib. Syst. 1(3), 330–343 (1990). doi:10.1109/71.80160
Wang, P.C., Korfhage, W.: Process scheduling using genetic algorithms. In: 7th IEEE Symposium Parallel and Distributed Processing, Texas, San Antonio, pp. 638–641, October 1995
Yang T., Gerasoulis A.: DSC: scheduling parallel tasks on an unbounded number of processors. IEEE Trans. Parallel Distrib. Syst. 5(9), 951–967 (1994)
Yo-Kwong K.: Ishfaq Ahmad, dynamic critical path scheduling: an effective technique for allocating task graphs to multiprocessors. IEEE Trans. Parallel Distrib. Syst. 7(5), 506–521 (1996). doi:10.1109/71.503776
Yue, K., Lilja, D.J.: Designing multiprocessor scheduling algorithms using a distributed genetic algorithm system. Technical Report No. HPPC-96-03, University of Minnesota, High performance Parallel Computing Research Group, May 1996
Zhong, Y.W., Yang, J.G.: A genetic algorithm for tasks scheduling in parallel multiprocessor systems. In: Proceedings of the Second International Conference on Machine Learning and Cybernetics, pp. 1785–1790 (2003)
Zomaya A.Y., Teh Y.H.: Observations on using genetic algorithms for dynamic load-balancing. IEEE Trans. Parallel Distrib. Syst. 12(9), 899–911 (2001). doi:10.1109/71.954620
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bonyadi, M.R., Ebrahimi Moghaddam, M. A Bipartite Genetic Algorithm for Multi-processor Task Scheduling. Int J Parallel Prog 37, 462–487 (2009). https://doi.org/10.1007/s10766-009-0107-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10766-009-0107-8