§3, p. 6 — fewer than schedules of long assignments
ProvedUnrelatedSched.FixedMachines.long_assignment_countLet be an matrix of positive integer processing times with machines and jobs, let be an integer deadline and . Call an assignment of job to machine long if , and call a partial schedule of long assignments admissible if the long assignments to each machine take at most time in total. Then
- in every admissible schedule of long assignments, every machine carries fewer than long assignments; and
- the number of admissible schedules of long assignments satisfies
The paper's words: "No machine can handle or more long assignments before time . Thus, for any instance there are less than schedules of long assignments." The count is what bounds the number of linear programs the procedure solves, and hence its running time for fixed and .
Formalization Note The exponent is a real number and the power is the real power Real.rpow; it is not rounded. The hypotheses and are needed for the strict inequality: for there is exactly one (empty) schedule and . The count is Set.ncard of a subset of a finite type, so it is the honest cardinality.
import Mathlib import Definitions.Def_UnrelatedSched_FixedMachines_LongAssignment
namespace UnrelatedSched.FixedMachines
/-- §3, p. 6: in an admissible schedule of long assignments for `(P, d)` no machine carries
`1/ε` or more long assignments, and (for `n ≥ 1`, `m ≥ 1`) there are fewer than
`(n + 1)^{m/ε}` admissible schedules of long assignments. -/
theorem long_assignment_count {m n : ℕ} (P : Matrix (Fin m) (Fin n) ℕ)
(hP : ∀ i j, 0 < P i j) (ε : ℝ) (hε : 0 < ε) (d : ℕ) (hn : 1 ≤ n) (hm : 1 ≤ m) :
(∀ L, IsAdmissible P ε d L →
∀ i, ((Finset.univ.filter (fun j => L j = some i)).card : ℝ) < 1 / ε) ∧
(({L : Fin n → Option (Fin m) | IsAdmissible P ε d L}.ncard : ℕ) : ℝ) <
((n : ℝ) + 1) ^ ((m : ℝ) / ε) := by sorry
end UnrelatedSched.FixedMachines
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.