Online Scheduling with Processing Slack and Commitments

35 concepts13 papers1 proposal

In resource management and cloud computing, schedulers face a fundamental dilemma: tasks arrive dynamically over time, and the system must decide on the fly which tasks to accept and execute. To maximize throughput or total value, traditional online algorithms rely heavily on flexibility—the ability to defer decisions, preempt running tasks, or cancel jobs if a higher-value request suddenly arrives.

However, real-world service providers operate under a constraint known as commitment. Once a provider accepts a job, they must guarantee its completion. This creates a severe vulnerability against an omniscient adversary. If a scheduler locks itself into a decision too early, the adversary can exploit this by sending a flood of low-value tasks followed immediately by highly valuable ones that the system no longer has the capacity to handle. As shown by Marc Rigter et al. in Optimal Admission Control for Multiclass Queues with Time-Varying Arrival Rates via State Abstraction, environments that lack a temporal buffer force a brutal trade-off where early decisions permanently block future high-value tasks.

To make online throughput maximization mathematically tractable under commitment constraints, researchers rely on a powerful structural concept: processing slack.

The Intuition of Processing Slack

Processing slack (or deadline laxity) means that the time window between a job's arrival and its deadline is strictly larger than the actual processing time required to complete it. Formally, if a job requires processing time $p$, its available time window is often assumed to be at least $(1 + \epsilon)p$ for some slack parameter $\epsilon > 0$.

Tight Job (No Slack):
|--- Processing Time (p) ---|
|------- Window (p) --------| -> No flexibility. Must start immediately.

Slack-Constrained Job:
|--- Processing Time (p) ---|... Slack Buffer ...|
|----------------- Window (1 + ε)p --------------| -> Flexible execution window.

Without this buffer, online scheduling is notoriously difficult. An adversary can present a sequence of "tight" jobs (where processing time equals the deadline window), forcing immediate execution decisions that disrupt future optimal scheduling. Chris Schwiegelshohn et al. demonstrated in The Power of Migration for Online Slack Scheduling that tight deadlines present the primary bottleneck in online scheduling, where even minor online decisions carry catastrophic downstream consequences.

When slack is present, it acts as a temporal insurance policy. It grants the scheduler the freedom to delay a task, batch requests, or temporarily interleave other urgent jobs without violating its completion guarantees. Yossi Azar et al. leveraged this in Truthful Online Scheduling with Commitments, proving that deadline slackness provides the exact operational flexibility needed to handle preemption and commitments while maintaining constant competitive ratios.

The Timing of Commitment

The core insight of this research direction is that the timing of a commitment fundamentally dictates whether an online algorithm can compete with an offline optimal scheduler.

  1. Commitment at Arrival: Requiring a scheduler to guarantee a job's completion the exact millisecond it arrives is a fundamental bottleneck. The authors of A general framework for handling commitment in online throughput maximization proved that committing at arrival makes it impossible to achieve a bounded competitive ratio. Even substantial job slack cannot compensate for the total lack of future information at the point of admission.
  2. Commitment at Start: If the commitment can be deferred until the moment the job actually begins execution, the problem becomes highly tractable. In a breakthrough result, Kevin Schewior demonstrated in Online Throughput Maximization on Unrelated Machines: Commitment is No Burden that committing at the start of execution does not degrade the optimal competitive ratio compared to models where jobs can be dropped or canceled at will.

This reveals a surprising truth: being locked into a task is not an inherent burden to system efficiency, provided the system can utilize the job's slack to delay the commitment until execution begins.

How It Works: Thresholds and Resource Protection

To convert processing slack into provable performance guarantees, algorithms must treat slack as a finite, shareable resource. Two primary mechanisms make this work:

1. Two-Threshold Admission Control

For weighted throughput maximization—where jobs carry different priorities or financial values—schedulers use multi-threshold strategies. In O(1/ε) is the answer in online weighted throughput maximization, Franziska Eberle designed an optimal $O(1/\epsilon)$-competitive algorithm using a two-threshold admission policy.

The algorithm evaluates incoming jobs based on both their value-to-time ratio and their remaining slack. If a job's value is high enough to clear the first threshold, it is considered for admission; however, it must also clear a second threshold that ensures its execution will not consume too much of the remaining temporal buffer, which would jeopardize already-committed tasks.

2. Strategic Capacity Blocking

To maintain competitiveness against an offline adversary, a scheduler cannot afford to be greedy. If a scheduler accepts every medium-sized job that fits, it gradually exhausts its slack pool.

To prevent this, the algorithm developed by Kevin Schewior intentionally blocks the admission of jobs with similar processing times immediately after accepting a task. This proactive blocking mechanism preserves a "liquidity buffer" of slack within the schedule, ensuring the system retains the capacity to absorb smaller, highly urgent tasks that may arrive later.

This concept is generalized by the Region Algorithm framework introduced by Franziska Eberle et al. in A general framework for handling commitment in online throughput maximization. By dividing the scheduling timeline into distinct geometric regions based on available slack fractions, the framework maps out exactly when a commitment can be safely made without degrading the system's overall competitive performance.

Key Foundational Work

A note on on-line broadcast scheduling with deadlines (2008) — contributed 3 concept elements to this direction.
Truthful Online Scheduling with Commitments (2015) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 12 papers
  2. Version 1 · 2026-10-04 · 9 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_commitment_timing_constraints_a5bdc911,
  title = {commitment timing constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/commitment-timing-constraints/rdr_a5bdc9112c0944cda39c7cbdcb74b43f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_commitment_timing_constraints_a5bdc911_v2,
  title = {commitment timing constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/commitment-timing-constraints/rdr_a5bdc9112c0944cda39c7cbdcb74b43f/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake