Evolutionary Models applied to Multiprocessor TaskScheduling: Serial and Multipopulation Genetic Algorithm

Bruno Well Dantas Morais, Gina Maira Barbosa de Oliveira, Tiago Ismailer de Carvalho

Abstract


This work presents the development of a multipopulation genetic algorithm for the task schedulingproblem with communication costs, aiming to compare its performance with the serial genetic algorithm. For thispurpose, a set of instances was developed and different approaches for genetic operations were compared.Experiments were conducted varying the number of populations and the number of processors available forscheduling. Solution quality and execution time were analyzed, and results show that the AGMP with adjustedparameters generally produces better solutions while requiring less execution time.

Keywords


multipopulation genetic algorithm; multiprocessor task scheduling

Full Text:

PDF

References


HOU, E. S. H.; ANSARI, N.; REN, H. A genetic algorithm for multiprocessor scheduling. IEEE Trans. Parallel Distrib. Syst., v. 5, n. 2, p. 113–120, 2 1994.

GOLDBERG, D. E. Genetic Algorithms in Search, Optimization and Machine Learning. 1st. ed. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1989. v.1.

ALBA, E.; TROYA, J. M. A survey of parallel distributed genetic algorithms. Complex,, v. 4, n. 4, p. 31–52, 3 1999.

KWOK, Y.-K.; AHMAD, I. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Comput, Surv,, v. 31, n. 4, p. 406–471, 12 1999.

CANTu ́-PAZ, E. A survey of parallel genetic algorithms. Calc. paralleles reseaux syst. repartis, v. 10, n. 2, p. 141–171, 1998.

CANTU ́-PAZ,E.etal.Aremultiplerunsofgenetic algorithms better than one? In: Genetic and Evolutionary Computation — GECCO 2003. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. p. 801–812.

CORREA, R. C.; FERREIRA, A.; REBREYEND, P. Scheduling multiprocessor tasks with genetic algorithms. IEEE Trans. Parallel Distrib. Syst., v. 10, n. 8, p. 825–837, 8 1999.

KAUR, K. et al. Heuristics based genetic algorithm for scheduling static tasks in homogeneous parallel system. Int. J. Comput. Sci. Secur. (IJCSS), v. 4, n. 2, p. 183–198, 1999.

WANG, L. et al. Task matching and scheduling in heterogeneous computing environments using a genetic-algorithm-based approach. J. Parallel Distrib. Comput., v. 47, n. 1, p. 8 – 22, 1997.

OMARA, F. A.; ARAFA, M. M. Genetic algorithms for task scheduling problem. J. Parallel Distrib. Comput., v. 70, n. 1, p. 13 – 22, 2010.

CHITRA, P.; RAJARAM, R.; VENKATESH, P. Application and comparison of hybrid evolutionary multiobjective optimization algorithms for solving task scheduling problem on heterogeneous systems. Appl. Soft Comput., v. 11, n. 2, p. 2725 – 2734, 2011.

MORADY, R.; DAL, D. A multi-population based parallel genetic algorithm for multiprocessor task scheduling with communication costs. In: . Messina, Italy: IEEE, 2016. (ISCC, ’16), p. 766–772.

KWOK, Y.-K.; AHMAD, I. Efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm. J. Parallel Distrib, Comput,, v. 47, n. 1, p. 58–77, 11 1997.

HWANG, R.; GEN, M.; KATAYAMA, H. A comparison of multiprocessor task scheduling algorithms with communication costs. Comput. Oper. Res., v. 35, n. 3, p. 976 – 993, 2008.

XU, Y. et al. A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Inf. Sci., v. 270, n. 1, p. 255 – 287, 2014.

QI, J. G.; BURNS, G. R.; HARRISON, D. K. The application of parallel multipopulation genetic algorithms to dynamic job-shop scheduling. Int. J. Adv. Manuf. Technol., v. 16, n. 8, p. 609–615, 7 2000.

SRINIVASA, K. G.; VENUGOPAL, K. R.; PATNAIK, L. M. A self-adaptive migration model genetic algorithm for data mining applications. Inf, Sci,, v. 177, n. 20, p. 4295–4313, 10 2007.

GEHRING, H.; BORTFELDT, A. A parallel genetic algorithm for solving the container loading problem. Int. Trans. Oper. Res., v. 9, n. 5-6, p. 497 – 511, 7 2002.

MU ̈HLENBEIN,H.;SCHOMISCH,M.;BORN,J.The parallel genetic algorithm as function optimizer. Parallel Comput,, v. 17, n. 6-7, p. 619–632, 9 1991.

YAO, J.; KHARMA, N.; GROGONO, P. Bi-objective multipopulation genetic algorithm for multimodal function optimization. IEEE Trans. Evol. Comput., v. 14, n. 1, p. 80–102, 2 2010.

HAN, K.-H. et al. Parallel quantum-inspired genetic algorithm for combinatorial optimization problem. In: . Seoul, South Korea: IEEE, 2001. (CEC2001, v. 2), p. 1422–1429 vol. 2.

OLTEANU, A.; MARIN, A. Generation and evaluation of scheduling dags: How to provide similar evaluation conditions. Comput. Sci. Master Res., v. 1, n. 1, p. 57, 2011.

JIANG, Y.; SHAO, Z.; GUO, Y. A dag scheduling scheme on heterogeneous computing systems using tuple-based chemical reaction optimization. Sci. World J., v. 2014, n. 1, p. 404375, 6 2014.

COSNARD, M. et al. Parallel gaussian elimination on an mimd computer. Parallel Comput., v. 6, n. 3, p. 275 – 296, 1988.

WU, M. Y.; GAJSKI, D. D. Hypertool: a programming aid for message-passing systems. IEEE Trans. Parallel Distrib. Syst., v. 1, n. 3, p. 330–343, 7 1990.

XU, Y.; LI, K.; HU, J. A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Inf. Sci., v. 270, n. 1, p. 255–257, 6 2014.

CARNEIRO, M. G. Abordagens baseadas em autoˆmatos celulares s ́ıncronos para o escalonamento esta ́tico de tarefas em multiprocessadores. Tese (Doutorado), Uberlaˆndia, Brasil, 2012.

GLOVER, F.; LAGUNA, M. Tabu search. In: Handbook of Combinatorial Optimization. 1. ed. Boston, MA: Springer US, 1999. Volume 1–3, p. 2093–2229.

FEO, T. A.; RESENDE, M. G. C. Greedy randomized adaptive search procedures. J. Glob. Optim., v. 6, n. 2, p. 109–133, 3 1995.

MLADENOVIC, N.; HANSEN, P. Variable neighborhood search. Comput. Oper. Res., v. 24, n. 11, p. 1097 – 1100, 1997.




DOI: https://doi.org/10.22456/2175-2745.82412

Copyright (c) 2019 Bruno Well Dantas Morais, Gina Maira Barbosa de Oliveira, Tiago Ismailer de Carvalho

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Indexing databases:
        

Acknowledgments: