p. 402 — branch and bound with the two-machine bound of p. 406 stops at a sequence of least mean completion time
ProvedIgnallSchrage.MeanCompletion.branch_and_bound_optimalLet jobs have arbitrary real processing times on machine and on machine . Run the branch-and-bound procedure of p. 402, ranking nodes by
Then:
- the procedure stops: after some number of steps, the first node of the list is terminal (it has scheduled jobs);
- whenever the first node of the list is terminal, the sequence consisting of followed by its one unscheduled job satisfies
Since is fixed, also minimizes the mean completion time , the paper's objective. This is the correctness of the paper's method for the two-machine mean-completion-time problem.
Formalization Note "The problem is solved: that node's sequence is an optimal one" is read as termination (some ) together with optimality over all permutation sequences. Terminal nodes are those at depth , whose last job is forced, as the paper's example (p. 403) and node counts show. The tie rule is that of p. 403 (a new node precedes old nodes with the same bound); the statement holds for any real data, without a sign condition.
import Mathlib import Definitions.Def_IgnallSchrage_MeanCompletion_LowerBound import Definitions.Def_IgnallSchrage_Makespan_Procedure
namespace IgnallSchrage.MeanCompletion
/-- p. 402, stopping rule, with the two-machine bound of p. 406: for `n ≥ 1` jobs and any real
processing times, (i) the branch-and-bound IgnallSchrage.Makespan.run ranked by `LB(J_r) = Σ_{J_r} d_i + max(T̂_r, Ŝ_r)`
reaches a list whose first node is terminal, and (ii) whenever the first node `P` of the list
is terminal, `P` is the beginning of a full sequence `σ*` (namely `P` followed by its one
IgnallSchrage.Makespan.unscheduled job) whose sum of completion times is at most that of every one of the `n!`
sequences. -/
theorem branch_and_bound_optimal {n : ℕ} (hn : 1 ≤ n) (a b : Fin n → ℝ) :
(∃ k P, (IgnallSchrage.Makespan.run (lowerBound a b) k).head? = some P ∧ IgnallSchrage.Makespan.IsTerminal P) ∧
∀ k P, (IgnallSchrage.Makespan.run (lowerBound a b) k).head? = some P → IgnallSchrage.Makespan.IsTerminal P →
∃ σstar : Equiv.Perm (Fin n), IgnallSchrage.Makespan.BeginsWith σstar P ∧
∀ σ : Equiv.Perm (Fin n), totalCompletion a b σstar ≤ totalCompletion a b σ := by sorry
end IgnallSchrage.MeanCompletion
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.