AFTD Auto-Formalizing Theoretical Domains

multidim_is_feasible_schedule

def

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)
See it in the graphDiscuss this resultChallenge it