Theorem 5.8 — the optimal makespan of Q | pmtn | Cmax is the bound w of (5.5)
ProvedSchedulingAlgorithms.uniform_pmtn_optimal_makespanConsider jobs with positive processing requirements sorted as , to be processed preemptively on uniform machines with positive speeds sorted as , where . With and , let
Then there is a feasible preemptive schedule whose makespan equals and which is optimal: its makespan is at most the makespan of every feasible preemptive schedule. Equivalently, the optimal value of is exactly .
This is Theorem 5.8 stated as a fact about schedules rather than about the level algorithm: the book proves the theorem by showing that the schedule the level algorithm builds — jobs of highest remaining level always assigned to the fastest free machines, ties processed jointly by time-sharing — finishes at time , and that is a lower bound (5.5). The result contains McNaughton's rule for identical machines as the case , where reduces to .
Formalization Note The statement asserts the existence of an optimal schedule and pins its value to ; it does not assert that the level algorithm produces it, since the algorithm is not part of the statement. Feasibility, makespan and are as in the definition file. The sorted orders, the positivity of speeds and requirements, and are the section's standing assumptions on p. 124; the normalisation is not assumed, as the statement is invariant under scaling all speeds.
import Definitions.Def_SchedulingAlgorithms_ParallelMachines
namespace SchedulingAlgorithms
theorem uniform_pmtn_optimal_makespan {n m : ℕ} (hm : 0 < m) (hmn : m ≤ n)
(s : Fin m → ℝ) (hs : ∀ j, 0 < s j) (hs' : Antitone s)
(p : Fin n → ℝ) (hp : ∀ i, 0 < p i) (hp' : Antitone p) :
∃ S : PreemptiveSchedule n m, IsFeasible s p S ∧ makespan S = levelBound s p ∧
∀ S' : PreemptiveSchedule n m, IsFeasible s p S' → makespan S ≤ makespan S' := by sorry
end SchedulingAlgorithms
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.