§4: reduction of to
ProvedTwoAgentSched.reductionalgorithm-analysisschedulingtwo-agent-scheduling
Let all processing times be nonnegative and all cost functions nondecreasing on . With the combined costs of the reduction ( on A-jobs; or on a B-job according as or ), let be a feasible schedule minimizing
over all feasible schedules, with optimal value . In the paper's words: "With these positions, if a feasible schedule exists solving with finite objective function value , then is also feasible and optimal for , and achieves the same optimal objective function value . Otherwise, if , then no feasible solution exists for the two-agents problem."
- If , then satisfies , its is at most that of every feasible schedule satisfying , and .
- If , no feasible schedule satisfies .
The reduction turns the two-agent problem into the classical single-agent problem solved by Lawler's algorithm.
Differences from the source:
- reading: σ* solving 1|prec|f_max → S* a feasible start-time schedule minimizing combMax over all feasible schedules, with no precedence constraints; reason: the reduction introduces no precedence constraints among J^A ∪ J^B; optimality is over all feasible schedules, as in problem CP
- reading: finite objective function value f*_max → combMax < ⊤; reason: for n_A ≥ 1 the value is never −∞, so < ⊤ is finiteness; for n_A = 0 a feasible optimum has value −∞ = f^A_max, which the paper's finite/∞ dichotomy places on the feasible side
- encoding: f_i(t) defined for t ≥ 0 → fComb defined for every real t; reason: only completion times of feasible schedules, which are ≥ 0, are evaluated
- generalization: processing times p^A_h, p^B_k of jobs (positive in scheduling practice) → real p ≥ 0 for every job; reason: zero-length jobs are allowed; every instance with positive processing times is an instance
- generalization: each f_i(·) a nondecreasing function of the completion time → each cost function MonotoneOn [0, ∞); reason: completion times are ≥ 0, so values at negative arguments never enter; every nondecreasing function is an instance
- generalization: an integer Q → Q : ℝ; reason: integers are reals; nothing in the argument uses integrality
- encoding: job sets J^A = {J^A_1, …, J^A_{n_A}}, J^B = {J^B_1, …, J^B_{n_B}} → Job nA nB = Fin nA ⊕ Fin nB (A-jobs inl h, B-jobs inr k); reason: Lean convention; same instances
- encoding: a feasible schedule σ, a feasible assignment of starting times on one machine, nonpreemptive, zero release dates → Feasible p S: S j ≥ 0 and, for distinct jobs, S i + p i ≤ S j or S j + p j ≤ S i; completion times S j + p j; reason: the paper's definition written out; zero-length jobs may share a start time
- encoding: f^A_max = max_h f^A_h(C^A_h) → fAmax: Finset.sup in EReal, equal to ⊥ when n_A = 0; reason: for n_A ≥ 1 it is the real maximum; the paper never treats an empty agent
- encoding: f^B_max ≤ Q → BOk: f^B_k(C^B_k) ≤ Q for every B-job k; reason: equivalent for n_B ≥ 1, written without a max so that n_B = 0 needs no convention (the constraint is then empty)
Preamble
import Mathlib import Definitions.Def_TwoAgentSched_Feasible import Definitions.Def_TwoAgentSched_fAmax import Definitions.Def_TwoAgentSched_fComb
Formal statement
namespace TwoAgentSched
/-- **Reduction of `1‖f^A_max : f^B_max` to `1|prec|f_max`** (Agnetis–Mirchandani–Pacciarelli–
Pacifici, Oper. Res. 52(2) (2004), §4, p. 232). With the combined costs `f_i = f^A_i` on A-jobs
and `f_i ∈ {∞, −∞}` on B-jobs according to `f^B_i(t) > Q` or `≤ Q` (`fComb`), let `S*` be a
feasible schedule minimizing `f_max = max_i f_i(C_i)` (`combMax`) over all feasible schedules.
1. If `f_max(S*) < ∞`, then `S*` satisfies `f^B_max ≤ Q`, it is optimal for CP (its `f^A_max`
is at most that of every feasible schedule satisfying `f^B_max ≤ Q`), and
`f^A_max(S*) = f_max(S*)`.
2. If `f_max(S*) = ∞`, no feasible schedule satisfies `f^B_max ≤ Q`. -/
theorem reduction {nA nB : ℕ} (p : Job nA nB → ℝ) (fA : Fin nA → ℝ → ℝ) (fB : Fin nB → ℝ → ℝ)
(Q : ℝ) (hp : ∀ j, 0 ≤ p j) (hfA : ∀ h, MonotoneOn (fA h) (Set.Ici 0))
(hfB : ∀ k, MonotoneOn (fB k) (Set.Ici 0))
(Sstar : Job nA nB → ℝ) (hSstar : Feasible p Sstar)
(hopt : ∀ S, Feasible p S →
combMax fA fB Q (fun j => Sstar j + p j) ≤ combMax fA fB Q (fun j => S j + p j)) :
(combMax fA fB Q (fun j => Sstar j + p j) < ⊤ →
BOk fB Q (fun j => Sstar j + p j) ∧
(∀ S, Feasible p S → BOk fB Q (fun j => S j + p j) →
fAmax fA (fun j => Sstar j + p j) ≤ fAmax fA (fun j => S j + p j)) ∧
fAmax fA (fun j => Sstar j + p j) = combMax fA fB Q (fun j => Sstar j + p j)) ∧
(combMax fA fB Q (fun j => Sstar j + p j) = ⊤ →
¬ ∃ S, Feasible p S ∧ BOk fB Q (fun j => S j + p j)) := by sorry
end TwoAgentSched
Source
Agnetis, Mirchandani, Pacciarelli, Pacifici, Scheduling Problems with Two Competing Agents, Operations Research 52(2) (2004), §4, p. 232 (definition of f_i and the paragraph "With these positions, …")