is_oneshot_drf_schedule2
A schedule (x, C) satisfies is_oneshot_drf_schedule2 I x C for a two-resource instance I if multidim_is_feasible_schedule2 I x C holds and for every time t ≥ 0 and every job j, x j t equals oneshot_drf_rate2 I applied to the set of jobs k with t < C k.
Statement
def is_oneshot_drf_schedule2 (I : MultidimInstance2) (x : Fin I.n → ℝ → ℝ) (C : Fin I.n → ℝ) : Prop
- Defined in
- arXiv:2611.07905 Sec. 2.2
- Verified
- 08 Nov 2026
- Axioms
- none listed
- Built on 3
- MultidimInstance2An instance of multidimensional scheduling with 2 resource types and zero release times, consisting of a positive number of jobs n with…
- oneshot_drf_rate2For a two-resource multidimensional scheduling instance I, an active set of jobs A, and a job j, the one-shot DRF rate of j is min(u_j,…
- multidim_is_feasible_schedule2A rate allocation x and completion time vector C satisfy multidim_is_feasible_schedule2 I x C if for every job j and time t, 0 ≤ x j t ≤…
- Used by 1
- oneshot_drf_total_completion_time2The total completion time oneshot_drf_total_completion_time2 I of one-shot DRF on a two-resource instance I is defined as sInf { s | ∃ (x…
Read back from the Lean
Given an instance I : MultidimInstance2 (with job count I.n > 0, processing requirements I.p j > 0, peak rates I.u j > 0, and 2-resource consumption matrix I.a j d ∈ [0, 1] with max over d of a j d equal to 1), a rate allocation function x : Fin I.n → ℝ → ℝ, and completion times C : Fin I.n → ℝ,
is_oneshot_drf_schedule2 I x C asserts that (x, C) is a feasible schedule and follows the one-shot Dominant Resource Fairness (DRF) rate allocation for all non-negative times:
1. **Feasibility (multidim_is_feasible_schedule2 I x C)**:
- For all jobs j : Fin I.n and all times t : ℝ, 0 ≤ x j t ≤ I.u j.
- For both resource dimensions d : Fin 2 and all times t ≥ 0, the total resource consumption across all jobs is at most 1: ∑ 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), the rate function x j is interval integrable on [0, C j], and the total processed work equals the requirement: ∫ t in (0 : ℝ)..(C j), x j t = I.p j.
2. **DRF Rate Allocation**:
- For every time t ≥ 0 and every job j : Fin I.n, the rate x j t equals oneshot_drf_rate2 I A(t) j, where A(t) = { k : Fin I.n | t < C k } is the set of active (uncompleted) jobs at time t.
- If j ∈ A(t) (i.e., t < C j), x j t = min (I.u j) λ*(t), where λ*(t) is the supremum (sSup) of all λ ≥ 0 satisfying ∀ d : Fin 2, ∑ k ∈ A(t), I.a k d * min (I.u k) λ ≤ 1.
- If j ∉ A(t) (i.e., t ≥ C j), 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 for a schedule being executed according to one-shot DRF. -/ def is_oneshot_drf_schedule2 (I : MultidimInstance2) (x : Fin I.n → ℝ → ℝ) (C : Fin I.n → ℝ) : Prop := multidim_is_feasible_schedule2 I x C ∧ ∀ (t : ℝ), 0 ≤ t → ∀ j, x j t = oneshot_drf_rate2 I (Finset.univ.filter (fun (k : Fin I.n) => t < C k)) j