.png){kind=icon}
.png){kind=icon}
Return
Efficient bi-level multi objective approach for budget-constrained dynamic Bag-of-Tasks scheduling problem in heterogeneous multi-cloud environment
.png){kind=icon}
PRE
AI
DOI：10.1007/s10489-022-03942-1.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Heterogeneous multi-cloud
Bag-of-Tasks scheduling
Budget-constrained
Bi-level multi-follower
NSGA-II