PaperlayerView exact revision on arXiv

Source-linked AI summary

Multidimensional Resource Scheduling with Small Demands

Yossi Azar, Rathish Das, Hao Sun

arXiv:2609.39349v1cs.DS

TL;DR

The paper asks when a resource–time volume bound is approximately achievable despite fragmentation from the resource profiles of concurrently executing jobs. It develops scheduling algorithms for small per-resource demands, including a deterministic online construction based on a fractional schedule. Small demands yield a near-optimal offline algorithm and a deterministic online algorithm with makespan at most 160 OPT.

  • Problem

    The paper asks when a resource–time volume bound is approximately achievable despite fragmentation from the resource profiles of concurrently executing jobs.

    Source: §1 · p. 2

  • Method

    It develops scheduling algorithms for small per-resource demands, including a deterministic online construction based on a fractional schedule.

    Source: §1 · pp. 3–4, §4 · p. 18

  • Results

    Small demands yield a near-optimal offline algorithm and a deterministic online algorithm with makespan at most 160 OPT.

    Source: §1 · pp. 3–4

  • Takeaways & Limitations

    Small demands extend the small-vector phenomenon to temporal resource scheduling with heterogeneous processing times.

    Source: §1 · p. 4

    The online guarantees require every demand coordinate to be at most 1/(4000 log d log T).

    Source: §1 · p. 4, §4 · p. 17

Abstract

from arXiv · show

We study multidimensional resource scheduling. Each job $i$ has a $d$-dimensional resource-demand vector $v_i$ and a processing time $s_i$. The scheduler assigns a start time to each job, subject to the constraint that, at every time, the total demand of the jobs being processed does not exceed $1$ in any resource dimension. The objective is to minimize the makespan. We focus on the regime in which every individual resource demand is small. We ask whether the favorable \emph{small-vector phenomenon} known for multidimensional vector packing, which corresponds to the special case of unit processing times, extends to jobs with heterogeneous processing times. The key difficulty is that arbitrary processing times create temporal interactions across multiple duration scales: a long job may overlap many shorter jobs, while feasibility must be maintained throughout every job's execution interval. We prove that the small-vector phenomenon persists in this temporal setting. For any $0<\epsilon<1/4$, after normalizing the maximum processing time to $1$, if every coordinate of every demand vector is at most $O(\epsilon^2/\log(d/\epsilon))$, we give a randomized offline algorithm that produces a schedule with expected makespan at most $ (1+6\epsilon)\mathrm{OPT}+3$. Thus, sufficiently small resource demands admit asymptotically near-optimal schedules in arbitrary dimension, despite heterogeneous processing times. We also obtain constant competitive ratios in the online setting. Let $T$ denote the ratio between the maximum and minimum processing times. If every coordinate is at most $O(1/(\log d\log T))$, we give a randomized $O(1)$-competitive algorithm, with a competitive ratio independent of both $d$ and $T$. We further derandomize our approach, obtaining a deterministic $O(1)$-competitive algorithm under a comparable smallness assumption.

1 Introduction

The paper asks whether small-vector advantages survive scheduling with heterogeneous durations, where jobs occupy resources across whole intervals and can overlap across scales. It reports near-optimal offline and constant-competitive online algorithms under small-demand conditions.

1 Introduction

  • The offline algorithm runs in O(dn log n) time, nearly linear in the input size.The introduction contrasts this with configuration-based approaches whose polynomial exponent grows rapidly with dimension and accuracy.Source: §1 · p. 4
  • In the small-vector regime, a randomized offline algorithm constructs a schedule whose expected makespan is asymptotically arbitrarily close to optimal, even when dimension d is not constant.Source: §1 · pp. 3–4
  • 96 OPT is the randomized online expected-makespan bound under a small-coordinate condition, with a competitive ratio independent of dimension and job count.Dimension and the processing-time ratio affect only the smallness requirement.Source: §1 · p. 4
  • The deterministic online algorithm achieves makespan at most 160 OPT under a comparable per-coordinate smallness condition.The stated condition is on every coordinate of every job's demand vector.Source: §1 · p. 4

