§7, p. 16 — with integer data −w* ≤ w_j ≤ w*, 1 ≤ p_j ≤ p*, every attainable ratio lies in [−w*, w*]
ProvedLawlerWCT.RhoMax.rho_mem_Iccbinary-searchinteger-datap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1ratioscheduling
Let be a finite job set whose weights and processing times are integers satisfying
Then for every nonempty ,
In particular the optimal ratio, the ratio of a ρ-maximal initial set, lies in the interval , which is the starting interval of the binary search.
Formalization Note. The statement bounds the ratio of every nonempty subset of , not only the optimal one, which is a slight generalisation of the paper's sentence; the precedence digraph plays no role and does not appear. The data are integers cast to reals.
Preamble
import Mathlib import Definitions.Def_LawlerWCT_RhoMax_Model
Formal statement
namespace LawlerWCT.RhoMax
theorem rho_mem_Icc {ι : Type*} (N : Finset ι) (w p : ι → ℤ) (wstar pstar : ℤ)
(hw : ∀ j ∈ N, -wstar ≤ w j ∧ w j ≤ wstar) (hpb : ∀ j ∈ N, 1 ≤ p j ∧ p j ≤ pstar) :
∀ I ⊆ N, I.Nonempty →
-(wstar : ℝ) ≤ LawlerWCT.SeriesPar.rho (fun j => (p j : ℝ)) (fun j => (w j : ℝ)) I ∧
LawlerWCT.SeriesPar.rho (fun j => (p j : ℝ)) (fun j => (w j : ℝ)) I ≤ (wstar : ℝ) := 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, sentence "Then surely the optimal value of ρ is contained in the interval [− w*, w*]."
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.