Research on scheduling of two types of tasks in multi-cloud environment based on multi-task optimization algorithm. (English) Zbl 07922849
Summary: The multi-cloud environment (MCE) tasks can be classified as CPU-intensive or I/O-intensive. Using a single model to handle two tasks often results in system performance issues due to mismatches between task requirements and resource demands, caused by differing data characteristics. In this paper, a multi-task multi-objective optimization (MTMO) model is constructed. A multi-objective evolutionary algorithm with quadratic crossover is used to simultaneously schedule two types of tasks. This improves scheduling efficiency. First, according to the different data characteristics of tasks in MCE, tasks are separated into CPU-intensive tasks with large amounts of computation and high demand for CPU resources and I/O-intensive tasks that require frequent memory access. Different multi-objective optimization models are constructed according to the characteristics of per-task. Secondly, each multi-objective optimization model is constructed as a sub-task in a multi-task environment to build a MTMO model. Then, a multi-objective multi-factor evolutionary algorithm based on quadratic crossover, I-MOMFEA-II, is proposed to schedule the two types of tasks simultaneously. Finally, the proposed algorithm in this paper improved cost, time, and energy consumption for CPU-intensive tasks by 7.6%, 20.1%, and 16.1% respectively, for I/O-intensive tasks, it improved cost, time, and VM throughput by 10%, 17.7%, and 36.5% respectively. The experimental results from simulations confirm the effectiveness of I-MOMFEA-II in elevating task scheduling productivity.
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 68W99 | Algorithms in computer science |
| 93A30 | Mathematical modelling of systems (MSC2010) |
Keywords:
multi-tasking evolutionary algorithm; multi-objective optimization; task scheduling; multi-cloudReferences:
| [1] | Algorithm1: I-MOMFEA-II algorithm |
| [2] | τ i = mod (i, K) + 1 //τ i is skill factor, K is the total number of tasks 4. Evaluate pi on task τ i |
| [3] | Φi is computed through ranking based on NFi and CDi. // Φi is scalar fitness |
| [4] | Select n•K parents from P(t) using Tournament Selection 10. Learn RMP(t) |
| [5] | Randomly select qi, qj from P(t) |
| [6] | Intra-task crossover and mutate (qi, qj) to get [qa, qb] with skill τ i 15. else if rand ≤ rmpτ i,τ j |
| [7] | Inter-task crossover and mutate (qi, qj) to get [qa, qb] with random τ i or τ j 17. else |
| [8] | Mutate and Intra-task crossover each to get [qa, qb] with respective skills 20. Evaluate [qa, qb] on assigned tasks only 21. Pm(t) = Pm(t)∪ [qa, qb] |
| [9] | Update Φi for each pi∈ C(t) |
| [10] | Select top N•K fittest from C(t) as P(t+1) 25. t = t + 1 Algorithm2: Crossover Operator Based on Quadratic Crossover Input: parent individuals pa and pb; |
| [11] | Inter-population crossover distribution index parameter:mu-between; |
| [12] | Intra-population crossover distribution index parameter:mu-in; Output: Offspring individuals ca and cb; |
| [13] | ca1,cb1)=SBX(pa,pb,mu-in); |
| [14] | Generate two random numbers:s1,e1,and e1 ≤ s1+2; |
| [15] | ca=Two-Point-Cross(ca1,pa,s1,e1); |
| [16] | ca=Two-Point-Cross(ca1,pb,s1,e1); |
| [17] | ca1,cb1)=SBX(pa,pb,mu-between); |
| [18] | The cb undergoes the same steps as the ca to complete the crossover. 23875.55307 128728.439 94879.68 EMT-PD 19723.43973 134386.4681 98417.94 |
| [19] | I-MO-MFEA-II 31142.64415 168429.1646 111633.3242 |
| [20] | I-MO-MFEA-II 42078.34615 237359.4439 145846 MO-MFEA-II 45879.91768 242683.2795 144876.48 |
| [21] | I-MO-MFEA-II 638630.051 1090622.473 832673.975 MO-MFEA-II 655320.4023 1109395.444 837881.81 |
| [22] | I-MO-MFEA-II 805204.0897 1448079.981 876880.2925 |
| [23] | I-MO-MFEA-II 1047031.03 1805537.49 1150850.72 MO-MFEA-II 1054619.114 1843665.045 1166835.1 |
| [24] | I-MO-MFEA-II 930623.7063 1490538.112 1097135.47 MO-MFEA-II 975778.2003 1508011.374 1102930.11 |
| [25] | I-MO-MFEA-II 1143712.812 1831982.893 1244669.67 MO-MFEA-II 1193470.461 1889552.957 1265711.818 |
| [26] | I-MO-MFEA-II 1403211.894 2181834.984 1402274.345 MO-MFEA-II 1436035.36 2243946.812 1423787.155 |
| [27] | L. Abualigah and M. Alkhrabsheh, Amended hybrid multi-verse optimizer with genetic algorithm for solving task scheduling problem in cloud computing, The Journal of Supercomputing, 2021, 78(1), 740-765. |
| [28] | T. A. Ahanger, H. A. Abdeljaber and M. Y. Uddin, Development of a hybrid algorithm for efficient task scheduling in cloud computing environment using artificial intelligence, International Journal of Computers Communications and Control, 2021, 16(5). |
| [29] | K. K. Bali, A. Gupta, Y. S. Ong, et al., Cognizant multitasking in multiobjec-tive multifactorial evolution: MO-MFEA-II, IEEE Trans Cybern, 2021, 51(4), 1784-1796. |
| [30] | X. Cai, S. Geng, D. Wu, et al., A multicloud-model-based many-objective intelli-gent algorithm for efficient task scheduling in internet of things, IEEE Internet of Things Journal, 2021, 8(12), 9645-9653. |
| [31] | Z. H. Cui, X. H. Xu, F. Xue, et al., Personalized Recommendation System Based on Collaborative Filtering for IoT Scenarios, IEEE Transactions on Services Computing, 2020. DOI: 10.1109/TSC.2020.2964552. · doi:10.1109/TSC.2020.2964552 |
| [32] | B. Da, A. Gupta and Y. -S. Ong, Curbing negative influences online for seam-less transfer evolutionary optimization, IEEE Transactions on Cybernetics, 2019, 49(12), 4365-4378. |
| [33] | R. Dai, J. Jie, H. Zheng, et al., Framework and experimental analysis of gener-alised surrogate-assisted particle swarm optimization, International Journal of Computing Science and Mathematics, 2022, 15(4), 332-346. |
| [34] | G. Ding and F. Dong, An improved pigeon-inspired optimisation for continuous function optimisation problems, International Journal of Computing Science and Mathematics, 2023, 17(3), 207-219. |
| [35] | T. T. Dong, L. Zhou, L. Chen, et al., A Hybrid algorithm for workflow schedul-ing in cloud environment, International Journal of Bio-Inspired Computation, 2023, 21(1), 48-56. |
| [36] | M. Farid, R. Latip, M. Hussin, et al., Weighted-adaptive inertia strategy for multi-objective scheduling in multi-clouds, Computers, Materials and Continua, 2022, 72(1), 1529-1560. |
| [37] | A. Gupta, Y. S. Ong and L. Feng, Multifactorial evolution: Toward evolu-tionary multitasking, IEEE Transactions on Evolutionary Computation, 2016, 20(3), 343-357. |
| [38] | A. Gupta, Y. S. Ong, L. Feng, et al., Multiobjective multifactorial optimization in evolutionary multitasking, IEEE Transactions on Cybernetics, 2017, 47(7), 1652-1665. |
| [39] | Y. S. Hao, M. D. Xia, N. Wen, et al., Parallel task scheduling under multiclouds, KSII Transactions on Internet and Information Systems, 2017, 11(1), 39-60. |
| [40] | S. Hubert Shanthan and B. J. Arockiam, Rate aware meta task scheduling algorithm for multi cloud computing (RAMTSA), 2nd National Conference on Computational Intelligence, 2018, 012001, Bangalore, India. |
| [41] | S. Kang, B. Veeravalli and K. M. M. Aung, Dynamic scheduling strategy with efficient node availability prediction for handling divisible loads in multi-cloud systems, Journal of Parallel and Distributed Computing, 2018, 113, 1-16. |
| [42] | H. Lan, G. Xu and Y. Yang, An enhanced multi-objective particle swarm op-timization with levy flight, International Journal of Computing Science and Mathematics, 2023, 17(1), 79-94. |
| [43] | X. Lin, T. Ren, J. Yang, et al., Multi-objective cellular memetic algorithm, International Journal of Computing Science and Mathematics, 2022, 15(3), 213-223. |
| [44] | Y. L. Lv, J. Zhang and L. L. Zuo, Genetic regulatory network-based optimiza-tion of master production scheduling and mixed-model sequencing in assembly lines, International Journal of Bio-Inspired Computing, 2022, 20(3), 150-159. |
| [45] | J. P. B. Mapetu, Z. Chen and L. Kong, Low-time complexity and low-cost binary particle swarm optimization algorithm for task scheduling and load balancing in cloud computing, Applied Intelligence, 2019, 49(9), 3308-3330. |
| [46] | S. K. Mishra, Energy-aware task allocation for multi-cloud networks, IEEE Access, 2020, 8, 178825-178834. |
| [47] | Z. Liang, W. Liang, Z. Wang, et al., Multiobjective evolutionary multitasking with two-stage adaptive knowledge transfer based on population distribution, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2022, 52(7), 4457-4469. |
| [48] | Z. Liang, J. Zhang, L. Feng, et al., A hybrid of genetic transform and hyper-rectangle search strategies for evolutionary multi-tasking, Expert Systems with Applications, 2019, 138. |
| [49] | J. Liu, P. Li, G. Wang, et al., A multitasking electric power dispatch approach with multi-objective multifactorial optimization algorithm, IEEE Access, 2020, 8, 155902-155911. |
| [50] | A. Roy, S. Midya, D. Hazra, et al., A hybrid task scheduling algorithm for efficient task management in multi-cloud environment, Advances in Intelligent Systems and Computing, 2018, 811, 47-57. |
| [51] | W. H. Tan and J. Mohamad-Saleh, Alligator optimisation algorithm for solv-ing unconstrainted optimisation problems, International Journal of Bio-Inspired Computation, 2023, 21(1), 11-25. |
| [52] | Z. Tang, M. Gong and M. Zhang, Evolutionary multi-task learning for modular extremal learning machine, in 2017 Congress on Evolutionary Computation, 2017, 474-479. |
| [53] | H. ThiThanh Binh, P. Dinh Thanh, T. Ba Trung, et al., Effective multifactorial evolutionary algorithm for solving the cluster shortest path tree problem, in 2018 Congress on Evolutionary Computation, 2018, 1-8. |
| [54] | L. J. Wu, D. Wu, T. H. Zhao, et al., Dynamic multi-objective evolutionary algorithm based on knowledge transfer, Information Sciences, 2023, 636, 118886. |
| [55] | F. Xue, Q. Hai, Y. Gong, et al., RVEA-based multi-objective workflow schedul-ing in cloud environments, International Journal of Bio-Inspired Computation, 2022, 20(1), 49-57. |
| [56] | W. S. Yang, L. Chen, Y. Y. Li, et al., A many-objective particle swarm opti-mization algorithm based on convergence assistant strategy, International Jour-nal of Bio-Inspired Computing, 2022, 20(2), 104-118. |
| [57] | Y. Yuan, Y. S. Ong, L. Feng, et al., Evolutionary multitasking for multiobjec-tive continuous optimization: Benchmark problems, performance metrics, and baseline results, 2017. DOI: 10.48550/arXiv.1706.02766. · doi:10.48550/arXiv.1706.02766 |
| [58] | Q. Zhang, S. Geng and X. Cai, Survey on task scheduling optimization strat-egy under multi-cloud environment, Computer Modeling in Engineering and Sciences, 2023, 135(3), 1863-1900. |
| [59] | T. H. Zhao, L. J. Wu, D. Wu, et al., Multi-factor evolution for large-scale multi-objective cloud task scheduling, KSII Transactions on Internet and Information Systems, 2023, 17(4), 1100-1122. |
| [60] | L. Zhou, L. Feng, J. Zhong, et al., Evolutionary multitasking in combinatorial search spaces: A case study in capacitated vehicle routing problem, in 2017 Symposium Series on Computational Intelligence, 2017, 1-8. |
| [61] | M. Zhou, R. Wu and H. Sun, An artificial bee colony algorithm with a distance factor, International Journal of Computing Science and Mathematics, 2022, 16(4), 355-376. |
| [62] | Q. H. Zhu, H. Tang, J. J. Huang, et al., Task scheduling for multi-cloud com-puting subject to security and reliability constraints, IEEE/CAA Journal of Automatica Sinica, 2021, 8(4), 848-865. |
| [63] | E. Zitzler and L. Thiele, Multiobjective optimization using evolutionary algo-rithms -A comparative case study, in 5th International Conference on Parallel Problem Solving from Nature, PPSN 1998, Amsterdam, Netherlands, 1998, 292-301. |
| [64] | E. Zitzler, L. Thiele, M. Laumanns, et al., Performance assessment of multiob-jective optimizers: An analysis and review, IEEE Transactions on Evolutionary Computation, 2003, 7(2), 117-132. |
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.
