MultidimInstance
An instance of multidimensional scheduling with D resource types and zero release times, consisting of a positive number of jobs n with processing requirements p_j > 0, rate caps u_j > 0, and demand vectors a_j in [0, 1]^D such that each entry is in [0, 1] and at least one entry equals 1.
Statement
structure MultidimInstance (D : ℕ)- 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
- Used by 9
- multidim_opt_nonnegThe offline optimal total completion time multidim_opt I of any multidimensional scheduling instance I with D resources is non-negative.
- multidim_instance_existsFor every natural number D ≥ 1, there exists an instance of multidimensional scheduling with D resources.
- 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_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…
- multidim_optThe offline optimal total completion time multidim_opt I of a multidimensional scheduling instance I with D resources is defined as the…
- oneshot_drf_fair_share_rateFor a multidimensional scheduling instance I with D resources and an active set of jobs A, the common fair-share rate…
- 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…
- 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…
- 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…
Read back from the Lean
A structure parameterized by a natural number D, containing: 1. A natural number n, 2. A proof hn that 0 < n, 3. A function p : Fin n → ℝ, 4. A proof hp that for every j : Fin n, 0 < p j, 5. A function u : Fin n → ℝ, 6. A proof hu that for every j : Fin n, 0 < u j, 7. A function a : Fin n → Fin D → ℝ, 8. A proof ha_nonneg that for all j : Fin n and d : Fin D, 0 ≤ a j d, 9. A proof ha_le_one that for all j : Fin n and d : Fin D, a j d ≤ 1, 10. A proof ha_dominant that for every j : Fin n, there exists some d : Fin D such that a j d = 1.
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
/-- An instance of multidimensional scheduling with D resources and zero release times. -/ structure MultidimInstance (D : ℕ) where n : ℕ hn : 0 < n p : Fin n → ℝ hp : ∀ j, 0 < p j u : Fin n → ℝ hu : ∀ j, 0 < u j a : Fin n → Fin D → ℝ ha_nonneg : ∀ j d, 0 ≤ a j d ha_le_one : ∀ j d, a j d ≤ 1 ha_dominant : ∀ j, ∃ d, a j d = 1