Abstract: To mitigate the negative impact of unstable edge computing, it designs Geo-distributed job Insurance Mechanism（GIM）, a new task replication and dispatching algorithm that guarantees the completion time of data analytics jobs across clouds and edges. To cater to the parallel processing and resource constraints, it first formulates the problem as a minimax polynomial integer programming. After relaxing the integer constraint, it adopts feasible-point algorithm to quickly converge to the optimal solution of the relaxed problem. Finally, it rounds such optimal solution based on high-risk-task-first heuristic and obtains a high-quality feasible solution of the original problem. The simulations driven by production trace show that GIM beats the other redundant execution strategies by at least 22% in terms of the average job completion time under different system utilization.

Key words: cloud computing, edge computing, task scheduling, insurance mechanism, delay optimization, job completion time

摘要： 为缓解边缘计算的不稳定性，设计了适用于跨域规模的任务复制与分配机制以保障作业各阶段的完成（Geo-distributed job Insurance Mechanism，GIM）。为满足并行任务执行特征和资源限制，先将问题形式化为Min-Max多项式整数规划问题，再放松整数约束并采用feasible-point算法快速地收敛到最优解，最后基于高危任务优先原则对最优解进行取整，得到满足原问题约束的高质量任务复制与分配方案。模拟实验表明，在不同的系统负载下，相比于当前的冗余执行策略，GIM至少能够减少22%的作业平均完成时间。

关键词: 云计算, 边缘计算, 任务调度, 保障机制, 时延优化, 作业完成时间