Theorem 5.7 — P | pmtn | sum w_i C_i has an optimal schedule without preemption
ProvedSchedulingAlgorithms.identical_pmtn_weighted_completion_nonpreemptiveConsider jobs with positive processing times and nonnegative weights , to be processed on identical machines, preemption allowed, with the objective where is the completion time of job (the stop time of its last piece). Then there is a feasible schedule without preemption — every job processed in a single uninterrupted piece on a single machine — whose objective value is at most that of every feasible preemptive schedule.
This is Theorem 5.7. Its point is that allowing preemption does not lower the optimal total weighted completion time on identical machines, so has the same optimum as ; the book uses it on p. 121 to conclude that the nonincreasing-weight schedule that is optimal for remains optimal when preemption is allowed. The proof takes an optimal preemptive schedule with the fewest preemption times and removes the preemptions at its last preemption time by exchanging tails of machine schedules, without increasing the objective.
Formalization Note The statement asserts existence of an optimal schedule, and that it is nonpreemptive, in one existential, so it is not vacuous if the optimum were not attained; that an optimum exists at all is part of what is claimed. Nonnegative weights are the book's standing convention for on parallel machines (a negative weight would make the objective unbounded below, and no optimal schedule would exist); positive processing times are its convention for jobs. The competitor class is every feasible preemptive schedule in the sense of the definition file, with any finite number of pieces.
import Definitions.Def_SchedulingAlgorithms_ParallelMachines
namespace SchedulingAlgorithms
theorem identical_pmtn_weighted_completion_nonpreemptive {n m : ℕ} (hm : 0 < m)
(p w : Fin n → ℝ) (hp : ∀ i, 0 < p i) (hw : ∀ i, 0 ≤ w i) :
∃ S : PreemptiveSchedule n m, IsFeasible (fun _ => 1) p S ∧ Nonpreemptive S ∧
∀ S' : PreemptiveSchedule n m, IsFeasible (fun _ => 1) p S' →
totalWeightedCompletionOf w S ≤ totalWeightedCompletionOf w S' := by sorry
end SchedulingAlgorithms
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.