Scheduling Under a Time-Varying Cost Signal

TL;DR — A whole class of systems must place deferrable work against a cost signal that changes over time — electricity spot price, cloud/GPU spot price, grid carbon intensity, network congestion, off-peak DB/batch windows. The design is always the same shape: model each job as (power/size P, duration D, release, deadline), consume a time series you do not produce (observed or forecast), and pick a start s that minimises cost(s) while meeting the deadline. Greedy (cheapest feasible start) beats a FIFO baseline; add a per-hour capacity cap and contention forces an ascending-slack heuristic. The iron law: no free lever — deferring buys lower cost but spends latency/freshness, and capacity caps how much you can ever save.

---

1. Simple explanation

Some work is urgent — a user is waiting, run it now. Other work is deferrable — it must finish by some deadline, but when inside that window is your choice. Training a model tonight, re-encoding a video, a nightly report, charging a battery, a batch ETL: all deferrable.

Now suppose the cost of doing work changes hour by hour. Electricity is cheap at 3am and dear at 6pm. GPU spot prices swing. The grid is dirty when gas plants run and clean when the wind blows. If your work is deferrable and the cost varies, you have a lever: run the work when it is cheap.

Analogy — running the dishwasher on a time-of-use electricity plan. The dishes must be clean by morning (the deadline). Electricity costs more at dinner, less overnight. So you press "delay start" and let it run at 2am. Same dishes, same energy, lower bill — because you moved a deferrable load to a cheaper time. This article is the general engineering of that "delay start" button: a Scheduler service that reads a cost signal and places deferrable jobs to minimise cost without missing deadlines.

Two honest catches the dishwasher makes obvious:

• If you defer too aggressively, someone waits (latency/freshness cost). No free lever.
• If everyone's dishwasher tries to run at the single cheapest hour, the circuit trips (capacity limit). Contention caps the savings.

---

2. Diagram

        ┌────────────────────┐        time series (price / carbon / congestion)
        │  SIGNAL / FORECAST │  ────────────────────────────────────────────┐
        │  service           │   signal[t] for t = now .. horizon            │
        │  (produces signal) │   (observed history + forecast ahead)         │
        └────────────────────┘                                              ▼
                                                     ┌───────────────────────────────┐
   producers ─► ┌───────────────┐   deferrable jobs  │        SCHEDULER service      │
   (users,      │   JOB QUEUE   │ ─────────────────► │  for each job:                │
    cron,       │ (P,D,release, │                    │   feasible = [release ..      │
    pipelines)  │  deadline)    │                    │               deadline − D]   │
                └───────────────┘                    │   pick s* = argmin cost(s)    │
                                                     │   respect per-hour capacity M │
                                                     └───────────────┬───────────────┘
                                                                     │ schedule: job → start hour
                                                                     ▼
                                                       ┌───────────────────────────┐
                                                       │   EXECUTOR / workers      │
                                                       │  run job at hour s*..s*+D  │
                                                       └───────────────────────────┘

   KEY: the Scheduler CONSUMES the signal; it does NOT produce it.
        The signal service (spot-price feed / EIA fuel mix / congestion monitor) is upstream.

---

3. How it works

3.1 Requirements

The scheduler's own decision must be cheap and fast relative to the work it places. Spending 10 minutes to save 2 minutes of cost is a lever pointed the wrong way.

3.2 The deferrable-job model

   job = (P, D, release, deadline)
     P        = power (kW)  or size (GPU-hours, rows)   — the "how big"
     D        = duration in time slots (hours)          — the "how long"
     release  = earliest slot the job may start
     deadline = job must FINISH by this slot
     slack    = deadline − release − D                  — the freedom you have to move it

slack = 0 means the job is pinned (only one feasible start). slack > 0 gives you room to shop for a cheaper hour. slack < 0 is infeasible — reject it. Energy/work is invariant: the job consumes P·D no matter when it runs; only the cost per unit changes with the signal. That invariance is the whole reason moving it is free of "work" and only trades cost against time.

3.3 The signal input (observed or forecast)

The scheduler consumes a time series it does not produce. That separation matters:

   signal[t] for t = now .. now + horizon
     PAST/NOW : observed (measured spot price, measured fuel mix → CI)
     FUTURE   : forecast (predicted price / predicted carbon) — uncertain!

For grid carbon, the signal is built from EIA Open Data API hourly fuel mix per balancing authority, e.g. ISO New England (ISO-NE), via the average-intensity formula (§4); it generalises to PJM, MISO, CAISO, NYISO, ERCOT, SPP. For spot price, it is the market feed. The scheduler treats all of these identically — as signal[t]. Because the future part is a forecast, the scheduler must tolerate the forecast being wrong (see §7).

