Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§3.1, p. 344 — after T_N: no idle time and nondecreasing deadlines, without moving T_N later

Proved
GTWSched.MaxDisc.normalize_after

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

deadlinesnormal-formp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1release-timesschedulingsingle-machine

Let NNN tasks have lengths li≥0l_i \ge 0li​≥0, release times ri≥0r_i \ge 0ri​≥0 and deadlines did_idi​ in special form for α≥0\alpha \ge 0α≥0, indexed so that d0≤d1≤⋯≤dN−1d_0 \le d_1 \le \dots \le d_{N-1}d0​≤d1​≤⋯≤dN−1​, and let TnT_nTn​ be the last task, n=N−1n = N - 1n=N−1. Let (σ,s)(\sigma, s)(σ,s) be an optimum schedule with the release time property with respect to TnT_nTn​. Then there is an optimum schedule (σ′′,s′′)(\sigma'', s'')(σ′′,s′′) such that:

  1. it has the release time property with respect to TnT_nTn​, and TnT_nTn​ occupies the same position as in (σ,s)(\sigma, s)(σ,s);
  2. the tasks before TnT_nTn​ are executed in the same order and at the same times as in (σ,s)(\sigma, s)(σ,s);
  3. TnT_nTn​ starts no later than before, sn′′≤sns''_n \le s_nsn′′​≤sn​, and in fact as early as possible:
sn′′=max⁡(rn, max⁡Ti before Tn(si+li)),s''_n = \max\Big(r_n,\ \max_{T_i \text{ before } T_n} (s_i + l_i)\Big),sn′′​=max(rn​, Ti​ before Tn​max​(si​+li​)),

with the inner maximum 000 when no task precedes TnT_nTn​; 4. the tasks after TnT_nTn​ are executed in increasing order of index (hence of nondecreasing deadline); 5. from the start of TnT_nTn​ on there is no idle time: each later task starts when its predecessor finishes.

These are the transformations by which the paper passes from a schedule given by Corollary 1 to a schedule in standard form.

Formalization Note. Indices are 0-based; the paper's TNT_NTN​ is the index N−1N-1N−1, expressed by a task nnn with n+1=Nn + 1 = Nn+1=N.

Preamble
import Mathlib
import Definitions.Def_GTWSched_MaxDisc_Model
Formal statement
namespace GTWSched.MaxDisc

theorem normalize_after {N : ℕ} (r d l : Fin N → ℝ) (α : ℝ) (hα : 0 ≤ α)
    (hr : ∀ i, 0 ≤ r i) (hl : ∀ i, 0 ≤ l i) (hsf : SpecialForm r d l α)
    (hd : Monotone d) (n : Fin N) (hnlast : n.val + 1 = N)
    (σ : Fin N ≃ Fin N) (s : Fin N → ℝ)
    (hopt : Optimum r d l σ s) (hrtp : ReleaseTimeProperty r σ s n) :
    ∃ (σ' : Fin N ≃ Fin N) (s' : Fin N → ℝ),
      Optimum r d l σ' s' ∧ ReleaseTimeProperty r σ' s' n ∧
      σ'.symm n = σ.symm n ∧
      (∀ p : Fin N, p < σ.symm n → σ' p = σ p ∧ s' (σ p) = s (σ p)) ∧
      s' n ≤ s n ∧
      s' n = max (r n) (⨆ i : {i : Fin N // σ'.symm i < σ'.symm n}, s' i.1 + l i.1) ∧
      (∀ p q : Fin N, σ'.symm n < p → p < q → σ' p < σ' q) ∧
      (∀ p q : Fin N, σ'.symm n ≤ p → q.val = p.val + 1 →
        s' (σ' q) = s' (σ' p) + l (σ' p)) := by sorry

end GTWSched.MaxDisc
Source
Garey, Tarjan & Wilfong, One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties, Math. Oper. Res. 13 (1988), p. 344, paragraph after the proof of COROLLARY 1 ("This immediately implies that there can be no idle time …") and the paragraph before COROLLARY 2 ("The necessary transformations …")
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me