不确定性感知的边缘计算任务调度算法
CSTR:
作者:
作者单位:

南京理工大学 计算机科学与工程学院,南京 210094

作者简介:

通讯作者:

E-mail: sunj@njust.edu.cn.

中图分类号:

TP273

基金项目:

江苏省重点研发计划项目(BE2022065-2);江苏省创新支撑计划项目(BZ2023046);教育部产学研创新基金项目(2020ITA03002,2021ITA01004);国家自然科学基金项目(62172224, U23B2006);江苏省自然科学基金项目(BK20220138).


Uncertainty-aware task scheduling algorithm in edge computing environments
Author:
Affiliation:

School of Computer Science and Engineering,Nanjing University of Science and Technology,Nanjing 210094,China

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    任务执行时长的不确定性是设计任务调度算法时的一个重要问题,关系到调度方案能否满足任务的截止时间要求.鉴于此,研究不确定性感知的边缘计算任务调度问题,以最小化边缘提供商开销为优化目标建立任务调度问题的优化模型.该模型将任务执行时长建模为随机变量并推导出任务完成时间的完整概率分布,引入关于任务截止时间的概率约束,以可调节的概率阈值保证任务按时完成.为求解该问题,进一步提出基于蝙蝠算法搜索策略的元启发式算法,包含两个关键的算法组件,映射算子实现蝙蝠空间与调度解空间的关联,评估算子实现候选解可行性的判定和优化目标值的计算.基于对比实验的仿真结果表明,所提出算法能够得到高质量的任务调度方案.

    Abstract:

    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.

    参考文献
    相似文献
    引证文献
引用本文

尹璐,周俊龙,孙晋,等.不确定性感知的边缘计算任务调度算法[J].控制与决策,2024,39(7):2405-2413

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2024-06-06
  • 出版日期: 2024-07-20
文章二维码