2022

Journal

Appl Intell 53, 9009–9037 (2023)

Bag-of-Tasks is a well-known model that processes big-data applications supporting embarrassingly parallel jobs with independent tasks. Scheduling Bag-of-Tasks in a dynamic multi-cloud environment is an NP-hard problem that has attracted a lot of attention in the last years. Such a problem can be modeled using a bi-level optimization framework due to its hierarchical scheme. Motivated by this issue, in this paper, an efficient bi-level multi-follower algorithm, based on hybrid metaheuristics, is proposed to solve the multi-objective budget-constrained dynamic Bag-of-Tasks scheduling problem in a heterogeneous multi-cloud environment. In our proposed model, the objective function differs depending on the scheduling level: The upper level aims to minimize the makespan of the whole Bag-of-Tasks under budget constraints; while each follower aims to minimize the makespan and the execution cost of tasks belonging to the Bag-of-Tasks. Since multiple conflicting objectives exist in the lower level, we propose an improved variant of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) called Efficient NSGA-II (E-NSGA-II), applying a recently proposed quick non-dominated sorting algorithm (QNDSA) with quasi-linear average time complexity. By performing experiments on proposed synthetic datasets, our algorithm demonstrates high performance in terms of makespan and execution cost while respecting budget constraints. Statistical analysis validates the outperformance of our proposal regarding the considering metrics.

TY - JOUR

AU - Karaja, Mouna

AU - Chaabani, Abir

AU - Azzouz, Ameni

AU - Ben Said, Lamjed

PY - 2023

DA - 2023/04/01

TI - Efficient bi-level multi objective approach for budget-constrained dynamic Bag-of-Tasks scheduling problem in heterogeneous multi-cloud environment

JO - Applied Intelligence

SP - 9009

EP - 9037

VL - 53

IS - 8

AB - Bag-of-Tasks is a well-known model that processes big-data applications supporting embarrassingly parallel jobs with independent tasks. Scheduling Bag-of-Tasks in a dynamic multi-cloud environment is an NP-hard problem that has attracted a lot of attention in the last years. Such a problem can be modeled using a bi-level optimization framework due to its hierarchical scheme. Motivated by this issue, in this paper, an efficient bi-level multi-follower algorithm, based on hybrid metaheuristics, is proposed to solve the multi-objective budget-constrained dynamic Bag-of-Tasks scheduling problem in a heterogeneous multi-cloud environment. In our proposed model, the objective function differs depending on the scheduling level: The upper level aims to minimize the makespan of the whole Bag-of-Tasks under budget constraints; while each follower aims to minimize the makespan and the execution cost of tasks belonging to the Bag-of-Tasks. Since multiple conflicting objectives exist in the lower level, we propose an improved variant of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) called Efficient NSGA-II (E-NSGA-II), applying a recently proposed quick non-dominated sorting algorithm (QNDSA) with quasi-linear average time complexity. By performing experiments on proposed synthetic datasets, our algorithm demonstrates high performance in terms of makespan and execution cost while respecting budget constraints. Statistical analysis validates the outperformance of our proposal regarding the considering metrics.

SN - 1573-7497

UR - https://doi.org/10.1007/s10489-022-03942-1

DO - 10.1007/s10489-022-03942-1

ID - Karaja2023

ER -