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

Authors

  • Bruno Well Dantas Morais Universidade Federal de Uberlândia http://orcid.org/0000-0001-6709-7642
  • Gina Maira Barbosa de Oliveira Universidade Federal de Uberlândia
  • Tiago Ismailer de Carvalho Universidade Federal de Uberlândia

DOI:

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

Keywords:

multipopulation genetic algorithm, multiprocessor task scheduling

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.

Downloads

Download data is not yet available.

Author Biographies

Bruno Well Dantas Morais, Universidade Federal de Uberlândia

Graduado em Ciência da Computação pela Universidade Federal de Uberlândia (2017). Estudante de mestrado em Ciência da Computação na Universidade Federal de Uberlândia.

Gina Maira Barbosa de Oliveira, Universidade Federal de Uberlândia

Bolsista de produtividade do CNPq de 2001 a 2017 (PQ-2). Possui graduação em Engenharia Elétrica pela Universidade Federal de Uberlândia (1990), mestrado em Engenharia Eletrônica e Computação pelo Instituto Tecnológico de Aeronáutica (1992) e doutorado em Engenharia Eletrônica e Computação pelo Instituto Tecnológico de Aeronáutica (1999). Pós-doutorado de 07/2013 a 07/2014 na Heriot-Watt University (Edinburgh-Scotland) na área de robótica bio-inspirada. Atualmente é professora associada da Universidade Federal de Uberlândia. Tem experiência na área de Ciência da Computação, atuando principalmente nos seguintes temas: algoritmos genéticos, autômatos celulares, computação evolutiva, computação bio-inspirada, robótica bio-inspirada e inteligência artificial. 

Tiago Ismailer de Carvalho, Universidade Federal de Uberlândia

Possui graduação em Ciência da Computação pela Universidade Federal de Uberlândia (2011), mestrado em Inteligência Artificial pela Faculdade de Computação da Universidade Federal de Uberlândia (2014). Atuou como professor substituto no Instituto Federal de Uberlândia onde ministrou as disciplinas de Lógica, Programação Básica, Serviço de Banco de Dados e Metodologia Científica. Tem experiência na área de Ciência da Computação, com ênfase em Inteligência Computacional, atuando principalmente nos seguintes temas: autômatos celulares e algoritmos genéticos.

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.

Downloads

Published

2019-04-14

How to Cite

Dantas Morais, B. W., Barbosa de Oliveira, G. M., & de Carvalho, T. I. (2019). Evolutionary Models applied to Multiprocessor TaskScheduling: Serial and Multipopulation Genetic Algorithm. Revista De Informática Teórica E Aplicada, 26(1), 11–25. https://doi.org/10.22456/2175-2745.82412

Issue

Section

Regular Papers