Carbon aware scheduling reduces emissions for edge computing jobs
Pre-emptive Carbon Aware Scheduling for Edge Workloads
Data Structures and Algorithms
Summary
Electricity used to run computing tasks comes from a mix of sources like coal and wind, which change over time and place in how much pollution they cause. This paper studies how to schedule jobs on edge computers or send them to the cloud to reduce pollution while still meeting deadlines and task orders. The authors provide an exact method for some cases and approximation methods for harder cases, showing trade-offs between carbon and cost. They also tested their approach on synthetic and real-world data to see how well it works.
What this means in practice
- •For edge computing operators: Schedule edge workloads to reduce carbon emissions without missing deadlines by balancing local execution and cloud outsourcing costs.
- •For cloud service teams: Manage offloading of edge jobs to cloud servers cost-effectively to complement carbon-aware scheduling strategies at the edge.
Authors
Cecilia Chen, Rajni Dabas, Samir Khuller, Emilie Rivkin
Abstract
Power grids use a constantly changing mix of fossil fuels and clean renewables like solar and wind. Because of this, the {\em carbon footprint} fluctuates drastically based on time and geographic location. Time-varying carbon intensity creates opportunities to reduce carbon emissions by shifting workloads to cleaner periods, but deadlines, task dependencies, and limited edge capacity constrain this flexibility. We study carbon-aware scheduling of jobs with release times, deadlines, and arbitrary precedence constraints under piecewise-constant carbon costs. Jobs execute preemptively on a single edge server or are outsourced at job-dependent costs to an unlimited-capacity cloud, modeled as providing instantaneous execution. The objective is to minimize the sum of edge carbon costs and cloud outsourcing costs while satisfying all timing and precedence constraints. For edge-only execution, we give an exact polynomial-time algorithm. Allowing cloud outsourcing makes the problem NP-hard, but we obtain a fully polynomial-time approximation scheme through a reduction to preemptive scheduling with rejection penalties (weighted tardiness). In contrast, even two edge servers without job migration admit no polynomially bounded approximation when carbon-cost variation is unrestricted, unless \(P=NP\). We complement these theoretical results with experiments on controlled synthetic workloads and production-derived Alibaba traces. On synthetic instances, our incremental max-flow implementation is $4.96\times$ faster on average than a direct min-cost flow, while experiements on production-derived workloads evaluate its performance under realistic job structures.