1.1 Techniques

  • The offline method rounds processing times geometrically, places jobs randomly from longer to shorter, and sends jobs that do not fit into an overflow pool.The placement horizon is only slightly longer than the max-coordinate resource–time volume.Source: §1.1 · p. 4
  • Geometric rounding limits failed placements to representative time points, enabling concentration bounds and a union bound across times and resource dimensions.Small coordinates make the probability of overflow tiny; a shelf algorithm schedules overflow jobs while their expected volume keeps the total loss to O(ε).Source: §1.1 · p. 5
  • The online method uses doubling for unknown final volume, a rounded-time grid to control overflow, and a separate online shelf schedule for rejected jobs.Concentration and a union bound over grid points and resource dimensions keep each job's overflow probability sufficiently small.Source: §1.1 · p. 5
  • The deterministic online method uses a fractional distribution over start times and an exponential potential to choose placements that maintain control of resources and time points.For each job, some supported start time does not increase the expected potential.Source: §1.1 · p. 5

2 (1 + ϵ)-Approximation for Offline Vector Scheduling

With maximum processing time normalized to 1, a randomized offline algorithm achieves an expected makespan of at most (1 + 6ε)OPT + 3 when every coordinate is sufficiently small.

2 (1 + ϵ)-Approximation for Offline Vector Scheduling

  • (1 + 6ε)OPT + 3 is the expected makespan bound when each coordinate is at most ε^2/(24log(d/ε)) and 0 < ε < 1/4.The maximum processing time is normalized to 1.Source: §2 · p. 6
  • Rounding processing times increases the optimum by at most a factor of (1 + ε), while the shelf algorithm bounds its added schedule length using max-coordinate volume.For the shelf schedule, the stated bound is (1 + 2δ)dV̂ + 2.Source: §2 · pp. 6, 10
  • The algorithm assigns jobs independently to admissible tentative start times, then sends jobs that do not fit to a rounded-duration shelf schedule.Jobs are considered in nonincreasing processing-time order; overflow durations are rounded up to powers of 2.Source: §2 · pp. 6–7
  • At most 2/ε representative times can witness a failed placement, enabling concentration bounds and union bounds over times and resource dimensions.The probability that a job enters the overflow pool is at most 2ε/d^3.Source: §2 · pp. 7–9
  • The proof bounds the full expected schedule length by (1 + 6ε)OPT + 3 after accounting for the tentative schedule and overflow pool.The final inequality uses ε ≤ 1/4.Source: §2 · p. 10

3 Online with Smaller Vector Size

A randomized online algorithm achieves expected makespan at most 96OPT under a coordinate bound of 1/(100log dlog T), using tentative placements and shelf scheduling for overflow.

3 Online with Smaller Vector Size

  • Each arriving job is tentatively assigned a uniformly chosen admissible start time; jobs that do not fit are scheduled by an online shelf algorithm after the tentative horizon.The algorithm uses a guessed horizon and doubles that guess when it is insufficient.Source: §3 · p. 11
  • For each vector vi, Algorithm 3.1 places it in the overflow pool with probability at most 1/d3; this bound follows by a union bound over d coordinates, each with failure probability at most 1/d4.Source: §3 · pp. 11–12
  • With a sufficiently large guessed horizon, the algorithm has expected length at most 4M, and guessing M increases the competitive ratio by at most a factor of 4.Rounding processing times to powers of 2 increases the optimal makespan by at most a factor of 2.Source: §3 · pp. 10, 13
  • 96OPT is the expected makespan bound when each coordinate is at most 1/(100log dlog T).T is the ratio of maximum to minimum processing times.Source: §3 · p. 13

4 Derandomizing the Algorithm

The section derandomizes the online algorithm by converting a fractional schedule into deterministic placements chosen to control a potential. Under a small-coordinate assumption, the resulting schedule has makespan at most 160OPT.

4 Derandomizing the Algorithm

  • A fractional distribution over start times is rounded by choosing a supported start that does not increase the potential, with vectors that do not fit sent to an overflow pool.The overflow pool is scheduled online with the Shelf algorithm starting at time q.Source: §4 · pp. 13–15
  • The algorithm constructs a 1/2-slack fractional schedule by assigning equal mass to admissible multiples of each rounded processing time in [0, M̄).The resulting fractional schedule has length at most M̄.Source: §4 · pp. 14, 17, 18
  • 160OPT is the deterministic online makespan bound when d ≥ 2 and every input vector’s maximum coordinate is at most 1/(4000 log d log T).The bound is stated relative to OPT before processing-time rounding.Source: §4 · pp. 17, 19

AI Disclosure

The authors used GPT-5.6 Sol solely for English-language polishing, not for technical work.

AI Disclosure

  • GPT-5.6 Sol was used for English-language polishing only, not to develop or verify technical content, arguments, proofs, algorithms, results, or scientific claims.The authors state that all technical contributions and their verification are entirely their work.Source: AI Disclosure · p. 19
Loading 2609.39349v1…