Pre-emptive Carbon Aware Scheduling for Edge Workloads

1 Introduction

• Carbon-aware scheduling must jointly navigate when workloads run and whether they use limited edge capacity or more expensive cloud servers.Time and location affect carbon intensity, while deferral and placement remain constrained by performance needs.Source: §1 · pp. 1–2

1.2 Related Work

• Prior work covers restricted carbon-aware scheduling and performance-focused offloading, while this paper extends scheduling to arbitrary precedence constraints and schedule-dependent outsourcing choices.Earlier work includes independent-job models and chain-structured jobs; carbon-aware edge-to-cloud frameworks have also optimized performance rather than carbon cost.Source: §1 · p. 2, §1.2 · p. 4

1.1 Problem Definition and Notations

• Jobs have release times, deadlines, and precedence constraints; edge execution is preemptive, while cloud outsourcing is all-or-nothing and incurs job-specific costs.Cloud jobs execute instantaneously with unlimited capacity, but still satisfy timing and precedence constraints.Source: §1.1 · pp. 2–3

1.3 Key Results

• The edge-only problem has an exact polynomial-time algorithm, while cloud outsourcing is NP-hard but admits an FPTAS; two non-migrating edge servers have no polynomially bounded approximation unless P = NP.The multi-server hardness holds with unrestricted carbon-cost variation.Source: §1.3 · p. 5

1.4 Organization of the paper

• The paper’s experiments compare exact solvers, study residual reuse and scalability, evaluate Alibaba-derived workloads, and examine Lawler’s algorithm for the outsourcing reduction.The paper reports a 4.96× average speed advantage for MaxFlow-Passes over direct minimum-cost flow on synthetic workloads.Source: §1.3 · pp. 5–6, §1.4 · p. 6

2 Exact scheduling on a single edge server

• The flow construction is equivalent in cost to feasible preemptive schedules, yielding a polynomial-time route to a minimum-cost schedule or an infeasibility report.Atomic-interval nodes encode available capacity and carbon cost; job nodes encode processing requirements and effective windows.Source: §2 · p. 6

2.1 Post-processing for precedence constraints

• Reordering jobs within their shared busy intervals enforces precedence while preserving the server’s occupied times and carbon cost.Effective windows ensure the reorder remains feasible; the swaps are performed in topological order.Source: §2.1 · pp. 6–7

2.2 Implementation without minimum-cost flow

• The incremental max-flow procedure opens interval capacity in increasing carbon-cost order and retains residual flow, producing a minimum-cost flow of value P.If the final flow is less than P, the instance is infeasible; precedence correction then yields the schedule in Theorem 3.Source: §2.2 · pp. 7–8

3 Approximation with cloud outsourcing

• Cloud outsourcing is NP-hard even for independent jobs with common release and deadline times and zero carbon cost; the paper obtains an FPTAS through a reduction to preemptive scheduling with rejection penalties.The passage also states hardness when outsourcing costs are proportional to processing times.Source: §3 · p. 8

3.1 Reduction to the penalty variant

• The reduction assigns each original job its effective release and deadline and outsourcing cost as its rejection penalty, then adds dummy jobs for carbon-cost intervals.The dummy jobs have total processing length equal to the interval and subset sums covering every integer length, so rejected dummy work can represent edge capacity and its carbon cost.Source: §3.1 · pp. 8–9

3.2 Proof of correctness

• The constructed penalty instance has the same optimum as the cloud-outsourcing problem, and the backward direction preserves every multiplicative approximation guarantee.Pruhs and Woeginger provide an FPTAS for the penalty problem with arbitrary release times and due dates.Source: §3.1 · p. 8, §3.2 · p. 9

4 Hardness for Multi-edge-server scheduling

• Unless P = NP, two edge servers with free preemption but no migration admit no polynomial-time approximation whose ratio is polynomially bounded in the number of jobs.This holds even for independent jobs with common release and deadline times, shared two-interval strictly positive carbon costs, and guaranteed feasibility.Source: §4 · p. 10
• On a YES-instance of Partition, splitting jobs into two equal-load sets gives total cost 2B, the optimum when all carbon rates are at least one.The construction sets each job’s processing time to its Partition item size, with release time 0 and deadline 2B.Source: §4 · p. 10
• On a NO-instance, one server must receive load at least B + 1, forcing processing in the expensive interval and a cost greater than 2B + L − 1.The construction sets the expensive-interval rate to L; the resulting gap lets a polynomial-time approximation decide Partition.Source: §4 · p. 10

5.1 Experimental Setup

• Synthetic workloads let the experiments control utilization, carbon composition, and flow-network size independently, while Alibaba workloads provide production-derived cases.The setup compares MaxFlow-Passes, MaxFlow-Restart, and MinCostFlow; the exact solvers agree on objective values for every tested instance.Source: §5 · p. 11, §5.1 · p. 11

5.2 Comparison of Exact Solvers

• 4.961×: MinCostFlow requires this average runtime ratio compared with MaxFlow-Passes, which remains faster throughout the tested parameter space.Across configurations, the average ratio ranges from approximately 3.81× to 6.68×.Source: §5.2 · p. 12, Figure 2 · p. 13

5.3 Benefit of Residual Reuse

• 2.069×: restarting requires this average runtime compared with incremental residual reuse, whose advantage is consistent across tested configurations.The green phase contributes 73.85% of final flow on average; brown adds 18.14% and red 8.01%, while at least half of instances need no red-phase flow.Source: §5.3 · pp. 13–14

5.4 Scalability

• MaxFlow-Passes handles networks with tens of millions of job–interval edges, while runtime rises with job count, network density, and edge count.For sparse instances, runtime reaches 843.0 s at 10,000 jobs; at 5,000 jobs, increasing density raises runtime from 188.9 s to 351.2 s.Source: §5.4 · p. 15
• At 1000 sparse jobs, CPU MaxFlow-Passes takes 4.96 s versus 6.34 s of GPU algorithm time and 12.35 s of GPU wall time.Across 1000-job configurations, GPU algorithm time is about 1.28×–1.53× CPU time; residual construction, flow recovery, and repeated GPU invocation remain significant costs.Source: §5.4 · p. 16, Figure 5 · p. 16

5.5 Evaluation on Alibaba Cluster Traces

• On Alibaba trace-derived workloads, MaxFlow-Passes remains faster than MinCostFlow, with the gap reaching approximately 10× on some of the largest networks.Both algorithms agree on feasibility and optimal carbon cost for every tested instance.Source: §5.5 · p. 17, Figure 6 · p. 17

5.6 Cloud-Outsourcing Reduction and Lawler’s Algorithm

• The evaluated configurations outsource approximately 2%–27% of original jobs, and the allocation between edge and cloud varies with scheduling configuration and outsourcing penalties.Lawler’s runtime rises rapidly with original job count, with denser carbon intervals generally requiring more computation; the reduction adds dummy jobs.Source: §5.6 · pp. 17–18, Figure 7 · p. 18

• Optimal strategies handle preemptive single-edge-server scheduling with time-varying costs, general precedence constraints, release times, and deadlines.Source: §6 · p. 18
• Network-flow methods provide a faster and easier way to find optimal solutions than general min-cost-flow methods.Source: §6 · p. 18
• The cloud-outsourcing algorithms build on Lawler and connect edge-versus-cloud decisions to classical weighted-tardiness scheduling.Source: §6 · p. 18
• The algorithm is not yet scalable; fast approximation algorithms for minimizing weighted tardiness remain an interesting direction.Source: §6 · p. 18