[Model] SequencingToMinimizeTardyTaskWeight

[isPANN]

Important

Build as optimization, not decision. Value = Min<u64>.
Objective: Minimize total weight of tardy tasks Σ wᵢ·Uᵢ.
Do not add a bound/threshold field — let the solver find the optimum directly. See #765.

Motivation

SEQUENCING TO MINIMIZE TARDY TASK WEIGHT (P187) from Garey & Johnson, A5 SS3. A single-machine scheduling problem: given n tasks with processing times, weights, and deadlines, find a schedule that minimizes the total weight of tardy tasks (those finishing after their deadline). This is the weighted generalization of Moore's tardy-tasks problem and is NP-hard by reduction from PARTITION (Karp, 1972). When all tasks share a common deadline, the problem reduces to the KNAPSACK problem. It admits a pseudo-polynomial-time algorithm (Lawler & Moore, 1969) and is thus only weakly NP-hard. No precedence constraints appear in this formulation.

Associated rules:

• R133: Partition → SequencingToMinimizeTardyTaskWeight (as target)
• Direct ILP: SequencingToMinimizeTardyTaskWeight → ILP

Definition

Name: SequencingToMinimizeTardyTaskWeight
Reference: Garey & Johnson, Computers and Intractability, A5 SS3

Mathematical definition:

INSTANCE: Set T of n tasks, for each task t ∈ T a processing time l(t) ∈ Z⁺, a weight w(t) ∈ Z⁺, and a deadline d(t) ∈ Z⁺.

OBJECTIVE: Find a one-processor schedule σ (a permutation of T) that minimizes

Σ_{t ∈ T : σ(t) + l(t) > d(t)} w(t)

where σ(t) is the start time of task t. A task t is tardy if it finishes after its deadline: σ(t) + l(t) > d(t).

The corresponding decision problem (GJ SS3) asks whether a schedule exists with total tardy weight ≤ K for a given bound K ∈ Z⁺.

Variables

• Count: n = |T|. The configuration is a permutation of the n tasks (a scheduling order).
• Per-variable domain: n (each position in the schedule selects a task index 0..n−1)
• Meaning: config[i] = j means task j is scheduled in position i. The schedule is processed left-to-right: the start time of the task in position i equals the sum of processing times of tasks in positions 0..i−1. A configuration is valid if it is a permutation (each task appears exactly once). The evaluate function computes the total weight of tardy tasks.

dims() returns [n; n] (permutation encoding).

Note: Not all configurations in the search space are valid permutations. The evaluate() function returns Min(u64::MAX) for invalid (non-permutation) configurations. The brute-force solver searches all n^n configurations but only n! are valid permutations.

Schema (data type)

Type name: SequencingToMinimizeTardyTaskWeight
Variants: none (no type parameters)

Field	Type	Description	Getter
lengths	Vec<u64>	Processing time l(t) for each task t	num_tasks() → self.lengths.len()
weights	Vec<u64>	Weight w(t) for each task t
deadlines	Vec<u64>	Deadline d(t) for each task t

Problem type: Optimization (minimization)
Value type: Min<u64>

Complexity

