P | pmtn | Cmax — the bound LB = max{max_i p_i, (sum_i p_i)/m} is attained
ProvedSchedulingAlgorithms.identical_pmtn_makespanConsider jobs with positive processing times to be processed preemptively on identical machines (all speeds equal to ). Let
Then (i) every feasible preemptive schedule has makespan at least , and (ii) some feasible preemptive schedule has makespan exactly . In other words, is the optimal value of .
Part (i) is the sentence "A lower bound for this problem is LB" on p. 108: no job can finish before its own processing time has elapsed, and the total work cannot exceed times the makespan. Part (ii) is the construction on the same page, McNaughton's wrap-around rule: fill the machines one after another with the jobs in any order, cutting a job in two whenever the current machine reaches time and continuing the remainder on the next machine from time . Because , the two parts of a cut job never overlap in time, which is what makes the resulting schedule feasible.
Formalization Note A feasible schedule is a finite list of pieces on which no machine and no job is double-booked and every job receives its full processing time; the makespan is the largest stop time. No sorting of the jobs is assumed, since the rule works for any order. The hypothesis is needed for to be defined and is what the definition of takes as an argument; is the book's standing assumption that there are machines at all.
import Definitions.Def_SchedulingAlgorithms_ParallelMachines
namespace SchedulingAlgorithms
theorem identical_pmtn_makespan {n m : ℕ} (hn : 0 < n) (hm : 0 < m)
(p : Fin n → ℝ) (hp : ∀ i, 0 < p i) :
(∀ S : PreemptiveSchedule n m, IsFeasible (fun _ => 1) p S →
mcNaughtonBound hn p m ≤ makespan S) ∧
∃ S : PreemptiveSchedule n m, IsFeasible (fun _ => 1) p S ∧
makespan S = mcNaughtonBound hn p m := by sorry
end SchedulingAlgorithms
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.