(5.5) — the bound w is a lower bound for Q | pmtn | Cmax
ProvedSchedulingAlgorithms.uniform_pmtn_lower_boundConsider jobs with positive processing requirements sorted as , to be processed preemptively on uniform machines with positive speeds sorted as , where . Let and . Then every feasible preemptive schedule has makespan at least
Here a feasible schedule is a finite list of pieces (job, machine, start, stop) in which no two pieces on one machine overlap, no two pieces of one job overlap, and each job receives total work over its pieces; the makespan is the largest stop time.
This is the bound (5.5) of Section 5.1.2. The term says that all the work has to fit into the total capacity of the machines during . The term says that the longest jobs, which can occupy at most machines at any instant, cannot be processed faster than at the combined rate of the fastest machines.
Formalization Note The sorted orders are hypotheses, Antitone p and Antitone s, because
the formula names the first jobs and machines. Positivity of the speeds makes every
with positive, so no division in is a division by zero; the book's normalisation
is not assumed, since the bound is invariant under scaling all speeds and the book uses
the normalisation only for a running-time estimate. The book's convention that a job is
processed by at most one machine at a time is part of feasibility and is exactly what the
terms rely on.
import Definitions.Def_SchedulingAlgorithms_ParallelMachines
namespace SchedulingAlgorithms
theorem uniform_pmtn_lower_bound {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) (hS : IsFeasible s p S) :
levelBound s p ≤ makespan S := by sorry
end SchedulingAlgorithms
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.