Uncertainty-aware task scheduling algorithm in edge computing environments

When designing task scheduling algorithms, the uncertainty of task execution duration is an important concern, which impacts whether the task completion time can meet its deadline constraint. In this paper, we study the uncertainty-aware task scheduling problem in edge computing systems and formulate a scheduling optimization model with the objective of minimizing the edge provider’s monetary cost. By modeling the task execution duration as a random variable and deriving the complete probability distribution of the task completion time, the formulated model introduces a probabilistic constraint on the task’s deadline to guarantee the task is completed on time with an adjustable probability threshold. To solve this problem, this paper further proposes a metaheuristic algorithm that is built upon the bat algorithm’s search strategy. The proposed algorithm contains two key algorithmic components. The mapping operator enables the connection between the bat space and the scheduling solution space, and the evaluation operator enables the determination of the candidate solution’s feasibility and the calculation of the optimization objective value. Simulation results based on comparative experiments demonstrate that the proposed algorithm is capable of obtaining high-quality task scheduling solutions. © 2024 Northeast University. All rights reserved.