§7, p. 16, Case 3 — if the best nonempty initial set has zero trial weight, ρ is optimal and I is ρ-maximal
ProvedLawlerWCT.RhoMax.case_3initial-setsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1parametric-searchratioscheduling
Let be an acyclic digraph on a finite job set , with positive processing times and real weights , and let be a real trial value with trial weights . Let be a nonempty initial set of of maximum trial weight among all nonempty initial sets of . If
then and is a ρ-maximal initial set of :
This is the third outcome of a trial value: the trial value equals the optimal ratio, and the maximum-weight initial set found is ρ-maximal.
Formalization Note. As in Case 2, the maximum is over nonempty initial sets: over all initial sets, the empty set would have weight and could be returned without being ρ-maximal.
Preamble
import Mathlib import Definitions.Def_LawlerWCT_RhoMax_Model
Formal statement
namespace LawlerWCT.RhoMax
theorem case_3 {ι : Type*} (N : Finset ι) (G : ι → ι → Prop)
(hGN : ∀ i j, G i j → i ∈ N ∧ j ∈ N) (hacyc : ∀ j, ¬ Relation.TransGen G j j)
(p w : ι → ℝ) (hp : ∀ j ∈ N, 0 < p j) (ρ : ℝ) (I : Finset ι)
(hI : LawlerWCT.SeriesPar.IsInitialSet G N I) (hIne : I.Nonempty)
(hmax : ∀ I', LawlerWCT.SeriesPar.IsInitialSet G N I' → I'.Nonempty → trialWeight p w ρ I' ≤ trialWeight p w ρ I)
(hzero : trialWeight p w ρ I = 0) :
LawlerWCT.SeriesPar.IsRhoMaximal G p w N I ∧ LawlerWCT.SeriesPar.rho p w I = ρ := by sorry
end LawlerWCT.RhoMax
Source
Lawler, Sequencing jobs to minimize total weighted completion time subject to precedence constraints, IRIA-LABORIA Rapport de Recherche No. 205 (Dec. 1976), HAL hal-04716371v1, p. 16, §7, Case 3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.