• Decision complexity: NP-complete (Karp, 1972; transformation from PARTITION). Weakly NP-hard.
• Best known exact algorithm: Pseudo-polynomial dynamic programming by Lawler & Moore (1969) in O(n · P) time, where n = |T| and P = Σ l(t) is the total processing time. For the unweighted case (all w(t) = 1), Moore's algorithm gives an O(n log n) greedy solution. For the weighted case with "agreeable" weights (w(t) < w(t') implies l(t) ≥ l(t')), Lawler (1976) gives a polynomial algorithm.
• Complexity string for declare_variants!: "factorial(num_tasks)" (brute-force over all permutations; the pseudo-polynomial DP depends on numeric values, not combinatorial size)
• Parameterized complexity: W[1]-hard parameterized by the number of tardy tasks (Heeger & Hermelin, 2024, ESA 2024), ruling out FPT algorithms under standard assumptions.
• References:
  • [Karp, 1972] R. M. Karp, "Reducibility among combinatorial problems", 1972.
  • [Lawler & Moore, 1969] E. L. Lawler and J. M. Moore, "A functional equation and its application to resource allocation and sequencing problems", Management Science, 16(1), 1969.
  • [Lawler, 1976] E. L. Lawler, "Sequencing to minimize the weighted number of tardy jobs", RAIRO, 1976.
  • [Heeger & Hermelin, 2024] K. Heeger and D. Hermelin, "Minimizing tardy processing time on a single machine in near-linear time", ESA 2024. arXiv:2401.01740.

Extra Remark

Full book text:

INSTANCE: Set T of tasks, for each task t in T a length l(t) in Z+, a weight w(t) in Z+, and a deadline d(t) in Z+, and a positive integer K.
QUESTION: Is there a one-processor schedule sigma for T such that the sum of w(t), taken over all t in T for which sigma(t) + l(t) > d(t), does not exceed K?

Reference: [Karp, 1972]. Transformation from PARTITION.

Comment: Can be solved in pseudo-polynomial time (time polynomial in |T| and sum l(t)) [Lawler and Moore, 1969]. Can be solved in polynomial time if weights are "agreeable" (i.e., w(t) < w(t') implies l(t) >= l(t')) [Lawler, 1976c].

Note: The original GJ formulation is a decision problem with bound K. This issue reformulates it as an optimization problem (minimize total tardy weight). The decision version is recovered by checking whether the optimal value ≤ K.

How to solve

• It can be solved by (existing) bruteforce. Enumerate all n! permutations; for each compute start times and total tardy weight; return the minimum.
• It can be solved by reducing to integer programming. Binary ILP with ordering variables x_{ij} (task i in position j), start time variables, tardiness indicators U_t, minimize Σ w_t · U_t.
• Other: Lawler-Moore pseudo-polynomial DP in O(n · Σ l(t)) time.

Example Instance

Input:
T = {t₁, t₂, t₃, t₄, t₅} (n = 5 tasks)
Lengths: l(t₁) = 3, l(t₂) = 2, l(t₃) = 4, l(t₄) = 1, l(t₅) = 2
Weights: w(t₁) = 5, w(t₂) = 3, w(t₃) = 7, w(t₄) = 2, w(t₅) = 4
Deadlines: d(t₁) = 6, d(t₂) = 4, d(t₃) = 10, d(t₄) = 2, d(t₅) = 8

Total processing time = 3 + 2 + 4 + 1 + 2 = 12.

Optimal schedule:
σ: t₄, t₁, t₅, t₃, t₂

Task	Start	Finish	Deadline	Tardy?	Weight
t₄	0	1	2	No	—
t₁	1	4	6	No	—
t₅	4	6	8	No	—
t₃	6	10	10	No	—
t₂	10	12	4	Yes	3

Total tardy weight = 3. Only t₂ (weight 3) is tardy.

Suboptimal feasible solutions (confirming optimality):

1. σ = (t₄, t₂, t₁, t₃, t₅): t₅ tardy (finish 12 > deadline 8), tardy weight = 4
2. σ = (t₁, t₄, t₅, t₃, t₂): t₂ tardy (weight 3) + t₄ tardy (finish 4 > deadline 2, weight 2), tardy weight = 5
3. σ = (t₄, t₂, t₁, t₅, t₃): t₃ tardy (finish 12 > deadline 10), tardy weight = 7
4. σ = (t₁, t₂, t₃, t₄, t₅): t₄ tardy + t₅ tardy, tardy weight = 9

Expected outcome: Min(3)

Reduction Rule Crossref

• R133: Partition → SequencingToMinimizeTardyTaskWeight
• Direct ILP: SequencingToMinimizeTardyTaskWeight → ILP (binary ordering + tardiness indicator formulation)

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	❌ Fail	W[1]-hardness citation wrong year/authors; complexity bound formula inaccurate
Well-written	⚠️ Warn	Minor notation issues; example is good but complexity section needs correction

Overall: 2 passed, 1 failed, 1 warning

---

Usefulness

The problem SequencingToMinimizeTardyTaskWeight does not exist in the current codebase. It is a classic scheduling problem from Garey & Johnson (A5 SS3) and adds a new problem category (single-machine scheduling) to the reduction graph. The motivation mentions a concrete associated rule (Partition → this problem), which would connect it to the existing graph. Pass.

Non-trivial

This is a genuine scheduling problem with a unique feasibility constraint: a configuration must correspond to a valid one-processor schedule where on-time task subsets are consistent with a feasible ordering (total processing time of on-time tasks with deadlines ≤ d must not exceed d for any threshold d). This is structurally distinct from all existing problems in the codebase (graph problems, SAT, set cover, QUBO, ILP, etc.). Pass.

Correctness

Reference verification:

1. Garey & Johnson, A5 SS3 — Confirmed. The problem "Sequencing to Minimize Tardy Task Weight" appears in the Appendix of Computers and Intractability under the Sequencing and Scheduling category. The definition in the issue matches the standard formulation. ✅

2. Karp, 1972 — NP-completeness via reduction from PARTITION — The issue body says "NP-complete by reduction from PARTITION (Karp, 1972)." However, the Garey & Johnson entry itself says "Transformation from PARTITION" and references Karp 1972. This is consistent with G&J. Note that in Karp's original reduction tree, the chain goes Knapsack → Job Sequencing, but the G&J book may use a different reduction. ✅ (consistent with cited source)

3. Lawler & Moore, 1969 — pseudo-polynomial algorithm — Confirmed. The paper "A functional equation and its application to resource allocation and sequencing problems" by Lawler & Moore (1969) in Management Science does provide a pseudo-polynomial DP for this problem. However, the complexity bound stated in the issue is inaccurate: the issue claims O(n * sum l(t) * log(sum w(t))), but the actual complexity is O(n · P) where P = Σ l(t) (total processing time). The log(sum w(t)) factor is not part of the standard bound. ❌

4. Lawler, 1976 — polynomial algorithm for agreeable weights — Confirmed. Lawler showed that when weights are "agreeable" (w(t) < w(t') implies l(t) ≥ l(t')), the problem can be solved in polynomial time. ✅

5. Hermelin et al., 2019 — W[1]-hardness — Incorrect citation. The W[1]-hardness result for 1||Σw_jU_j is from Heeger & Hermelin (2024), published at ESA 2024 (arXiv: 2401.01740, January 2024). The issue cites "Hermelin et al., 2019" which does not match. The authors are Klaus Heeger and Danny Hermelin (not "et al."), and the year is 2024, not 2019. ❌

Verdict: Fail — Two factual errors in the complexity section.

Well-written

4a: Information Completeness — All template sections are present and substantive: Motivation, Definition (Name + Reference + formal definition), Variables, Schema, Complexity, How to solve, Example Instance. ✅

4b: Definition Completeness — The formal definition is taken directly from Garey & Johnson and is precise and implementable. Input structure, feasibility constraints (schedule consistency), and the decision question are all clearly stated. ✅

4c: Symbol and Notation Consistency — Minor issue: the Variables section defines u_t as binary indicators but then notes "the actual decision of which tasks are on-time must be consistent with a valid schedule." This consistency constraint is important but somewhat informally stated. The Schema field names (lengths, weights, deadlines, bound_k) are reasonable but cannot be verified against pred show since the problem doesn't exist yet. ⚠️

4d: Example Quality — The example is excellent: 5 tasks, multiple schedules shown with step-by-step verification, demonstrates both infeasible and feasible orderings, arrives at the correct answer (YES). This is detailed enough for the paper. ✅

Verdict: Warn — Generally well-written with a good example, but the complexity section contains factual errors (covered under Correctness).

Recommendations

• Fix the pseudo-polynomial complexity bound to O(n · P) where P = Σ l(t), per Lawler & Moore (1969).
• Fix the W[1]-hardness citation to Heeger & Hermelin (2024), arXiv:2401.01740, ESA 2024.
• Consider citing the recent improvement by Bringmann et al. (2022) who achieved near-linear time O(P · log P · log n) for the weighted tardy jobs problem via (max,+)-convolutions (arXiv: 2202.06841).

[isPANN]

Implementation note: build as optimization

This model should be implemented as an optimization problem (Value = Min<u64> or similar), not a decision problem with a bound field.

• Objective: Minimize total weight of tardy tasks Σ w_i · U_i where U_i = 1 if task i finishes after its deadline
• Do not add a bound threshold on total tardy weight — let the solver find the optimal sequence directly
• Follows the same pattern as the existing SequencingToMinimizeWeightedTardiness (which already uses Min<usize>)

See #765 for context on the decision-vs-optimization policy.

[isPANN]

Issue Quality Check — Model

Re-check (previous check from 2026-03-12 by @zazabap). Previously: 2 passed, 1 failed, 1 warning. This re-check validates current issue state and adds numerical example verification.

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph; mentions Partition reduction
Non-trivial	✅ Pass	Distinct feasibility constraints and objective from existing scheduling problems
Correctness	❌ Fail	Wrong example optimal value; complexity bound formula inaccurate; W[1]-hardness citation wrong year/authors
Well-written	⚠️ Warn	Schema conflicts with optimization directive; example needs correction

Overall: 2 passed, 1 failed, 1 warning

---

Usefulness

SequencingToMinimizeTardyTaskWeight does not exist in the current codebase (pred show fails). The closest existing problems are:

• SequencingToMinimizeWeightedTardiness — minimizes total weighted tardiness (sum w_j * T_j where T_j = max(0, C_j - d_j)), a continuous tardiness measure
• MinimumTardinessSequencing — unit-length tasks with precedence constraints, minimizes number (not weight) of tardy tasks

The proposed problem minimizes the weighted number of tardy tasks (sum w_j * U_j where U_j is binary), which is a genuinely different objective. The issue mentions a Partition reduction (R133), connecting it to the existing graph. Pass.

Non-trivial

The objective function (minimize weighted count of tardy tasks) is structurally distinct from both existing scheduling problems. The feasibility constraint (schedule consistency: the on-time subset must be achievable by some valid single-machine ordering) is a non-trivial combinatorial constraint that differs from graph, SAT, and set-system problems in the codebase. Pass.

Correctness

Reference verification:

1. Garey & Johnson, A5 SS3 — Confirmed. The problem appears in the G&J appendix under Sequencing and Scheduling. The definition matches. ✅

2. Karp, 1972 — NP-completeness via reduction from PARTITION — Consistent with G&J's statement "Transformation from PARTITION." ✅

3. Lawler & Moore, 1969 — pseudo-polynomial algorithm — The algorithm exists and solves 1||sum w_j U_j in pseudo-polynomial time. However, the complexity bound is wrong: the issue claims O(n * sum l(t) * log(sum w(t))), but the correct bound is O(n * P) where P = sum l(t) (total processing time). The extra log(sum w(t)) factor does not appear in the standard bound. ❌

4. Lawler, 1976 — polynomial algorithm for agreeable weights — Confirmed. ✅

5. Hermelin et al., 2019 — W[1]-hardness — Wrong citation. The correct reference is Heeger & Hermelin (2024), "Minimizing the Weighted Number of Tardy Jobs is W[1]-hard", published at ESA 2024. The authors are Klaus Heeger and Danny Hermelin (two authors, not "et al."), and the year is 2024, not 2019. ❌

6. Example optimal value is wrong. The issue claims the "best schedule" t4, t2, t1, t3, t5 achieves tardy weight 4, presented as the optimal. However, brute-force enumeration of all 120 permutations shows the true optimum is 3, achieved by e.g. the schedule t4, t1, t5, t3, t2 (only t2 is tardy, weight 3). Python verification script output:

   Optimal (minimum) tardy weight: 3
   Optimal schedule: [t4, t1, t5, t3, t2]
     t4: finish=1, deadline=2, on-time
     t1: finish=4, deadline=6, on-time
     t5: finish=6, deadline=8, on-time
     t3: finish=10, deadline=10, on-time
     t2: finish=12, deadline=4, TARDY (weight=3)
   

   The instance has 13 distinct tardy-weight values (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 17), so it is rich enough for testing — but the claimed answer must be corrected. ❌

Verdict: Fail — Three factual errors (complexity bound, W[1]-hardness citation, example optimal value).

Well-written

4a: Information Completeness — All template sections are present. However, the schema includes a bound_k field for the decision version, which conflicts with the implementation note directing Value = Min<u64> (optimization, no bound). The schema needs updating to remove bound_k. ⚠️

4b: Definition Completeness — The formal definition is taken directly from G&J and is precise. However, it describes the decision variant (with threshold K), not the optimization variant required by the implementation note. The definition, variables, and schema should be rewritten to match the optimization formulation. ⚠️

4c: Symbol and Notation Consistency — Symbols are defined and consistent within the decision framing. The variable description correctly notes the schedule-consistency constraint. ✅

4d: Example Quality — The example has 5 tasks and 13 distinct objective values, which is excellent for round-trip testing. However, the claimed optimal value (4) is wrong (true optimum is 3). The example is also framed as a decision problem (asking "is tardy weight <= 5?") rather than optimization ("what is the minimum tardy weight?"). With corrections, the example would be good. ⚠️

Verdict: Warn — The example and schema need updating to match the optimization formulation and correct the optimal value.

Recommendations

• Fix the pseudo-polynomial complexity bound to O(n * P) where P = sum l(t), per Lawler & Moore (1969).
• Fix the W[1]-hardness citation to Heeger & Hermelin (2024), arXiv:2401.01740, ESA 2024.
• Fix the example: the optimal tardy weight is 3 (schedule: t4, t1, t5, t3, t2), not 4.
• Remove the bound_k field from the schema and reframe the definition, variables, and example as an optimization problem (Value = Min<u64>, minimize sum w_t * U_t) per the implementation note.
• Consider citing Hermelin, Molter & Shabtay (2022), "Minimizing the Weighted Number of Tardy Jobs via (max,+)-Convolutions", which achieves O(P * log P * log n) time — an improvement over the classic O(n * P) bound.

[isPANN]

Issue Quality Check — Model (Re-check)

Re-check (previous checks from 2026-03-12 by @zazabap and 2026-03-29 by @isPANN). No changes to the issue body since last check. Previously: 2 passed, 1 failed, 1 warning. Now: same — 2 passed, 1 failed, 1 warning. All previously identified errors remain unfixed.

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph; mentions Partition reduction
Non-trivial	✅ Pass	Distinct feasibility constraints from existing scheduling problems
Correctness	❌ Fail	Wrong example optimal value; complexity bound formula inaccurate; W[1]-hardness citation wrong year/authors
Well-written	⚠️ Warn	Schema conflicts with optimization directive; example needs correction

Overall: 2 passed, 1 failed, 1 warning

Change from previous checks: None. Issue body unchanged; all 3 correctness errors persist.

---

Usefulness

SequencingToMinimizeTardyTaskWeight does not exist in the codebase (pred show fails). The closest existing problems are:

• SequencingToMinimizeWeightedTardiness — minimizes total weighted tardiness (continuous measure, sum w_j * T_j)
• MinimumTardinessSequencing — unit-length tasks with precedence constraints, minimizes number of tardy tasks
• SequencingToMinimizeWeightedCompletionTime, SequencingToMinimizeMaximumCumulativeCost, etc.

The proposed problem minimizes the weighted count of tardy tasks (sum w_j * U_j where U_j is binary), which is a genuinely different objective. The issue mentions a Partition reduction (R133), connecting it to the existing graph. Pass.

Non-trivial

The objective function (minimize weighted count of tardy tasks) is structurally distinct from all existing scheduling problems. The feasibility constraint (the on-time subset must be achievable by some valid single-machine ordering) is a non-trivial combinatorial constraint. Pass.

Correctness

Reference verification:

1. Garey & Johnson, A5 SS3 — Confirmed. The definition in the issue matches the standard formulation. ✅

2. Karp, 1972 — NP-completeness via reduction from PARTITION — Consistent with G&J's statement "Transformation from PARTITION." ✅

3. Lawler & Moore, 1969 — pseudo-polynomial algorithm — The algorithm exists and solves 1||sum w_j U_j in pseudo-polynomial time. However, the complexity bound is wrong: the issue claims O(n * sum l(t) * log(sum w(t))), but the correct bound is O(n * P) where P = sum l(t). The spurious log(sum w(t)) factor does not appear in the standard bound (see Lawler & Moore, 1969). ❌

4. Lawler, 1976 — polynomial algorithm for agreeable weights — Confirmed. ✅

5. Hermelin et al., 2019 — W[1]-hardness — Wrong citation. The correct reference is Heeger & Hermelin (2024), "Minimizing the Weighted Number of Tardy Jobs Is W[1]-Hard", ESA 2024 (arXiv:2401.01740). Two authors (Klaus Heeger, Danny Hermelin), not "et al.", and the year is 2024, not 2019. ❌

6. Example optimal value is wrong. The issue claims the "best schedule" t4, t2, t1, t3, t5 achieves tardy weight 4. Brute-force enumeration of all 120 permutations shows the true optimum is 3, achieved by e.g. t4, t1, t5, t3, t2 (only t2 is tardy, weight 3):

   Optimal (minimum) tardy weight: 3
   Optimal schedule: [t4, t1, t5, t3, t2]
     t4: finish=1, deadline=2, on-time
     t1: finish=4, deadline=6, on-time
     t5: finish=6, deadline=8, on-time
     t3: finish=10, deadline=10, on-time
     t2: finish=12, deadline=4, TARDY (weight=3)
   

   The instance has 13 distinct tardy-weight values, so it is rich enough for round-trip testing — but the claimed answer must be corrected. ❌

Verdict: Fail — Three factual errors (complexity bound, W[1]-hardness citation, example optimal value). All three were identified in previous checks and remain unfixed.

Well-written

4a: Information Completeness — All template sections are present. However, the schema includes a bound_k field for the decision version, which conflicts with the implementation note directing Value = Min<u64> (optimization, no bound). The schema needs updating to remove bound_k. ⚠️

4b: Definition Completeness — The formal definition is taken from G&J and is precise, but describes the decision variant (with threshold K), not the optimization variant required by the implementation note. ⚠️

4c: Symbol and Notation Consistency — Symbols are defined and consistent within the decision framing. ✅

4d: Example Quality — The example has 5 tasks and 13 distinct objective values (excellent for round-trip testing). However: (1) the claimed optimal value (4) is wrong (true optimum is 3), and (2) the example is framed as a decision problem ("is tardy weight <= 5?") rather than optimization ("what is the minimum tardy weight?"). With corrections, the example would be good. ⚠️

Verdict: Warn — Schema and example framing need updating to match optimization directive; example answer needs correction.

Recommendations

• Fix the pseudo-polynomial complexity bound to O(n * P) where P = sum l(t), per Lawler & Moore (1969).
• Fix the W[1]-hardness citation to Heeger & Hermelin (2024), arXiv:2401.01740, ESA 2024.
• Fix the example: the optimal tardy weight is 3 (schedule: t4, t1, t5, t3, t2), not 4.
• Remove the bound_k field from the schema and reframe the definition, variables, and example as an optimization problem (Value = Min<u64>, minimize sum w_t * U_t) per the implementation note.
• Consider citing Hermelin, Molter & Shabtay (2023), "Minimizing the Weighted Number of Tardy Jobs via (max,+)-Convolutions", which improves on the classic O(n * P) bound in certain parameter regimes.

[isPANN]

Fix-issue changelog

• Fixed optimal value: 4 → 3 (schedule: t₄,t₁,t₅,t₃,t₂; verified by brute-force over all 120 permutations)
• Fixed complexity bound: O(n * sum l(t) * log(sum w(t))) → O(n · P) where P = Σ l(t) (per Lawler & Moore 1969)
• Fixed W[1]-hardness citation: "Hermelin et al., 2019" → Heeger & Hermelin (2024), ESA 2024, arXiv:2401.01740
• Removed bound_k field from schema (optimization formulation per Upgrade 17 decision models to optimization versions #765)
• Reformulated Definition as optimization (minimize total tardy weight)
• Added getter methods (num_tasks())
• Added concrete complexity string factorial(num_tasks) for declare_variants!
• Added ILP solvability and direct ILP crossref
• Replaced example with fully verified optimal + 4 suboptimal schedules
• Added permutation-based variable encoding with dims() mapping

Applied by /fix-issue.