is_oneshot_drf_schedule
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