3.4 The objective

For a single job, pick the feasible start that minimises total cost:

   minimise   cost(s) = Σ_{h=0}^{D-1} P · signal[s + h]
   subject to release ≤ s ≤ deadline − D

Because P·D (the work) is constant across s, minimising cost(s) is purely about landing the D consecutive slots on the cheapest window the deadline allows.

3.5 Greedy placement vs FIFO baseline

   FIFO  (baseline): start at the earliest feasible slot  →  s = release
   GREEDY (policy) : start at the feasible slot minimising cost(s)

FIFO ignores the signal entirely — it is the honest "do nothing clever" control you must beat. Greedy scans the slack + 1 feasible windows and takes the cheapest. For one job, greedy is optimal (it checks every legal start). You report the win as Savings% (§4) against FIFO.

3.6 The capacity extension (contention → ascending-slack)

Real executors have finite capacity: at most M jobs (or M kW) can run in any single hour. Now greedy's "everyone piles into the single cheapest hour" breaks — that hour overflows M. Jobs contend.

   without capacity : each job independently grabs its cheapest window
   with capacity M  : the cheapest hours fill up → later jobs must take 2nd/3rd-cheapest

A good, cheap heuristic is ascending slack (a.k.a. least-slack-first / EDF-flavoured):

   1. sort jobs by slack ASCENDING (tightest deadline first — least freedom)
   2. for each job in that order:
        pick the cheapest feasible window whose every hour still has capacity < M
        decrement remaining capacity for those hours

Intuition: place the least flexible jobs first (they have the fewest options), leaving the flexible jobs to absorb whatever cheap slots remain. This is a heuristic, not provably optimal — the exact version is an integer program / min-cost flow — but it is fast, online-friendly, and close to optimal in practice. Capacity is the ceiling on savings: the more contention, the more jobs are pushed off the cheapest hours, and the smaller the achievable Savings%.

3.7 Where it sits in a larger architecture

   [ Signal/Forecast service ]  produces signal[t]  (spot feed / EIA fuel mix / congestion probe)
              │  (pull hourly, or push on update)
              ▼
   [ Scheduler service ]  ◄──── [ Job queue ]  (producers enqueue deferrable jobs)
              │  decision: job → start hour (fast, ms–s)
              ▼
   [ Executor / worker pool ]  runs jobs at their assigned windows, reports completion
              │
              ▼
   [ Metrics ]  Savings% vs FIFO · deadline-miss rate · decision latency · signal freshness

Clean separation of concerns: the Signal service owns prediction; the Scheduler owns placement; the Executor owns running. The scheduler is stateless-ish and cheap; swap the signal source (carbon ↔ price) without touching placement logic.

---

4. The math

Cost of a start. For a job (P, D, release, deadline) and signal signal[·]:

cost(s) = Σ_{h=0}^{D-1} P · signal[s + h] ,     release ≤ s ≤ deadline − D

Grid carbon signal (one common source). Average intensity from fuel mix:

CI(t) = ( Σ_f gen_f(t)·EF_f ) / ( Σ_f gen_f(t) )      gCO2/kWh
   AR5 EF (gCO2/kWh): COAL 820, GAS 490, OIL 650, NUCLEAR 12,
                      SOLAR 48, HYDRO 24, WIND 11, OTHER ≈ 230

Savings vs FIFO. With s_fifo = release and s_greedy = argmin_s cost(s):

Savings% = (Total_FIFO − Total_greedy) / Total_FIFO × 100

Worked numeric example (carbon as the signal). Job: P = 10 kW, D = 2 h, release = 0, deadline = 4. Slack = 4 − 0 − 2 = 2, feasible s ∈ {0,1,2}. Signal CI (gCO2/kWh) for hours 0–4: [300, 220, 150, 180, 260].

cost(0) = 10·(300 + 220) = 5200 gCO2      ← FIFO (earliest feasible)
cost(1) = 10·(220 + 150) = 3700 gCO2
cost(2) = 10·(150 + 180) = 3300 gCO2      ← GREEDY (cheapest feasible)

Savings% = (5200 − 3300) / 5200 × 100 = 1900 / 5200 × 100 ≈ 36.5%

The energy P·D = 20 kWh is identical for every start — only the cost per kWh (the signal) differs, which is exactly why the lever works.

One CI(t) from a fuel mix. Hour 2 mix (MW) WIND 200, GAS 300, NUCLEAR 500:

