A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. (English) Zbl 1341.68020
Summary: On parallel and distributed heterogeneous computing systems, a heuristic-based task scheduling algorithm typically consists of two phases: task prioritization and processor selection. In a heuristic based task scheduling algorithm, different prioritization will produce different makespan on a heterogeneous computing system. Therefore, a good scheduling algorithm should be able to efficiently assign a priority to each subtask depending on the resources needed to minimize makespan. In this paper, a task scheduling scheme on heterogeneous computing systems using a multiple priority queues genetic algorithm (MPQGA) is proposed. The basic idea of our approach is to exploit the advantages of both evolutionary-based and heuristic-based algorithms while avoiding their drawbacks. The proposedalgorithm incorporates a genetic algorithm (GA) approach to assign a priority to each subtask while using a heuristic-based earliest finish time (EFT) approach to search for a solution for the task-to-processor mapping. The MPQGA method also designs crossover, mutation, and fitness function suitable for the scenario of directed acyclic graph (DAG) scheduling. The experimental results for large-sized problems from a large set of randomly generated graphs as well as graphs of real-world problems with various characteristics show that the proposed MPQGA algorithm outperforms two non-evolutionary heuristics and a random search method in terms of schedule quality.
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
Keywords:
directed acyclic graph; genetic algorithm; heuristic algorithm; makespan; multiple priority queue; task schedulingSoftware:
HypertoolReferences:
| [1] | Topcuoglu, H.; Hariri, S.; Wu, M.-Y., Performance-effective and low-complexity task scheduling for heterogeneous computing, IEEE Trans. Parallel Distrib. Syst., 13, 3, 260-274 (2002) |
| [3] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman: W.H. Freeman New York · Zbl 0411.68039 |
| [4] | Zomaya, A.; Ward, C.; Macey, B., Genetic scheduling for parallel processor systems: comparative studies and performance issues, IEEE Trans. Parallel Distrib. Syst., 10, 8, 795-812 (1999) |
| [5] | Kwok, Y.-K.; Ahmad, I., Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM Comput. Surv. (CSUR), 31, 4, 406-471 (1999) |
| [7] | Gkoutioudi, K.; Karatza, H. D., Task cluster scheduling in a grid system, Simul. Modell. Practice Theory, 18, 9, 1242-1252 (2010), http://dx.doi.org/10.1016/j.simpat.2010.04.011 |
| [8] | Mishra, P. K.; Mishra, A.; Mishra, K. S.; Tripathi, A. K., Benchmarking the clustering algorithms for multiprocessor environments using dynamic priority of modules, Appl. Math. Modell., 36, 12, 6243 (2012), http://dx.doi.org/10.1016/j.apm.2012.02.011 · Zbl 1349.68042 |
| [9] | Lin, C.-S.; Lin, C.-S.; Lin, Y.-S.; Hsiung, P.-A.; Shih, C., Multi-objective exploitation of pipeline parallelism using clustering, replication and duplication in embedded multi-core systems, J. Syst. Architect., 59, 10, Part C, 1083-1094 (2013), http://dx.doi.org/10.1016/j.sysarc.2013.05.024 |
| [10] | Shin, K.; Cha, M.; Jang, M.; Jung, J.; Yoon, W.; Choi, S., Task scheduling algorithm using minimized duplications in homogeneous systems, J. Parallel Distrib. Comput., 68, 8, 1146-1156 (2008), http://dx.doi.org/10.1016/j.jpdc.2008.04.001 · Zbl 1243.68127 |
| [11] | Sinnen, O.; To, A.; Kaur, M., Contention-aware scheduling with task duplication, J. Parallel Distrib. Comput., 71, 1, 77-86 (2011), http://dx.doi.org/10.1016/j.jpdc.2010.10.004 |
| [12] | Tang, X.; Li, K.; Liao, G.; Li, R., List scheduling with duplication for heterogeneous computing systems, J. Parallel Distrib. Comput., 70, 4, 323-329 (2010), http://dx.doi.org/10.1016/j.jpdc.2010.01.003 · Zbl 1233.68092 |
| [13] | Badawi, A. A.; Shatnawi, A., Static scheduling of directed acyclic data flow graphs onto multiprocessors using particle swarm optimization, Comput. Oper. Res., 40, 10, 2322-2328 (2013), http://dx.doi.org/10.1016/j.cor.2013.03.015 · Zbl 1348.68022 |
| [14] | Kashan, A. H.; Kashan, M. H.; Karimiyan, S., A particle swarm optimizer for grouping problems, Inform. Sci., 252, 0, 81-95 (2013), http://dx.doi.org/10.1016/j.ins.2012.10.036 · Zbl 1320.68170 |
| [15] | Zhao, F.; Tang, J.; Wang, J.; Jonrinaldi, An improved particle swarm optimization with decline disturbance index (ddpso) for multi-objective job-shop scheduling problem, Comput. Oper. Res., 45, 0, 38-50 (2014), http://dx.doi.org/10.1016/j.cor.2013.11.019 · Zbl 1348.90337 |
| [17] | Kang, Q.; He, H., A novel discrete particle swarm optimization algorithm for meta-task assignment in heterogeneous computing systems, Microproc. Microsyst., 35, 1, 10-17 (2011), http://dx.doi.org/10.1016/j.micpro.2010.11.001 |
| [18] | Ferrandi, F.; Lanzi, P.-L.; Pilato, C.; Sciuto, D.; Tumeo, A., Ant colony heuristic for mapping and scheduling tasks and communications on heterogeneous embedded systems, IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst., 29, 6, 911-924 (2010), http://dx.doi.org/10.1109/TCAD.2010.2048354 |
| [19] | Kim, H.; Kang, S., Communication-aware task scheduling and voltage selection for total energy minimization in a multiprocessor system using ant colony optimization, Inform. Sci., 181, 18, 3995-4008 (2011), http://dx.doi.org/10.1016/j.ins.2011.04.037 |
| [20] | Yildiz, A. R., Optimization of cutting parameters in multi-pass turning using artificial bee colony-based approach, Inform. Sci., 220, 399-407 (2013) |
| [21] | Torres-Jimenez, J.; Rodriguez-Tello, E., New bounds for binary covering arrays using simulated annealing, Inform. Sci., 185, 1, 137-152 (2012), http://dx.doi.org/10.1016/j.ins.2011.09.020 |
| [23] | Yildiz, A., Cuckoo search algorithm for the selection of optimal machining parameters in milling operations, Int. J. Adv. Manuf. Technol., 64, 1-4, 55-61 (2013) |
| [24] | Garai, G.; Chaudhurii, B., A novel hybrid genetic algorithm with tabu search for optimizing multi-dimensional functions and point pattern recognition, Inform. Sci., 221, 0, 28-48 (2013), http://dx.doi.org/10.1016/j.ins.2012.09.012 |
| [26] | Yildiz, A. R., A comparative study of population-based optimization algorithms for turning operations, Inform. Sci., 210, 81-88 (2012) |
| [27] | Yildiz, A. R., Comparison of evolutionary-based optimization algorithms for structural design optimization, Eng. Appl. Artif. Intell., 26, 1, 327-333 (2013), http://dx.doi.org/10.1016/j.engappai.2012.05.014 |
| [28] | Swiecicka, A.; Seredynski, F.; Zomaya, A., Multiprocessor scheduling and rescheduling with use of cellular automata and artificial immune system support, IEEE Trans. Parallel Distrib. Syst., 17, 3, 253-262 (2006) |
| [29] | Yildiz, A.; Öztürk, N.; Kaya, N.; Öztürk, F., Hybrid multi-objective shape design optimization using taguchis method and genetic algorithm, Struct. Multidisc. Optim., 34, 4, 317-332 (2007), http://dx.doi.org/10.1007/s00158-006-0079-x |
| [30] | Lin, C.-H., A rough penalty genetic algorithm for constrained optimization, Inform. Sci., 241, 0, 119-137 (2013), http://dx.doi.org/10.1016/j.ins.2013.04.001 |
| [31] | Hou, E.; Ansari, N.; Ren, H., A genetic algorithm for multiprocessor scheduling, IEEE Trans. Parallel Distrib. Syst., 5, 2, 113-120 (1994) |
| [32] | Lu, H.; Niu, R.; Liu, J.; Zhu, Z., A chaotic non-dominated sorting genetic algorithm for the multi-objective automatic test task scheduling problem, Appl. Soft Comput., 13, 5, 2790-2802 (2013), http://dx.doi.org/10.1016/j.asoc.2012.10.001 |
| [33] | Behnamian, J.; Ghomi, S. F., The heterogeneous multi-factory production network scheduling with adaptive communication policy and parallel machine, Inform. Sci., 219, 0, 181-196 (2013) · Zbl 1293.90022 |
| [34] | Kołodziej, J.; Khan, S. U., Multi-level hierarchic genetic-based scheduling of independent jobs in dynamic heterogeneous grid environment, Inform. Sci., 214, 0, 1-19 (2012) |
| [35] | Li, K.; Tong, Z.; Liu, D.; Tesfazghi, T.; Liao, X., A pts-pgats based approach for data-intensive scheduling in data grids, Front. Comput. Sci. China, 5, 4, 513-525 (2011) |
| [36] | Daoud, M. I.; Kharma, N., A hybrid heuristic-genetic algorithm for task scheduling in heterogeneous processor networks, J. Parallel Distrib. Comput., 71, 11, 1518-1531 (2011), http://dx.doi.org/10.1016/j.jpdc.2011.05.005 |
| [37] | Pedergnana, M.; Marpu, P.; Mura, M.; Benediktsson, J.; Bruzzone, L., A novel technique for optimal feature selection in attribute profiles based on genetic algorithms, IEEE Trans. Geosci. Remote Sens., 51, 6, 3514-3528 (2013), http://dx.doi.org/10.1109/TGRS.2012.2224874 |
| [38] | Robles-Ortega, M. D.; Ortega, L.; Feito, F. R., A new approach to create textured urban models through genetic algorithms, Inform. Sci., 243, 0, 1-19 (2013), http://dx.doi.org/10.1016/j.ins.2013.03.053 |
| [39] | Köker, R., A genetic algorithm approach to a neural-network-based inverse kinematics solution of robotic manipulators based on error minimization, Inform. Sci., 222, 0, 528-543 (2013), http://dx.doi.org/10.1016/j.ins.2012.07.051 · Zbl 1293.68271 |
| [40] | Zhang, R.; Wu, C., Bottleneck machine identification method based on constraint transformation for job shop scheduling with genetic algorithm, Inform. Sci., 188, 0, 236-252 (2012) · Zbl 1247.90166 |
| [41] | Balin, S., Parallel machine scheduling with fuzzy processing times using a robust genetic algorithm and simulation, Inform. Sci., 181, 17, 3551-3569 (2011) |
| [42] | Wen, Y.; Xu, H.; Yang, J., A heuristic-based hybrid genetic-variable neighborhood search algorithm for task scheduling in heterogeneous multiprocessor system, Inform. Sci., 181, 3, 567-581 (2011) |
| [43] | Lam, A.; Li, V., Chemical-reaction-inspired metaheuristic for optimization, IEEE Trans. Evol. Comput., 14, 3, 381-399 (2010) |
| [45] | Fogel, D. B., Evolutionary algorithms in theory and practice, Complexity, 2, 4, 26-27 (1997), http://dx.doi.org/10.1002/(SICI)1099-0526(199703/04) |
| [46] | Goldberg, D., Genetic Algorithms in Search. Genetic Algorithms in Search, Optimization, and Machine Learning (1989), Addison-Wesley: Addison-Wesley Reading, Massachusetts, New York · Zbl 0721.68056 |
| [47] | Song, S.; Hwang, K.; Kwok, Y.-K., Risk-resilient heuristics and genetic algorithms for security-assured grid job scheduling, IEEE Trans. Comput., 55, 6, 703-719 (2006) |
| [48] | Nix, A.; Vose, M., Modeling genetic algorithms with markov chains, Ann. Math. Artif. Intell., 5, 1, 79-88 (1992) · Zbl 1034.68534 |
| [49] | Wright, A. H.; Zhao, Y., Markov chain models of genetic algorithms, (Proceedings of the Genetic and Evolutionary Computation (GECCO) Conference (1999), Morgan Kaufmann), 734-741 |
| [50] | Reeves, C. R., A genetic algorithm for flowshop sequencing, Comput. Oper. Res., 22, 1, 5-13 (1995), genetic Algorithms. doi:http://dx.doi.org/10.1016/0305-0548(93)E0014-K · Zbl 0815.90097 |
| [51] | Ahuja, R. K.; Orlin, J. B., Commentary developing fitter genetic algorithms, INFORMS J. Comput., 9, 3, 251-253 (1997) |
| [52] | Kapsalis, A.; Rayward-Smith, V. J.; Smith, G. D., Solving the graphical steiner tree problem using genetic algorithms, J. Oper. Res. Soc., 44, 4, 397-406 (1993) · Zbl 0774.90083 |
| [53] | Levine, D., Commentary genetic algorithms: a practitioner’s view, INFORMS J. Comput., 9, 3, 256-259 (1997) |
| [54] | Davis, L., Genetic Algorithms and Simulated Annealing (1987), Morgan Kaufmann Publishers Inc.: Morgan Kaufmann Publishers Inc. San Francisco, CA, USA · Zbl 0684.68013 |
| [56] | Wu, M.-Y.; Gajski, D., Hypertool: a programming aid for message-passing systems, IEEE Trans. Parallel Distrib. Syst., 1, 3, 330-343 (1990) |
| [58] | Li, K., Performance analysis of power-aware task scheduling algorithms on multiprocessor computers with dynamic voltage and speed, IEEE Trans. Parallel Distrib. Syst., 19, 11, 1484-1497 (2008) |
| [59] | Li, K., Scheduling precedence constrained tasks with reduced processor energy on multiprocessor computers, IEEE Trans. Comput., 61, 12, 1668-1681 (2012) · Zbl 1365.68126 |
| [60] | Holland, J., Adaptation in Natural and Artificial Systems (1975), University of Michigan Press: University of Michigan Press Ann Arbor, MI, USA · Zbl 0317.68006 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
