CONCEPT Cited by 1 source

Common-deadline scheduling¶

Common-deadline scheduling is the problem-class restriction where "all jobs share a common deadline (e.g., all data processing must finish by the nightly batch run)" (Source: sources/2026-02-11-google-scheduling-in-a-changing-world-time-varying-capacity).

Instead of each job carrying its own individual deadline, the entire workload shares a single wall-clock cutoff — the scheduler's only constraint is that whatever work it commits to must all complete by that one shared time. This restriction is load-bearing for online throughput-maximising scheduling with "interrupt without restart" preemption: in the general case, the competitive ratio of any online algorithm approaches zero, but restricting to common deadlines makes "novel constant competitive algorithms" achievable.

Why the restriction helps¶

The adversarial lower bound for interrupt-without-restart is driven by the adversary's ability to mix jobs with different urgency characteristics — forcing the scheduler into commitments that preclude later work. When all jobs share a single deadline, the adversary loses this leverage: the scheduler only has one deadline to miss, not many. That structural simplification is enough to move the competitive-ratio floor from zero to a constant.

Concretely, with a common deadline:

The scheduler knows the total time budget at each point in time (remaining time until the deadline).
A "tentative schedule" over already-arrived jobs can be maintained against that one shared time horizon rather than per-job horizons.
When new jobs arrive, the scheduler decides whether to reshuffle in favour of higher-throughput configurations; the reshuffling algorithm is bounded because there's only one wall-clock boundary to respect.

The 2026-02-11 post describes the unit-capacity variant of the constant-competitive algorithm: "the algorithm maintains a tentative schedule by assigning the jobs that have already arrived to disjoint time intervals. When a new job arrives, the algorithm modifies the tentative schedule by taking the first applicable action out of the following four actions". The four actions themselves are not in the raw capture; the captured fragment covers the algorithm's framing and setup, not its action definitions.

Production motivation¶

The paper names "all data processing must finish by the nightly batch run" as the canonical motivating example. This is the exact shape of the nightly-ETL / nightly-batch pipeline that dominates data-platform workloads:

All Spark jobs for tomorrow's reports must finish by 06:00.
All Airflow DAGs for the analytics dashboard must land by the 08:00 business-day start.
All warehouse ingestion jobs must complete before the downstream BI refresh.

In every case, the individual jobs don't have independent deadlines — they all chase a single shared cutoff driven by the downstream consumer's schedule. The common-deadline model captures this exact production shape.

Contrast: independent deadlines¶

When each job has its own deadline, the scheduling problem is strictly harder — the scheduler must juggle per-job time-budget constraints, and adversarial arrivals can create infeasible deadlines that a common-deadline scheduler would never face. Real production schedulers often sit in a middle ground: a few classes of jobs with class-level deadlines (the nightly batch class all shares 06:00; the interactive class all shares sub-second SLO), rather than strictly per-job deadlines or strictly one global deadline.

The common-deadline restriction is a useful theoretical simplification that captures the nightly-batch shape precisely and delivers constant-competitive bounds; mapping it onto the multi-class production reality is left to the practitioner.

Relationship to EDF¶

Earliest Deadline First (EDF) is the canonical deadline-aware scheduling algorithm — pick the job with the soonest deadline at each decision point. Under common deadlines, EDF degenerates: every job has the same deadline, so EDF's tiebreak rule becomes the whole policy. The 2026-02-11 paper doesn't use EDF as its primitive; it uses a tentative-schedule with four revision actions on arrival. Under common deadlines, the interesting design space is how the scheduler reshuffles the tentative schedule, not which deadline to chase first.

Seen in¶

sources/2026-02-11-google-scheduling-in-a-changing-world-time-varying-capacity — common-deadline restriction lifts the adversarial lower bound for interrupt-without-restart online scheduling from zero-competitive to constant-competitive; the motivating example is "all data processing must finish by the nightly batch run"; the delivered algorithm maintains a tentative schedule revised by four actions on each job arrival (unit-capacity variant — full action list not in raw capture).