CI(2) = (200·11 + 300·490 + 500·12) / 1000 = 155200 / 1000 ≈ 155 gCO2/kWh

Accounting honesty. CI(t) here is an average intensity. A scheduling decision arguably displaces the marginal generator (often gas ≈ 490), whose factor differs — so average-basis Savings% can overstate real avoided emissions. Report the transparent average basis and state the marginal caveat (Electricity Maps / WattTime give marginal signals). Note also lifecycle vs combustion-only factors. When the signal is spot price, the number is exact (money is money) and this caveat disappears — but a "market impact" analogue reappears if your load is large enough to move the price.

---

5. Real code

A runnable Scheduler.schedule(jobs, signal, capacity) service: greedy for one job, ascending-slack under a per-hour capacity cap, with the FIFO baseline for comparison.

"""A cost-aware scheduler for deferrable jobs against a time-varying signal.
The signal (price / carbon / congestion) is CONSUMED, not produced, by this service."""
from __future__ import annotations
from dataclasses import dataclass


@dataclass(frozen=True)
class Job:
    id: str
    P: float          # power/size per slot
    D: int            # duration in slots
    release: int      # earliest start slot
    deadline: int     # must FINISH by this slot (exclusive end)

    @property
    def slack(self) -> int:
        return self.deadline - self.release - self.D     # freedom to move the job

    def feasible_starts(self):
        # start s is feasible iff release <= s and s + D <= deadline
        return range(self.release, self.deadline - self.D + 1)


def cost(job: Job, s: int, signal: list[float]) -> float:
    # same work P*D for every s; only the signal hours differ
    return sum(job.P * signal[s + h] for h in range(job.D))


class Scheduler:
    def fifo_start(self, job: Job) -> int:
        return next(iter(job.feasible_starts()))                       # earliest feasible

    def greedy_start(self, job: Job, signal: list[float]) -> int:
        return min(job.feasible_starts(), key=lambda s: cost(job, s, signal))  # cheapest feasible

    def schedule(self, jobs: list[Job], signal: list[float], capacity: int | None = None) -> dict:
        """Return {job_id: start_slot}.
        No capacity  -> each job independently takes its cheapest feasible window (greedy).
        With capacity M -> ascending-slack heuristic: place tightest-deadline jobs first,
                           taking the cheapest window whose slots still have room (< M)."""
        for j in jobs:                                                 # reject the infeasible
            if j.slack < 0:
                raise ValueError(f"job {j.id} infeasible: slack={j.slack}")

        if capacity is None:
            return {j.id: self.greedy_start(j, signal) for j in jobs}

        used = [0] * len(signal)                                       # jobs running per slot
        placement: dict[str, int] = {}
        for j in sorted(jobs, key=lambda x: x.slack):                  # least slack first
            best_s, best_c = None, float("inf")
            for s in j.feasible_starts():
                if all(used[s + h] < capacity for h in range(j.D)):    # every slot has room
                    c = cost(j, s, signal)
                    if c < best_c:
                        best_s, best_c = s, c
            if best_s is None:
                raise RuntimeError(f"job {j.id}: no capacity-feasible window (raise M or horizon)")
            for h in range(j.D):
                used[best_s + h] += 1                                  # reserve capacity
            placement[j.id] = best_s
        return placement

    def savings_pct(self, jobs: list[Job], signal: list[float], capacity: int | None = None) -> dict:
        greedy = self.schedule(jobs, signal, capacity)
        total_greedy = sum(cost(j, greedy[j.id], signal) for j in jobs)
        total_fifo   = sum(cost(j, self.fifo_start(j), signal) for j in jobs)   # baseline
        return {"total_fifo": round(total_fifo, 2),
                "total_greedy": round(total_greedy, 2),
                "savings_pct": round((total_fifo - total_greedy) / total_fifo * 100, 2)}


if __name__ == "__main__":
    signal = [300, 220, 150, 180, 260, 200]            # gCO2/kWh, hours 0..5
    sched = Scheduler()

    one = [Job("j1", P=10, D=2, release=0, deadline=4)]
    print(sched.schedule(one, signal))                 # {'j1': 2}  -> cheapest window
    print(sched.savings_pct(one, signal))              # ~36.54% vs FIFO

    # Contention: three jobs all want the cheap window; capacity = 1 forces spreading.
    many = [Job("a", 10, 2, 0, 4), Job("b", 10, 2, 0, 6), Job("c", 10, 1, 0, 3)]
    print(sched.schedule(many, signal, capacity=1))    # ascending-slack spreads them out
    print(sched.savings_pct(many, signal, capacity=1)) # savings shrink under the cap

