[Model] MinimumTardinessSequencing

[isPANN]

Motivation

MINIMUM TARDINESS SEQUENCING (SS2) from Garey & Johnson, Computers and Intractability, Chapter 3, Section 3.2.3, p.73. A classical NP-complete single-machine scheduling problem where unit-length tasks with precedence constraints and deadlines must be scheduled to minimize the number of tardy tasks (tasks that finish after their deadline). Corresponds to the scheduling notation 1|prec, pⱼ=1|∑Uⱼ.

Planned reductions:

• CLIQUE → MinimumTardinessSequencing (Garey & Johnson Theorem 3.10, Section 3.2.3) — the original NP-completeness proof reduces Maximum Clique to this problem by encoding vertices as tasks and edges as deadline-constrained tasks with precedence from their endpoints.

Definition

Name: MinimumTardinessSequencing
Reference: Garey & Johnson, Computers and Intractability, Chapter 3, Section 3.2.3, p.73 (listed as SS2 in appendix)

Mathematical definition:

INSTANCE: A set T of "tasks," each t ∈ T having "length" 1 and a "deadline" d(t) ∈ Z⁺, and a partial order ≺ on T.
OBJECTIVE: Find a "schedule" σ: T → {0,1,...,|T|−1} such that σ(t) ≠ σ(t') whenever t ≠ t', such that σ(t) < σ(t') whenever t ≺ t', that minimizes |{t ∈ T : σ(t)+1 > d(t)}| (the number of tardy tasks).

Formulation: This is an optimization problem (minimize tardy task count), consistent with the MinimumVertexCover / MinimumDominatingSet pattern. The bound K from the original decision version is not part of the instance; instead the solver minimizes the objective directly.

Variables

• Count: |T| variables, one per task.
• Per-variable domain: Each task t is assigned a position σ(t) ∈ {0, 1, ..., |T|−1}.
• dims(): Returns [num_tasks; num_tasks] — each variable takes values in 0..num_tasks. Configurations that are not valid permutations or that violate precedence constraints evaluate to SolutionSize::Invalid. Only bijective, precedence-respecting schedules yield SolutionSize::Valid(tardy_count).
• Meaning: σ(t) is the 0-indexed start time (= finish time − 1) of task t. A task t is tardy if σ(t) + 1 > d(t). The brute-force solver explores all num_tasks^num_tasks configurations; the valid subset is the set of topological sorts of the precedence DAG (at most num_tasks!).

Schema (data type)

Type name: MinimumTardinessSequencing
Variants: No generic parameters needed; a single concrete type.
Traits: OptimizationProblem with type Value = usize, direction() = Minimize, Metric = SolutionSize<usize>.

Field	Type	Description
num_tasks	usize	Number of tasks |T|
deadlines	Vec<usize>	Deadline d(t) for each task t (1-indexed: task finishes at position+1)
precedences	Vec<(usize, usize)>	List of (predecessor, successor) pairs encoding the partial order on T

Size fields: num_tasks() (= |T|), num_precedences() (= number of precedence pairs).

Note: No max_tardy / K field — this is an optimization problem that minimizes tardy count directly.

Complexity

• Best known exact algorithm: Standard subset dynamic programming over the precedence DAG runs in O(2^n · n) time, where n = |T| (see Lawler, Lenstra, Rinnooy Kan, Shmoys, "Sequencing and Scheduling: Algorithms and Complexity," Handbooks in Operations Research and Management Science, Vol. 4, 1993). No faster-than-2^n exact algorithm is known for the general precedence-constrained case (unlike 1|prec|∑Cⱼ where Cygan et al. (2014) achieved O*((2 − ε)^n)).
• declare_variants! complexity string: "2^num_tasks" (subset DP baseline)
• NP-completeness: Garey & Johnson, Theorem 3.10, via reduction from CLIQUE. Remains NP-complete even when the partial order consists only of chains (Lenstra & Rinnooy Kan, 1980).
• Polynomial special cases: K=0 solvable by Lawler (1973); empty precedence solvable by Moore (1968) / Sidney, J.B. (1975), "Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs," Operations Research, 23(2):283–298.
• Parameterized complexity: For the variant without precedences (1||∑wⱼUⱼ), Heeger & Hermelin (ESA 2024) showed W[1]-hardness parameterized by number of distinct processing times or weights alone. No significant FPT results are known for the precedence-constrained version.

Extra Remark

Full book text:

INSTANCE: A set T of "tasks," each t ∈ T having "length" 1 and a "deadline" d(t) ∈ Z+, a partial order < on T, and a non-negative integer K ≤ |T|.
QUESTION: Is there a "schedule" σ: T → {0,1,...,|T|−1} such that σ(t) ≠ σ(t') whenever t ≠ t', such that σ(t) < σ(t') whenever t < t', and such that |{t ∈ T: σ(t)+1 > d(t)}| ≤ K?

Reference: [Garey and Johnson, 1976c]. Transformation from CLIQUE (see Section 3.2.3).

Comment: Remains NP-complete even if all task lengths are 1 and < consists only of "chains" (each task has at most one immediate predecessor and at most one immediate successor) [Lenstra, 1977]. The general problem can be solved in polynomial time if K = 0 [Lawler, 1973], or if < is empty [Moore, 1968] [Sidney, 1973]. The < empty case remains polynomially solvable if "agreeable" release times (i.e., r(t) < r(t') implies d(t) ≤ d(t')) are added [Kise, Ibaraki, and Mine, 1978], but is NP-complete for arbitrary release times (see previous problem).

How to solve

• It can be solved by (existing) bruteforce: enumerate all configurations via dims(), check permutation validity and precedence constraints, count tardy tasks for valid schedules, find the minimum.
• It can be solved by reducing to integer programming. The problem 1|prec,pⱼ=1|∑Uⱼ has a natural ILP formulation: introduce binary variables x_{t,s} (task t starts at time slot s), with precedence constraints (if t ≺ t', then ∑_s s·x_{t,s} < ∑_s s·x_{t',s}), permutation constraints (each task assigned exactly one slot, each slot assigned exactly one task), and objective min ∑_t U_t where U_t = 1 iff σ(t)+1 > d(t). Useful for verification against brute-force.
• Other: N/A

Example Instance

Small instance:

Tasks: T = {t₀, t₁, t₂, t₃, t₄} (5 tasks, unit length each)
Deadlines:

• d(t₀) = 5, d(t₁) = 5, d(t₂) = 5 (vertex-like tasks, very late deadline)
• d(t₃) = 3, d(t₄) = 3 (edge-like tasks, early deadline)

Partial order (precedences):

• t₀ ≺ t₃ (t₀ must precede t₃)
• t₁ ≺ t₃ (t₁ must precede t₃)
• t₁ ≺ t₄ (t₁ must precede t₄)
• t₂ ≺ t₄ (t₂ must precede t₄)

Optimal schedule σ (1 tardy task):

• σ(t₀) = 0 (finish at 1 ≤ d=5 ✓)
• σ(t₁) = 1 (finish at 2 ≤ d=5 ✓)
• σ(t₃) = 2 (finish at 3 ≤ d=3 ✓ — not tardy; t₀ and t₁ scheduled earlier ✓)
• σ(t₂) = 3 (finish at 4 ≤ d=5 ✓)
• σ(t₄) = 4 (finish at 5 > d=3 — TARDY)

Tardy tasks: {t₄}, count = 1. This is optimal: both t₃ and t₄ cannot finish by time 3 simultaneously (they each need 2 predecessors scheduled first, requiring at least 3 tasks in positions 0–2, leaving at most one edge task finishable by deadline 3).

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem, but no planned reduction rules mentioned
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	⚠️ Warn	Core NP-completeness claim is correct, but complexity section lacks a concrete best-known exact algorithm bound
Well-written	❌ Fail	Naming convention violation; complexity section incomplete; variable domain/dims() design unclear

Overall: 1 passed, 2 warnings, 1 failed

---

Usefulness

The problem does not exist in the codebase (pred show MinimumTardinessSequencing returns "Unknown problem"). It is a classical NP-complete scheduling problem from Garey & Johnson (1979), Section 3.2.3. This adds a new problem category (scheduling with precedence constraints) not currently represented.

Warning: The Motivation section mentions no planned reduction rules that this problem would enable or be a target of. Without at least one reduction rule connecting it to the existing graph, this would be an orphan node in the reduction graph. The issue should specify which reductions are planned (e.g., from CLIQUE, as noted in Garey & Johnson's original proof, or to ILP/QUBO).

Non-trivial

This is genuinely distinct from all 24 existing problems. It involves:

• A partial order (DAG) on tasks as precedence constraints
• A permutation (bijective schedule) as the solution space
• A deadline-based tardiness count as the feasibility criterion

No existing problem combines these three structural elements. Pass.

Correctness

NP-completeness claim: Verified. Garey & Johnson (1979) establish NP-completeness of this problem via reduction from CLIQUE (referenced as "Garey and Johnson, 1976c" in the book). The claim that it remains NP-complete even when the partial order consists only of chains (Lenstra, 1977) is consistent with the known literature (Lenstra, Rinnooy Kan, & Brucker, 1977, "Complexity of Machine Scheduling Problems," Annals of Discrete Mathematics).

The polynomial special cases cited (K=0 solvable by Lawler 1973; empty precedence solvable by Moore 1968 / Sidney 1973) are well-known results in scheduling theory and are consistent with the literature.

Warning — Complexity section is vague: The issue states "branch-and-bound or dynamic programming over permutations" with "naive brute-force over all topological sorts runs in O(|T|!) time" but provides no specific best-known exact algorithm with a concrete time bound. The project requires a declare_variants! macro with a precise complexity string (e.g., "2^(1.1996 * num_vertices)" for MIS). A statement like "O(|T|!)" is not useful — every NP-hard problem can be solved in factorial time. The issue should identify whether there is a better exact algorithm (e.g., dynamic programming over subsets in O(2^n * n) time, or parameterized algorithms). Note: Baptiste (1999) showed that 1|p_j=p|sum w_j U_j (equal processing times, no precedence) is solvable in O(n^7), but the precedence-constrained version remains hard.

Recommendation: Search for parameterized or FPT algorithms for this problem. A recent paper (IPEC 2024) studies "Single-machine scheduling to minimize the number of tardy jobs" from a parameterized complexity perspective.

Well-written

Several issues found:

1. Naming convention violation (Fail):
The name MinimumTardinessSequencing uses the "Minimum" prefix, which in this project's conventions indicates an optimization problem (OptimizationProblem trait, Metric = SolutionSize<W>). However, the issue describes a satisfaction/decision problem (QUESTION: Is there a schedule with at most K tardy tasks?), where max_tardy (K) is part of the instance and Metric = bool.

Compare with existing satisfaction problems that do NOT use Minimum/Maximum prefixes: Satisfiability, KSatisfiability, CircuitSAT, KColoring. The problem should either:

• (a) Be renamed to remove the "Minimum" prefix (e.g., TardinessSequencing), keeping it as a satisfaction problem with K in the instance, or
• (b) Be reformulated as an optimization problem (MinimumTardinessSequencing with Metric = SolutionSize<usize>, where the objective is to minimize the number of tardy tasks, and K is removed from the instance).

Option (b) would be more consistent with how MinimumVertexCover and MinimumDominatingSet are implemented in the codebase (they are optimization problems, not decision problems with a bound).

2. Complexity section incomplete (Fail):
No concrete best-known exact algorithm complexity string is provided. The declare_variants! macro requires a precise expression like "num_tasks!" or "2^num_tasks * num_tasks". The issue must specify which algorithm achieves which bound.

3. Variable domain / dims() design unclear (Warn):
The Variables section says each variable takes values in {0, ..., |T|-1} and the assignment must be a bijection. This implies dims() = [|T|; |T|], making the brute-force search space |T|^|T|. However, the valid configurations are only permutations (|T|!), meaning the brute-force solver would waste enormous effort on invalid configurations. The issue should address how dims() and evaluate() will handle this — either by using a permutation-aware representation or by clearly stating that non-permutation configurations return false / Invalid.

4. Minor: "P7" numbering is non-standard:
The issue says "P7 from Garey & Johnson, Chapter 3, Section 3.2.3, p.73." The standard Garey & Johnson numbering uses category codes (SS for Sequencing and Scheduling). This is not a failure, just potentially confusing for readers expecting the standard appendix numbering.

5. All template sections present: Motivation, Definition, Variables, Schema, Complexity, How to solve, Example Instance are all present and substantive. The example is well-worked with both a YES and NO instance.

Recommendations

• Decide between satisfaction vs. optimization formulation and rename accordingly
• Provide a concrete complexity bound for the declare_variants! macro
• Clarify the dims() representation strategy for permutation-based problems
• Add at least one planned reduction rule to the Motivation section to avoid an orphan node
• Consider whether the optimization formulation (minimize number of tardy tasks) would be more useful for reductions

[isPANN]

Issue updated: reformulated as optimization problem (removed K bound), added concrete complexity "2^num_tasks", clarified dims() strategy, added CLIQUE → MinimumTardinessSequencing reduction plan, fixed SS2 numbering.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not in reduction graph; planned CLIQUE reduction connects it
Non-trivial	✅ Pass	Distinct scheduling problem with precedence constraints, deadlines, and permutation feasibility — not isomorphic to any existing model
Correctness	✅ Pass	All references verified; complexity claim is reasonable
Well-written	⚠️ Warn	Minor notation issues; overall well-structured and implementable

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

Pass. MinimumTardinessSequencing does not exist in the codebase (verified via pred show). The 24 currently registered problems contain no scheduling problems at all, making this the first scheduling problem in the reduction graph. The issue identifies a concrete planned reduction (CLIQUE → MinimumTardinessSequencing from Garey & Johnson Theorem 3.10), which connects it to the existing graph. The motivation is concrete: this is a classical NP-complete problem (SS2 in the Garey & Johnson appendix) corresponding to the standard scheduling notation 1|prec, pj=1|∑Uj.

Non-trivial

Pass. This problem has a genuinely different structure from all existing problems:

• The feasibility constraint requires a valid permutation (bijective schedule) that respects a partial order — no existing model has permutation-based feasibility.
• The objective (count of tardy tasks) is distinct from any existing problem's objective.
• The input structure (tasks + deadlines + precedence DAG) is unlike graph, formula, set, or algebraic problems currently in the codebase.
• This would naturally belong in src/models/misc/ given its unique input structure.

Correctness

Pass. All references verified:

• Garey & Johnson (1979), SS2, Theorem 3.10: The book is well-known (garey1979 already in references.bib). The problem definition matches the standard formulation. The NP-completeness via reduction from CLIQUE is a classic result.
• Lenstra & Rinnooy Kan (1980): Verified — "Complexity results for scheduling chains on a single machine," European Journal of Operational Research, Vol. 4(4), pp. 270–275, 1980. Confirms NP-completeness for chain precedence constraints with unit-length tasks. Note: the Garey & Johnson book cites this as "[Lenstra, 1977]" (a technical report); the issue uses the 1980 journal publication, which is preferable.
• Moore (1968): Verified — "An n job, one machine sequencing algorithm for minimizing the number of late jobs," Management Science, 15(1), 102–109, 1968. The Moore-Hodgson algorithm solves 1||∑Uj (no precedence) in O(n log n) time.
• Lawler (1973): Verified — "Optimal sequencing of a single machine subject to precedence constraints," Management Science, 19, 544–546, 1973. Solves precedence-constrained scheduling for certain objectives in polynomial time.
• Heeger & Hermelin (ESA 2024): Verified — "Minimizing the Weighted Number of Tardy Jobs Is W[1]-Hard," ESA 2024, LIPIcs Vol. 308, Article 68 (also arXiv:2401.01740). Confirms W[1]-hardness of 1||∑wjUj parameterized by number of distinct processing times or weights. The issue correctly scopes this to the variant without precedences.
• Complexity string "2^num_tasks": The O(2^n · n) subset DP baseline is standard for NP-hard scheduling problems with precedence constraints. No faster-than-2^n exact algorithm is known for 1|prec,pj=1|∑Uj (unlike 1|prec|∑Cj where Cygan et al. (2014) broke the 2^n barrier). The complexity string drops the polynomial factor, which is consistent with existing declare_variants! conventions in the codebase.

Note: The issue does not provide a specific citation for the "standard subset DP" algorithm. While the O(2^n · n) bound is folklore for this class of problems, a citation to a textbook or survey (e.g., Lawler et al., "Sequencing and Scheduling: Algorithms and Complexity," 1993) would strengthen this claim.

Well-written

Warning — minor issues:

Sections present and substantive: ✅ All required sections (Motivation, Definition/Name/Reference, Variables, Schema, Complexity, How to solve, Example Instance) are present and substantive.

Definition completeness: ✅ The formal definition is precise, with input (tasks, deadlines, partial order), feasibility constraints (bijective schedule respecting precedence), and objective (minimize tardy count) clearly stated.

Example quality: ✅ The example has 5 tasks with non-trivial precedence structure, a fully worked optimal schedule, and a clear explanation of why it is optimal.

Minor issues:

1. Symbol inconsistency in the dims() description: The Variables section says dims() returns [num_tasks; num_tasks] using Rust array-repeat syntax. This is correct but could be clearer — the textual description "each variable takes values in 0..num_tasks" is what matters for implementation, and this is present.
2. Deadline indexing convention: The definition says deadlines are in Z+ (positive integers), and the schema says deadlines are Vec<usize>. The example uses d(t₃) = 3 and checks "finish at 3 ≤ d=3" which is "σ(t)+1 ≤ d(t)". This is consistent, but the schema description should explicitly state the 1-indexed convention (it does: "1-indexed: task finishes at position+1"). ✅
3. No size_fields getter methods listed: The schema table shows num_tasks, deadlines, and precedences as fields, but does not explicitly list what getter methods the type will expose for the overhead system. For the declare_variants! complexity string "2^num_tasks", the getter num_tasks() must exist. This is implied but could be stated explicitly.
4. Sidney (1973) reference not verified: The issue mentions "Sidney (1973)" for the empty-precedence case being polynomially solvable, but does not provide a full citation. This is a minor gap since Moore (1968) already establishes this result.

None of these issues are blocking for implementation.

Recommendations

• Add a textbook citation for the O(2^n · n) subset DP algorithm (e.g., Lawler et al. 1993 survey, or a scheduling textbook).
• Consider whether an ILP formulation is feasible (the "How to solve" section leaves this unchecked) — assignment variables x_{t,s} ∈ {0,1} with precedence and permutation constraints would enable ILP-based solving, which would be useful for verification.
• The Sidney (1973) reference could be expanded to: Sidney, J.B., "Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs," Operations Research, 21(1), 283–298, 1973.