Remark 1 — under the triangle inequality, d^min_i = d^max_i = δ_ab
ProvedRunwayCPS.DiscreteTime.remark_1p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1runwayschedulingtriangle-inequality
Assume and that the separations satisfy the triangle inequality, for all . Let be a node of at a stage , with penultimate aircraft and final aircraft . Then
So under the triangle inequality the third coordinate of each node is determined, and the modified network of §6.2 reduces to the discrete-time CPS network of §6.1.2.
Formalization Note Only the first sentence of Remark 1 is formalized here; the equivalence with the §6.1.2 network enters through Lemma 4.
Preamble
import Mathlib import Definitions.Def_RunwayCPS_DiscreteTime_ModifiedNetwork
Formal statement
namespace RunwayCPS.DiscreteTime
/-- Remark 1, first sentence (p. 1660): if the separations satisfy the triangle inequality,
then for every node `i` of `G` at a stage `p ≥ 2`, with penultimate and final aircraft `a`
and `b`, `d^min_i = d^max_i = δ_ab`. -/
theorem remark_1 {n : ℕ} [NeZero n] (I : Instance n) (hk : 1 ≤ I.k)
(htri : TriangleIneq I.δ) (p : ℕ) (hp : 2 ≤ p) (i : List (Fin n))
(hi : IsGNode I p i) :
dmin I i = (I.δ (penult i) (RunwayCPS.Makespan.final i) : ℤ) ∧
dmax I p i = (I.δ (penult i) (RunwayCPS.Makespan.final i) : ℤ) := by sorry
end RunwayCPS.DiscreteTime
Source
Balakrishnan & Chandran, Algorithms for Scheduling Runway Operations Under Constrained Position Shifting, Oper. Res. 58(6) (2010), p. 1660, Remark 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.