Genetic algorithms and multiprocessor task scheduling: A systematic literature review
Resumo
This paper reports a systematic review of the literature about genetic algorithms applied to the multiprocessor task scheduling problem. After defining a protocol with the main rules of this review, the research was performed considering journal papers published between 1990 and 2018. At the end of this process, 37 works were recovered and analyzed. By performing a meta-analysis, a variety of information was extracted and summarized, including impact factor, Eigenfactor score, scenarios considered, optimization metrics, volume of citations, and others.
Palavras-chave:
Genetic algorithms, Multiprocessor task scheduling, DAG, Systematic literature review
Referências
Afrati, F., Papadimitriou, C. H., and Papageorgiou, G. (1988). Scheduling DAGs to minimize time and communication. In Reif, J. H., editor, VLSI Algorithms and Architectures, volume 319 of Lecture Notes in Computer Science, pages 134–138.
Aguilar, J. and Gelenbe, E. (1997). Task assignment and transaction clustering heuristics for distributed systems. Information Sciences, 97(1-2):199–219.
Ahmad, S. G., Liew, C. S., Munir, E. U., Ang, T. F., and Khan, S. U. (2016). A hybrid genetic algorithm for optimization of scheduling workflow applications in heterogeneous computing systems. Journal of Parallel and Distributed Computing, 87:80–90.
Akbari, M. (2018). An efficient genetic algorithm for task scheduling on heterogeneous computing systems based on TRIZ. Journal of Advances in Computer Research, 9(3):103–132.
Akbari, M., Rashidi, H., and Alizadeh, S. H. (2017). An enhanced genetic algorithm with new operators for task scheduling in heterogeneous computing systems. Engineering Applications of Artificial Intelligence, 61:35–46.
Amalarethinam, D. I. G. and Selvi, F. K. M. (2012). Grid scheduling strategy using GA (GSSGA). International Journal of Computer Technology and Applications, 3(4):1800–1806.
Amirjanov, A. and Sobolev, K. (2017). Scheduling of directed acyclic graphs by a genetic algorithm with a repairing mechanism. Concurrency and Computation: Practice and Experience, 29(5):1–10.
Awadall, M., Ahmad, A., and Al-Busaidi, S. (2013). Min-min GA based task scheduling in multiprocessor systems. International Journal of Engineering and Advanced Technology, 3(2):22–31.
Benten, M. S. T. and Sait, S. M. (1994). Genetic scheduling of task graphs. International Journal of electronics, 77(4):401–415.
Bonyadi, M. R. and Moghaddam, M. E. (2009). A bipartite genetic algorithm for multiprocessor task scheduling. International Journal of Parallel Programming, 37(5):462– 487.
Chitra, P., Venkatesh, P., and Rajaram, R. (2011). Comparison of evolutionary computation algorithms for solving bi-objective task scheduling problem on heterogeneous distributed computing systems. Sadhana, 36(2):167–180.
Corrêa, R. C., Ferreira, A., and Rebreyend, P. (1999). Scheduling multiprocessor tasks with genetic algorithms. IEEE Transactions on Parallel and Distributed systems, 10(8):825–837.
Daoud, M. I. and Kharma, N. (2011). A hybrid heuristic-genetic algorithm for task scheduling in heterogeneous processor networks. Journal of Parallel and Distributed Computing, 71(11):1518–1531.
Demiroz, B. and Topcuoglu, H. R. (2006). Static task scheduling with a unified objective on time and resource domains. The Computer Journal, 49(6):731–743.
Dhingra, S., Gupta, S. B., and Biswas, R. (2014). Genetic algorithm parameters optimization for bi-criteria multiprocessor task scheduling using design of experiments. International Journal of Computer, Control, Quantum and Information Engineering, 8(4):661–667.
Guzek, M., Pecero, J. E., Dorronsoro, B., and Bouvry, P. (2014). Multi-objective evolutionary algorithms for energy-aware scheduling on distributed computing systems. Applied Soft Computing, 24:432–446.
Hassan, M.-A., Kacem, I., Martin, S., and Osman, I. M. (2015). Genetic algorithms for job scheduling in cloud computing. Studies in Informatics and Control, 24(4):387– 400.
Hou, E. S. H., Ansari, N., and Ren, H. (1994). A genetic algorithm for multiprocessor scheduling. IEEE Transactions on parallel and distributed systems, 5(2):113–120.
Hwang, R., Gen, M., and Katayama, H. (2008). A comparison of multiprocessor task scheduling algorithms with communication costs. Computers & Operations Research, 35(3):976–993.
Kaur, K., Chhabra, A., and Singh, G. (2010a). Heuristics based genetic algorithm for scheduling static tasks in homogeneous parallel system. International Journal of Computer Science and Security, 4(2):183–198.
Kaur, K., Chhabra, A., and Singh, G. (2010b). Modified genetic algorithm for task scheduling in homogeneous parallel system using heuristics. International Journal of Soft Computing, 5(2):42–51.
Kwok, Y.-K. and Ahmad, I. (1997). Efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm. Journal of Parallel and Distributed Computing, 47(1):58–77.
Levy, Y. and Ellis, T. J. (2006). A system approach to conductan effective literature review in support of information systems research. Informing Science Journal, 9(1):181–212.
Mohamed, M. R. and Awadalla, M. H. (2011). Hybrid algorithm for multiprocessor task scheduling. International Journal of Computer Science Issues, 8(3):79–89.
Omara, F. and Arafa, M. (2010). Genetic algorithms for task scheduling problem. Journal of Parallel and Distributed Computing, 70(1):13–22.
Pillai, A. S., Singh, K., Saravanan, V., Anpalagan, A., Woungang, I., and Barolli, L. (2018). A genetic algorithm-based method for optimizing the energy consumption and performance of multiprocessor systems. Soft Computing, 22(10):3271–3285.
Puntel, F. E., Charão, A., Franciscatto, M. H., Lima, J. C. D., and da Rocha, C. C. (2018). A systematic review of scheduling algorithms and resource management in contextaware applications: A meta-analytic approach. In ICEIS, pages 664–670.
Ramachandra, G. and Elmaghraby, S. E. (2006). Sequencing precedence-related jobs on two machines to minimize the weighted completion time. International Journal of Production Economics, 100(1):44–58.
Sathappan, O. L., Chitra, P., Venkatesh, P., and Prabhu, M. (2011). Modified genetic algorithm for multiobjective task scheduling on heterogeneous computing system. International Journal of Information Technology, Communications and Convergence, 1(2):146–158.
Sheikh, H. F., Ahmad, I., and Arshad, S. A. (2017). Performance, energy, and temperature enabled task scheduling using evolutionary techniques. Sustainable Computing: Informatics and Systems, 22:272–286.
Sheikh, H. F., Ahmad, I., and Fan, D. (2016). An evolutionary technique for performance-energy-temperature optimized scheduling of parallel tasks on multi-core processors. IEEE Transactions on Parallel and Distributed Systems, 27(3):668–681.
Singh, J. and Singh, G. (2012). Improved task scheduling on parallel system using genetic algorithm. International Journal of Computer Applications, 39(17):17–22.
Singh, R. (2012). Task scheduling with genetic approach and task duplication technique. International Journal of Computer Applications & Information Technology, 1(1):7–12.
Tsuchiya, T., Osada, T., and Kikuno, T. (1998). Genetics-based multiprocessor scheduling using task duplication. Microprocessors and Microsystems, 22(3-4):197–207.
Wang, L., Siegel, H. J., Roychowdhury, V. P., and Maciejewski, A. A. (1997). Task matching and scheduling in heterogeneous computing environments using a geneticalgorithm-based approach. Journal of parallel and distributed computing, 47(1):8–22.
Wang, X., Yeo, C. S., Buyya, R., and Su, J. (2011). Optimizing the makespan and reliability for workflow applications with reputation and a look-ahead genetic algorithm. Future Generation Computer Systems, 27(8):1124–1134.
Wu, A. S., Yu, H., Jin, S., Lin, K.-C., and Schiavone, G. (2004). An incremental genetic algorithm approach to multiprocessor scheduling. IEEE Transactions on parallel and distributed systems, 15(9):824–834.
Xu, Y., Li, K., Hu, J., and Li, K. (2014). A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Information Sciences, 270:255–287.
Yao, W., You, J., and Li, B. (2004). Main sequences genetic scheduling for multiprocessor systems using task duplication. Microprocessors and Microsystems, 28(2):85–94.
Zomaya, A. Y., Ward, C., and Macey, B. (1999). Genetic scheduling for parallel processor systems: comparative studies and performance issues. IEEE Transactions on Parallel and Distributed Systems, 10(8):795–812.
Aguilar, J. and Gelenbe, E. (1997). Task assignment and transaction clustering heuristics for distributed systems. Information Sciences, 97(1-2):199–219.
Ahmad, S. G., Liew, C. S., Munir, E. U., Ang, T. F., and Khan, S. U. (2016). A hybrid genetic algorithm for optimization of scheduling workflow applications in heterogeneous computing systems. Journal of Parallel and Distributed Computing, 87:80–90.
Akbari, M. (2018). An efficient genetic algorithm for task scheduling on heterogeneous computing systems based on TRIZ. Journal of Advances in Computer Research, 9(3):103–132.
Akbari, M., Rashidi, H., and Alizadeh, S. H. (2017). An enhanced genetic algorithm with new operators for task scheduling in heterogeneous computing systems. Engineering Applications of Artificial Intelligence, 61:35–46.
Amalarethinam, D. I. G. and Selvi, F. K. M. (2012). Grid scheduling strategy using GA (GSSGA). International Journal of Computer Technology and Applications, 3(4):1800–1806.
Amirjanov, A. and Sobolev, K. (2017). Scheduling of directed acyclic graphs by a genetic algorithm with a repairing mechanism. Concurrency and Computation: Practice and Experience, 29(5):1–10.
Awadall, M., Ahmad, A., and Al-Busaidi, S. (2013). Min-min GA based task scheduling in multiprocessor systems. International Journal of Engineering and Advanced Technology, 3(2):22–31.
Benten, M. S. T. and Sait, S. M. (1994). Genetic scheduling of task graphs. International Journal of electronics, 77(4):401–415.
Bonyadi, M. R. and Moghaddam, M. E. (2009). A bipartite genetic algorithm for multiprocessor task scheduling. International Journal of Parallel Programming, 37(5):462– 487.
Chitra, P., Venkatesh, P., and Rajaram, R. (2011). Comparison of evolutionary computation algorithms for solving bi-objective task scheduling problem on heterogeneous distributed computing systems. Sadhana, 36(2):167–180.
Corrêa, R. C., Ferreira, A., and Rebreyend, P. (1999). Scheduling multiprocessor tasks with genetic algorithms. IEEE Transactions on Parallel and Distributed systems, 10(8):825–837.
Daoud, M. I. and Kharma, N. (2011). A hybrid heuristic-genetic algorithm for task scheduling in heterogeneous processor networks. Journal of Parallel and Distributed Computing, 71(11):1518–1531.
Demiroz, B. and Topcuoglu, H. R. (2006). Static task scheduling with a unified objective on time and resource domains. The Computer Journal, 49(6):731–743.
Dhingra, S., Gupta, S. B., and Biswas, R. (2014). Genetic algorithm parameters optimization for bi-criteria multiprocessor task scheduling using design of experiments. International Journal of Computer, Control, Quantum and Information Engineering, 8(4):661–667.
Guzek, M., Pecero, J. E., Dorronsoro, B., and Bouvry, P. (2014). Multi-objective evolutionary algorithms for energy-aware scheduling on distributed computing systems. Applied Soft Computing, 24:432–446.
Hassan, M.-A., Kacem, I., Martin, S., and Osman, I. M. (2015). Genetic algorithms for job scheduling in cloud computing. Studies in Informatics and Control, 24(4):387– 400.
Hou, E. S. H., Ansari, N., and Ren, H. (1994). A genetic algorithm for multiprocessor scheduling. IEEE Transactions on parallel and distributed systems, 5(2):113–120.
Hwang, R., Gen, M., and Katayama, H. (2008). A comparison of multiprocessor task scheduling algorithms with communication costs. Computers & Operations Research, 35(3):976–993.
Kaur, K., Chhabra, A., and Singh, G. (2010a). Heuristics based genetic algorithm for scheduling static tasks in homogeneous parallel system. International Journal of Computer Science and Security, 4(2):183–198.
Kaur, K., Chhabra, A., and Singh, G. (2010b). Modified genetic algorithm for task scheduling in homogeneous parallel system using heuristics. International Journal of Soft Computing, 5(2):42–51.
Kwok, Y.-K. and Ahmad, I. (1997). Efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm. Journal of Parallel and Distributed Computing, 47(1):58–77.
Levy, Y. and Ellis, T. J. (2006). A system approach to conductan effective literature review in support of information systems research. Informing Science Journal, 9(1):181–212.
Mohamed, M. R. and Awadalla, M. H. (2011). Hybrid algorithm for multiprocessor task scheduling. International Journal of Computer Science Issues, 8(3):79–89.
Omara, F. and Arafa, M. (2010). Genetic algorithms for task scheduling problem. Journal of Parallel and Distributed Computing, 70(1):13–22.
Pillai, A. S., Singh, K., Saravanan, V., Anpalagan, A., Woungang, I., and Barolli, L. (2018). A genetic algorithm-based method for optimizing the energy consumption and performance of multiprocessor systems. Soft Computing, 22(10):3271–3285.
Puntel, F. E., Charão, A., Franciscatto, M. H., Lima, J. C. D., and da Rocha, C. C. (2018). A systematic review of scheduling algorithms and resource management in contextaware applications: A meta-analytic approach. In ICEIS, pages 664–670.
Ramachandra, G. and Elmaghraby, S. E. (2006). Sequencing precedence-related jobs on two machines to minimize the weighted completion time. International Journal of Production Economics, 100(1):44–58.
Sathappan, O. L., Chitra, P., Venkatesh, P., and Prabhu, M. (2011). Modified genetic algorithm for multiobjective task scheduling on heterogeneous computing system. International Journal of Information Technology, Communications and Convergence, 1(2):146–158.
Sheikh, H. F., Ahmad, I., and Arshad, S. A. (2017). Performance, energy, and temperature enabled task scheduling using evolutionary techniques. Sustainable Computing: Informatics and Systems, 22:272–286.
Sheikh, H. F., Ahmad, I., and Fan, D. (2016). An evolutionary technique for performance-energy-temperature optimized scheduling of parallel tasks on multi-core processors. IEEE Transactions on Parallel and Distributed Systems, 27(3):668–681.
Singh, J. and Singh, G. (2012). Improved task scheduling on parallel system using genetic algorithm. International Journal of Computer Applications, 39(17):17–22.
Singh, R. (2012). Task scheduling with genetic approach and task duplication technique. International Journal of Computer Applications & Information Technology, 1(1):7–12.
Tsuchiya, T., Osada, T., and Kikuno, T. (1998). Genetics-based multiprocessor scheduling using task duplication. Microprocessors and Microsystems, 22(3-4):197–207.
Wang, L., Siegel, H. J., Roychowdhury, V. P., and Maciejewski, A. A. (1997). Task matching and scheduling in heterogeneous computing environments using a geneticalgorithm-based approach. Journal of parallel and distributed computing, 47(1):8–22.
Wang, X., Yeo, C. S., Buyya, R., and Su, J. (2011). Optimizing the makespan and reliability for workflow applications with reputation and a look-ahead genetic algorithm. Future Generation Computer Systems, 27(8):1124–1134.
Wu, A. S., Yu, H., Jin, S., Lin, K.-C., and Schiavone, G. (2004). An incremental genetic algorithm approach to multiprocessor scheduling. IEEE Transactions on parallel and distributed systems, 15(9):824–834.
Xu, Y., Li, K., Hu, J., and Li, K. (2014). A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Information Sciences, 270:255–287.
Yao, W., You, J., and Li, B. (2004). Main sequences genetic scheduling for multiprocessor systems using task duplication. Microprocessors and Microsystems, 28(2):85–94.
Zomaya, A. Y., Ward, C., and Macey, B. (1999). Genetic scheduling for parallel processor systems: comparative studies and performance issues. IEEE Transactions on Parallel and Distributed Systems, 10(8):795–812.
Publicado
15/10/2019
Como Citar
SILVA, Eduardo da; GABRIEL, Paulo.
Genetic algorithms and multiprocessor task scheduling: A systematic literature review. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 16. , 2019, Salvador.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 250-261.
ISSN 2763-9061.
DOI: https://doi.org/10.5753/eniac.2019.9288.
