(5.8) — jobs fit into an interval of length T iff sum_{i in A} p_i ≤ T h(A) for every set A
ProvedSchedulingAlgorithms.uniform_pmtn_feasible_iffConsider jobs with positive processing requirements sorted as and uniform machines with positive speeds sorted as , and a length . For a set of jobs put
the largest combined speed that jobs can use at one instant. Then the jobs can be scheduled preemptively within the interval — some feasible preemptive schedule has makespan at most — if and only if
This is condition (5.8) of Section 5.1.2, the necessary and sufficient condition the book derives from the level algorithm and then uses in Theorem 5.9 to reduce to a flow problem. Necessity is the counting argument behind (5.5) applied to an arbitrary set of jobs; sufficiency is that (5.8) for the sets says exactly that the bound of (5.5) is at most , and the level algorithm then finishes by time .
Formalization Note The condition is quantified over all subsets , as printed, including (where it reads ) and sets with . Feasibility and makespan are as in the definition file; "within an interval of length " is the requirement that every piece stops by time , which with is the book's meaning. The sorted orders are the section's standing assumptions and are kept, although the displayed condition is symmetric in the jobs. No relation between and is assumed, since the book states (5.8) for arbitrary through the case distinction in .
import Definitions.Def_SchedulingAlgorithms_ParallelMachines
namespace SchedulingAlgorithms
theorem uniform_pmtn_feasible_iff {n m : ℕ} (hm : 0 < m)
(s : Fin m → ℝ) (hs : ∀ j, 0 < s j) (hs' : Antitone s)
(p : Fin n → ℝ) (hp : ∀ i, 0 < p i) (hp' : Antitone p)
(T : ℝ) (hT : 0 ≤ T) :
(∃ S : PreemptiveSchedule n m, IsFeasible s p S ∧ makespan S ≤ T) ↔
∀ A : Finset (Fin n), ∑ i ∈ A, p i ≤ T * speedCapacity s A := by sorry
end SchedulingAlgorithms
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.