Remark 7.1 — is 1 or at most on incomparable pairs
ProvedSingleMachinePrec.IntervalReduction.remark_7_1interval-ordersp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Let be the Stage 2 instance with parameter . Let and be jobs with intervals and such that . Then
- and ;
- if and are incomparable in , then or ;
- if , then , that is, the interval of lies completely to the left of that of ;
- if , then .
The remark is the bookkeeping behind Claim 2: on incomparable pairs, the weights of split into "heavy" nodes of weight exactly and "light" nodes of weight at most .
Formalization Note The ceilings are integer valued and the powers are integer powers of the real ( is possible for 's left end). The paper takes "large"; the statement assumes , under which parts 3 and 4 hold (at they fail).
Preamble
import Mathlib import Definitions.Def_SingleMachinePrec_IntervalReduction_Instance
Formal statement
namespace SingleMachinePrec.IntervalReduction
/-- Remark 7.1 (p. 662): for jobs `i, j` with intervals `[a, b]` and `[c, d]` and `a ≤ d`,
`p_i ≤ 1/k^⌈b⌉`, `w_j ≤ k^⌈c⌉`; if `i, j` are incomparable then `p_i w_j = 1` or
`p_i w_j ≤ 1/k`; `p_i w_j ≥ k` implies `b < c`; and `p_i w_j = 1` implies `⌈b⌉ = ⌈c⌉`. -/
theorem remark_7_1 {N : ℕ} {G : SimpleGraph (Fin N)} (L : TreeLayout G) (k : ℝ) (hk : 1 < k)
(x y : Job L) (hxy : left L x ≤ right L y) :
procTime L k x ≤ 1 / k ^ ⌈right L x⌉ ∧
weight L k y ≤ k ^ ⌈left L y⌉ ∧
(Incomparable (prec L) x y →
procTime L k x * weight L k y = 1 ∨ procTime L k x * weight L k y ≤ 1 / k) ∧
(k ≤ procTime L k x * weight L k y → right L x < left L y) ∧
(procTime L k x * weight L k y = 1 → ⌈right L x⌉ = ⌈left L y⌉) := by sorry
end SingleMachinePrec.IntervalReduction
Source
Ambühl, Mastrolilli, Mutsanas, Svensson, On the Approximability of Single-Machine Scheduling with Precedence Constraints, Math. Oper. Res. 36(4) (2011), p. 662, Remark 7.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.