AFTD Auto-Formalizing Theoretical Domains

is_oneshot_drf_schedule

def

A rate allocation x and completion time vector C satisfy is_oneshot_drf_schedule I x C for an instance I with D resources if multidim_is_feasible_schedule I x C holds and for every time t ≥ 0 and every job j, x j t equals oneshot_drf_rate I (Finset.univ.filter (fun k => t < C k)) j.

Statement

def is_oneshot_drf_schedule {D : ℕ} (I : MultidimInstance D) (x : Fin I.n → ℝ → ℝ) (C : Fin I.n → ℝ) : Prop
Defined in
arXiv:2611.07905 Tight Worst-Case Completion-Time Bounds for Dominant Resource Fairness, Section 2.2
Verified
08 Nov 2026
Axioms
none listed
Built on 3
  • MultidimInstanceAn instance of multidimensional scheduling with D resource types and zero release times, consisting of a positive number of jobs n with…
  • multidim_is_feasible_scheduleA rate allocation x and completion time vector C satisfy multidim_is_feasible_schedule I x C for an instance I with D resources if for…
  • oneshot_drf_rateFor a multidimensional scheduling instance I with D resources, an active set of jobs A, and a job j, the one-shot DRF rate…
Used by 1
  • oneshot_drf_total_completion_timeThe total completion time oneshot_drf_total_completion_time I of one-shot DRF on an instance I with D resources is defined as the real…

Read back from the Lean

Given a dimension D : ℕ, a multidimensional instance I : MultidimInstance D, a schedule allocation function x : Fin I.n → ℝ → ℝ, and completion times C : Fin I.n → ℝ, is_oneshot_drf_schedule I x C asserts that: 1. (x, C) is a feasible schedule for instance I (multidim_is_feasible_schedule I x C), meaning: - For all jobs j : Fin I.n and all times t : ℝ, 0 ≤ x j t ≤ I.u j. - For all resource dimensions d : Fin D and all times t ≥ 0, the total resource consumption satisfies ∑ j : Fin I.n, I.a j d * x j t ≤ 1. - For all jobs j : Fin I.n, the completion time is non-negative (0 ≤ C j), x j is interval integrable on [0, C j], and the total processed work equals I.p j (∫ t in 0..(C j), x j t = I.p j). 2. At every time t ≥ 0, the rate assigned to every job j : Fin I.n equals its one-shot Dominant Resource Fairness (DRF) rate with respect to the set of jobs active at time t (A(t) = { k : Fin I.n | t < C k }): - If t < C j (job j is still running), x j t = min (I.u j) λ(A(t)), where λ(A(t)) is the fair share rate defined as the real supremum (sSup) of all lam ≥ 0 such that for every resource dimension d : Fin D, ∑ k ∈ A(t), I.a k d * min (I.u k) lam ≤ 1. - If t ≥ C j (job j is completed), x j t = 0.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Predicate that a schedule follows the one-shot DRF allocation rule. -/
def is_oneshot_drf_schedule {D : ℕ} (I : MultidimInstance D) (x : Fin I.n → ℝ → ℝ) (C : Fin I.n → ℝ) : Prop :=
  multidim_is_feasible_schedule I x C ∧
  ∀ (t : ℝ), 0 ≤ t →
    ∀ j, x j t = oneshot_drf_rate I (Finset.univ.filter (fun (k : Fin I.n) => t < C k)) j
See it in the graphDiscuss this resultChallenge it