Scheduling in a changing world: Maximizing throughput with time-varying capacity

The post presents scheduling algorithms for non-preemptive jobs when cloud capacity changes over time because of failures, maintenance, power limits, or higher-priority workloads. The goal is to maximize completed job value while respecting release times, deadlines, processing durations, and fluctuating parallel capacity. The research establishes the first constant-factor guarantees for several offline and online variants, including a 1/11 competitive ratio for a demanding common-deadline model.

Scheduling with Time-Varying Capacity

• A capacity profile specifies how many jobs can run simultaneously at each point in time.
• Each job has:
  • A release time
  • A hard deadline
  • A processing duration
  • A weight or profit
• Jobs must run continuously once started in the non-preemptive setting.
• If capacity drops during execution, an interrupted job loses its progress.
• The objective is to select and schedule jobs maximizing total completed weight.
• The study considers:
  • Offline scheduling, where future jobs and capacity changes are known.
  • Online scheduling, where jobs arrive dynamically and decisions cannot be reversed.

Offline Scheduling Results

• The optimal problem is NP-hard, so the work focuses on approximation guarantees.
• For unit-profit jobs, an earliest-finish-time Greedy algorithm achieves a 1/2-approximation.
  • It completes at least half as many jobs as an optimal schedule.
  • This matches the classic guarantee for single-capacity scheduling.
• For jobs with different weights, a primal-dual algorithm achieves a 1/4-approximation.

Why Online Non-Preemptive Scheduling Is Difficult

• Online schedulers must commit without knowing future jobs.
• Starting a long job can block many shorter jobs that arrive later.
• Because each completed job may have equal value regardless of duration, one poor decision can sharply reduce throughput.
• Consequently, standard non-preemptive online algorithms have competitive ratios approaching zero.

Interruption with Restarts

• An active job may be interrupted, but its completed work is discarded and the job can be retried later.
• A modified earliest-finish-time Greedy algorithm achieves a 1/2 competitive ratio.
• This means it can guarantee at least half the throughput of an optimal schedule with complete knowledge of future arrivals.

Interruption Without Restarts

• If an interrupted job is permanently discarded, online scheduling becomes substantially harder.
• In general, every online algorithm can be forced into decisions that prevent it from completing much future work.
• The competitive ratio again approaches zero.
• The authors therefore study a practical special case in which all jobs share a common deadline.

A Common-Deadline Algorithm

For a unit-capacity system, the algorithm maintains a tentative schedule of jobs in disjoint time intervals. When a new job arrives, it applies the first suitable action:

1. Place the job in an empty interval.
2. Replace a scheduled future job if the new job is significantly shorter.
3. Interrupt the current job if the new job is shorter than its remaining processing time.
4. Discard the new job.

• The approach balances immediate execution against preserving capacity for shorter future jobs.
• A generalized version works with arbitrary capacity profiles.
• The resulting algorithm achieves the first constant competitive guarantee for this setting: 1/11.

The results suggest that schedulers for volatile cloud environments need controlled interruption and carefully designed replacement policies. Allowing restarts offers strong guarantees, while stricter interruption rules require additional structure—such as a shared deadline—to achieve predictable performance.