Expected output:

{'j1': 2}
{'total_fifo': 5200, 'total_greedy': 3300, 'savings_pct': 36.54}
{'a': 2, 'c': 1, 'b': 4}
{'total_fifo': 13400, 'total_greedy': 10100, 'savings_pct': 24.63}

The contended case makes the ceiling concrete: with capacity = 1, the three jobs cannot all sit in the single cheapest hour, so total savings fall to 24.6%, below the single-job 36.5%.

---

6. Real-world example — one design, many signals

The exact same service backs very different products by swapping only signal[t]:

Concrete scenario (carbon). A media company re-encodes 500 videos nightly on ISO-NE. Each job: P ≈ 4 kW, D = 3 h, released at 20:00, deadline 08:00 (slack = 9 h). FIFO starts them all at 20:00 (evening gas peak, high CI). The scheduler pulls the EIA-derived CI forecast, spreads jobs across the low-carbon overnight/early-wind hours under a rack capacity cap, and reports ≈30–40% Savings% vs FIFO on the average basis — with the explicit marginal caveat that the real avoided emissions depend on the marginal (often gas) plant, so the honest figure is a range, not a single hero number. Swap the signal to AWS spot price and the identical scheduler now minimises dollars instead of grams — the code does not change.

The no-free-lever reality in this scenario. Pushing all 500 jobs to the single greenest hour is impossible (capacity), and deferring a job to 05:00 means its output is not ready until 08:00 — fine for nightly encodes, fatal for anything a user is waiting on. Cost ⟷ latency ⟷ slack are three corners you cannot all win.

---

7. Interview questions companies actually ask

Q [Google — carbon-aware compute] "Design a carbon-aware batch scheduler. Walk the whole thing."
  A Requirements: accept deferrable jobs (P, D, release, deadline); hard-deadline SLA; fast
    decision (ms–s); consume a carbon signal; fall back to FIFO if the signal is down. Model
    each job with slack = deadline − release − D. Ingest CI(t) from EIA fuel-mix per balancing
    authority (average formula), observed for the past, FORECAST for the future. Objective:
    minimise cost(s) = Σ P·CI(s+h) over feasible starts. Greedy is optimal for one job; under a
    per-hour capacity M, jobs contend, so use ascending-slack (tightest first, cheapest window
    with room). Architecture: Signal service (produces) → Scheduler (places) → Executor (runs) →
    Metrics (Savings% vs FIFO, deadline-miss rate). Report Savings% on the transparent AVERAGE
    basis and state the marginal caveat. Tradeoff: deferring buys carbon savings but spends
    latency/freshness, and capacity caps the achievable savings.

Q [AWS — Spot / EC2] "Design a cost-aware scheduler for Spot instances."
  A Identical shape, signal = spot price time series. Jobs are interruptible/deferrable batch
    work with deadlines. Greedy places each on the cheapest feasible window; capacity = your
    fleet/quota. Extra Spot wrinkle: instances can be RECLAIMED, so add checkpointing and
    treat reclamation as forced rescheduling. Baseline = on-demand run-now; win = $ saved.

Q [datacenter / infra roles] "Why greedy, and when does it stop being optimal?"
  A For a SINGLE job with no contention, greedy checks every feasible start and takes the
    cheapest — provably optimal. It stops being optimal under a per-hour CAPACITY cap: jobs
    compete for the same cheap hours, and locally-greedy choices can block a better global
    assignment. Then it's a min-cost assignment / integer program; ascending-slack is a fast,
    near-optimal heuristic that places least-flexible jobs first.

Q [Google / any] "How do you handle the forecast being WRONG?"
  A The future part of the signal is a forecast, so: (1) re-plan on a rolling horizon as fresh
    observations arrive (MPC-style) instead of committing far ahead; (2) keep slack in reserve
    rather than betting everything on the single predicted-cheapest hour; (3) bound the downside
    — even a wrong forecast rarely does worse than FIFO if you never violate deadlines; (4)
    monitor realised Savings% vs predicted and fall back to FIFO if forecast error blows up.
    Deadlines are HARD (correctness); cost is SOFT (optimisation) — degrade cost, never the SLA.

Q [systems design] "What's the cost/latency/slack tradeoff — the 'no free lever'?"
  A Deferring a job to a cheaper hour lowers cost but RAISES latency/freshness (the result is
    ready later). More slack = more room to save; zero slack = no savings possible. A per-hour
    capacity cap limits how many jobs reach the cheapest hours, so it CAPS total savings. You
    cannot maximise cheap-cost, low-latency, and high-throughput at once — pick the corner the
    product needs (nightly batch: cheap+high-throughput; interactive: low-latency).

Q [infra] "Where does the signal come from, and who owns it?"
  A A separate Signal/Forecast service OWNS prediction; the scheduler only CONSUMES signal[t].
    For carbon: EIA Open Data hourly fuel mix per balancing authority → CI via the average
    formula; generalises to PJM/MISO/CAISO/NYISO/ERCOT/SPP. For price: the market feed. This
    separation lets you swap carbon ↔ price ↔ congestion without touching placement logic.

Q [green/infra] "Average vs marginal carbon — does it change your design or just your report?"
  A Mostly the report, sometimes the signal source. Average CI (EIA) is transparent and
    reproducible but a scheduling decision displaces the MARGINAL generator (often gas ≈490),
    which differs. So I report Savings% on the average basis AND state the marginal caveat, and
    if accuracy matters I feed a marginal signal (Electricity Maps / WattTime) into the SAME
    scheduler. Also flag lifecycle vs combustion-only factors. The placement math is unchanged.

Q [scale] "How do you scale this to millions of jobs?"
  A Scheduling is cheap per job (scan slack+1 windows), so batch it: group jobs by
    release/deadline buckets, vectorise cost(s) over the signal, and shard by time window.
    Capacity assignment becomes a min-cost flow you can solve per shard. The Scheduler is
    near-stateless (state = capacity reservations), so scale it horizontally behind the queue.

---

8. When to use / tradeoffs

   USE a cost-signal scheduler when ALL hold:
     ✓ the work is DEFERRABLE (has slack: deadline − release − D > 0)
     ✓ the cost of doing work VARIES meaningfully over time (price / carbon / congestion)
     ✓ you can OBSERVE or FORECAST that signal over the job's horizon
     ✓ deferring the work is acceptable to the product (no user waiting on it now)
   DON'T bother when:
     ✗ work is latency-critical / interactive (no slack to spend)
     ✗ the signal is flat or unpredictable (nothing to exploit, forecast useless)
     ✗ scheduling overhead > the cost you'd save (lever pointed the wrong way)
   HONEST LIMITS (no free lever):
     • cost ⟷ latency ⟷ slack: cheaper means later; zero slack means zero savings
     • CAPACITY caps savings — contention pushes jobs off the cheapest hours
     • forecasts are wrong — re-plan on a rolling horizon, keep slack, fall back to FIFO
     • carbon numbers are average-basis; marginal is what your decision really displaces
     • deadlines are HARD (never miss); cost is SOFT (optimise) — degrade cost, not correctness

---

9. Summary + related articles

• A class of systems places deferrable work against a time-varying cost signal (price, carbon, congestion, off-peak windows).
• Model each job as (P, D, release, deadline); slack = deadline − release − D is your freedom; work P·D is invariant, only cost-per-unit varies.
• The scheduler consumes a signal (observed + forecast) it does not produce — a separate Signal/Forecast service owns prediction.
• Objective: min cost(s) = Σ P·signal(s+h) over feasible starts; greedy beats the FIFO baseline; report Savings%.
• Add a per-hour capacity cap M → contention → ascending-slack heuristic (tightest deadlines placed first).
• Architecture: Signal service → Scheduler → Executor → Metrics; the scheduler is cheap, fast, and near-stateless.
• No free lever: deferring trades cost for latency/freshness; capacity caps the savings; forecasts are wrong (re-plan, keep slack, fall back to FIFO).
• Carbon numbers are average-basis — report that transparently and state the marginal caveat.

Related: Greedy Scheduling & Interval Selection · Carbon-Aware Scheduling of Flexible Loads · Green Computing Tradeoffs (No Free Lever)

Resources

• Google — carbon-aware computing / time-shifting compute — https://blog.google/inside-google/infrastructure/data-centers-work-harder-sun-shines-wind-blows/
• AWS — EC2 Spot best practices (interruption-tolerant batch) — https://docs.aws.amazon.com/AWSEC2/latest/UserGuide/spot-best-practices.html
• EIA Open Data API (hourly fuel mix by balancing authority) — https://www.eia.gov/opendata/
• Electricity Maps (marginal vs average carbon signals) — https://www.electricitymaps.com/
• WattTime (marginal emissions signal) — https://www.watttime.org/
• Earliest-Deadline-First / least-slack scheduling (real-time systems primer) — https://en.wikipedia.org/wiki/Earliest_deadline_first_scheduling
• Model Predictive Control (rolling-horizon replanning under forecast error) — https://en.wikipedia.org/wiki/Model_predictive_control