随着物联网、人工智能等技术的高速发展,各类终端设备的数量和计算需求急剧增长,例如自动驾驶、VR等计算密集型应用对延迟日益敏感。海量数据长距离的传播时延、有限的网络带宽和不稳定的网络环境等弊端使得传统云计算服务无法满足这些应用的服务质量(QoS)要求。因此,边缘计算的概念应运而生。作为云计算的有益补充,通过在网络边缘侧部署小型边缘服务器并与远程云协同管理,边缘计算得以为用户提供低延迟、高带宽、高性能的计算服务。但另一方面,相对于远程云来说,边缘服务器的存储、计算资源较为受限,每台边缘服务器同一时刻只能配置少量功能来处理相应的任务。与此同时,日益复杂的终端应用通常由一组具有先后约束关系的相关功能组成,我们将用户对应用的请求建模成一个有向无环图(DAG),图中节点代表需要执行某功能的任务,图中有向边代表任务之间的先后约束关系。当一个应用请求在线到达边缘系统后,我们需要将其中的任务调度至边缘服务器或云上以使其尽可能在截止期限前完成。任务在开始执行前必须满足DAG中的先后约束关系,同时在被分派的服务器上也应进行相应功能的按需配置。本文将对上述实际场景下的DAG调度进行研究,目标是使更多的应用请求在其截止期限前完成。具体工作有如下几点:·针对离线单个应用请求的调度问题,在每台边缘服务器上的功能配置固定的特殊情况下,我们给出了可以高效地找到最佳任务调度方案的策略。当允许按需配置功能时,我们提出了一种新颖的近似算法GenDoc,并从理论上分析了其与最优解的误差项。·针对在线多个应用请求的调度问题,基于列表调度方法,我们提出了高效且易于在实践中部署的在线算法OnDoc,该算法通过维护多应用请求调度队列,使服务器的资源得到充分利用,从而减少应用请求的完成时间,使得更多的应用请求满足其截止期限。·基于Alibaba2018真实生产环境中的数据集,我们对算法进行了大规模模拟以验证其性能。实验结果表明,我们提出的GenDoc和OnDoc算法在各自场景下均优于基准算法,且在各关键参数变化下均表现最优。GenDoc在应用的平均完成时间上至少比基准算法缩减了 24%(最多为54%)。而OnDoc满足其截止期限的应用请求数量至少是基准算法的1.9 ×。