A Novel Model for Online Scheduling of Approximation Jobs

Approximation jobs are widely deployed on Amazon EC2, which compute partial task segments to obtain useful results. For such jobs, maximizing total profit is the primary goal, where profit equals the sum of job utilities minus the total machine costs. Unfortunately, maximizing the total profit of approximation jobs is an NP-hard problem. This problem is further complicated by online job arrivals and heterogeneous resource demands across different tasks. This work builds an optimization framework that clearly characterizes job utility and machine costs to resolve this problem. Within this framework, we propose an efficient dual algorithm for job scheduling. The proposed method leverages the dual-fitting approach to measure algorithm performance by analyzing the primal and dual objective growth at each step. This work proves that our algorithm achieves a constant competitive ratio. The results from the trace-driven simulations demonstrate that our algorithms consistently outperform these baselines across various metrics.