multidim_is_feasible_schedule
A 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 every job j and time t, 0 ≤ x j t ≤ I.u j; for every resource d and nonnegative time t ≥ 0, the total resource demand ∑ j, I.a j d * x j t ≤ 1; and for every job j, 0 ≤ C j, x j is interval integrable with respect to the volume measure on [0, C j], and the interval integral of x j from 0 to C j equals I.p j.
Statement
def multidim_is_feasible_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.1
- Verified
- 08 Nov 2026
- Axioms
- none listed
- Built on 1
- MultidimInstanceAn instance of multidimensional scheduling with D resource types and zero release times, consisting of a positive number of jobs n with…
- Used by 4
- multidim_opt_nonnegThe offline optimal total completion time multidim_opt I of any multidimensional scheduling instance I with D resources is non-negative.
- drf_cap_lower_bound_le_optFor every multidimensional scheduling instance I with D resources and zero release times, the sum over all jobs of processing requirement…
- multidim_optThe offline optimal total completion time multidim_opt I of a multidimensional scheduling instance I with D resources is defined as the…
- is_oneshot_drf_scheduleA rate allocation x and completion time vector C satisfy is_oneshot_drf_schedule I x C for an instance I with D resources if…
Read back from the Lean
Given a natural number D, an instance I : MultidimInstance D, a schedule/rate function x : Fin I.n → ℝ → ℝ, and a vector of completion times C : Fin I.n → ℝ, multidim_is_feasible_schedule I x C asserts that:
1. For every job j : Fin I.n and every time t : ℝ, 0 ≤ x j t and x j t ≤ I.u j.
2. For every resource dimension d : Fin D and every time t : ℝ with 0 ≤ t, the sum over all jobs j : Fin I.n of I.a j d * x j t is at most 1.
3. For every job j : Fin I.n, all of the following hold:
- 0 ≤ C j;
- x j is interval integrable on [0, C j] with respect to the Lebesgue volume measure;
- The interval integral ∫ t in (0 : ℝ)..(C j), x j t equals I.p j.
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
/-- Feasibility predicate for a multidimensional scheduling rate allocation and completion times. -/ def multidim_is_feasible_schedule {D : ℕ} (I : MultidimInstance D) (x : Fin I.n → ℝ → ℝ) (C : Fin I.n → ℝ) : Prop := (∀ j t, 0 ≤ x j t ∧ x j t ≤ I.u j) ∧ (∀ (d : Fin D) (t : ℝ), 0 ≤ t → ∑ j : Fin I.n, I.a j d * x j t ≤ 1) ∧ (∀ j, 0 ≤ C j ∧ IntervalIntegrable (x j) MeasureTheory.volume 0 (C j) ∧ ∫ t in (0 : ℝ)..(C j), x j t = I.p j)