§9, p. 666 — the schedule U∖A → B → A → V∖B is feasible and has value n² − |A|·|B|
ProvedSingleMachinePrec.Biclique.upper_bound_schedulebicliquep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1precedence-constraintsscheduling
Let be an -by- bipartite graph (), its bipartite scheduling instance, and an edge biclique of (, , ). Then a schedule of all jobs of in the block order
exists, and every such schedule is feasible for and has value
This is the upper half of Lemma 9.1: applied to a maximum edge biclique it gives .
Formalization Note The paper writes ; the value is in fact equal to , which is what is stated. Feasibility, which the paper argues from the absence of precedence constraints from to , is part of the conclusion.
Preamble
import Mathlib import Definitions.Def_SingleMachinePrec_Biclique_SG
Formal statement
namespace SingleMachinePrec.Biclique
/-- §9, p. 666 (proof of Lemma 9.1, upper bound). Let `G = (U, V, E)` be an `n`-by-`n` bipartite
graph and `(A, B)` an edge biclique of `G`. A sequence of all the jobs of `S_G` in the order
`U \ A → B → A → V \ B` exists; every such sequence observes the precedence constraints
`P = (U × V) \ E` of `S_G`, and its value is `n² − |A| · |B|`. -/
theorem upper_bound_schedule {U V : Type*} [Fintype U] [Fintype V] [DecidableEq U]
[DecidableEq V] (E : U → V → Prop) (n : ℕ) (hU : Fintype.card U = n)
(hV : Fintype.card V = n) (A : Finset U) (B : Finset V) (hAB : IsEdgeBiclique E A B) :
(∃ l : List (U ⊕ V), InBlockOrder A B l) ∧
∀ l : List (U ⊕ V), InBlockOrder A B l →
LawlerPrec.MinMax.IsFeasible (precSG E) Finset.univ l ∧
valSG l = (n : ℝ) ^ 2 - (A.card : ℝ) * (B.card : ℝ) := by sorry
end SingleMachinePrec.Biclique
Source
Ambühl, Mastrolilli, Mutsanas, Svensson, On the Approximability of Single-Machine Scheduling with Precedence Constraints, Math. Oper. Res. 36(4) (2011), p. 666, §9, proof of Lemma 9.1 (upper bound)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.