[Model] MinimumTardinessSequencing (arbitrary-length variant)

[isPANN]

Important

Build as optimization, not decision. Value = Min<usize>.
Objective: Minimize the number of tardy tasks.
Do not add a bound/threshold field — let the solver find the optimum directly. See #765.

This generalizes the existing MinimumTardinessSequencing model (unit-length tasks) to arbitrary task lengths. The existing unit-length model becomes the weight: "One" variant.

Motivation

SEQUENCING TO MINIMIZE TARDY TASKS (P186) from Garey & Johnson, A5 SS2. A single-machine scheduling problem with precedence constraints: given n tasks with arbitrary lengths, deadlines, and a partial order, find a schedule that minimizes the number of tardy tasks (tasks finishing after their deadline). NP-complete by reduction from CLIQUE (Garey & Johnson, 1976). Remains NP-complete even with unit task lengths and chain precedence constraints. Without precedence constraints, it is solvable in polynomial time by Moore's algorithm (1968) for unit lengths and by the Lawler-Moore algorithm for arbitrary lengths.

The existing MinimumTardinessSequencing model only supports unit-length tasks (pj = 1). This issue generalizes it to support arbitrary task lengths using a weight parameter W, where W = One recovers the unit-length variant and W = usize enables arbitrary lengths.

Associated rules:

• R132: Clique → MinimumTardinessSequencing (as target, existing)

Definition

Name: MinimumTardinessSequencing (generalized with weight parameter W)
Reference: Garey & Johnson, Computers and Intractability, A5 SS2

Mathematical definition:

INSTANCE: Set T of n tasks, partial order ≺ on T (precedence constraints), for each task t ∈ T a processing time l(t) ∈ Z⁺ and a deadline d(t) ∈ Z⁺.

OBJECTIVE: Find a one-processor schedule σ (a permutation of T respecting ≺) that minimizes the number of tardy tasks:

|{t ∈ T : C(t) > d(t)}|

where C(t) = σ(t) + l(t) is the completion time of task t, and σ(t) is the start time (sum of processing times of all tasks scheduled before t).

Variants:

• W = One (default): Unit-length tasks (l(t) = 1 for all t). The lengths field is omitted. This is the existing MinimumTardinessSequencing model.
• W = usize: Arbitrary task lengths. The lengths field stores l(t) for each task.

The corresponding decision problem (GJ SS2) asks whether a schedule exists with at most K tardy tasks.

Variables

• Count: n = |T|. The configuration is a permutation of tasks (encoded as Lehmer code, matching the existing implementation).
• Per-variable domain: n − i for position i (Lehmer code: dims() returns [n, n-1, …, 1])
• Meaning: The Lehmer code encodes a permutation of tasks. The evaluate function decodes the permutation, checks precedence constraints, computes completion times using task lengths, and counts tardy tasks.

dims() returns the Lehmer code dimensions (same as existing MinimumTardinessSequencing).

Schema (data type)

Type name: MinimumTardinessSequencing<W>
Variants: W — weight/length type (One for unit-length, usize for arbitrary)

Field	Type	Description	Getter
lengths	Vec<W> (omitted when W = One)	Processing time l(t) for each task	num_tasks() → number of tasks
deadlines	Vec<usize>	Deadline d(t) for each task
precedences	Vec<(usize, usize)>	Precedence pairs (predecessor, successor)	num_precedences()

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

Relationship to existing model: The current MinimumTardinessSequencing (no type parameter) becomes MinimumTardinessSequencing<One>. The num_tasks field is replaced by self.deadlines.len() (or self.lengths.len() for W = usize).

Complexity

• Decision complexity: NP-complete (Garey & Johnson, 1976; transformation from CLIQUE). Remains NP-complete even with unit task lengths and chain precedence constraints.
• Best known exact algorithm:
  • Unit-length (W = One): Brute-force over all permutations. Existing complexity: "2^num_tasks" (Lehmer code encoding).
  • Arbitrary-length (W = usize): Same brute-force approach, "2^num_tasks".
  • Without precedence constraints: Moore's algorithm O(n log n) for unit lengths; Lawler-Moore DP for weighted case.
• References:
  • [Garey & Johnson, 1976] M. R. Garey and D. S. Johnson, "Scheduling tasks with nonuniform deadlines on two processors", JACM 23, 1976.
  • [Moore, 1968] J. M. Moore, "An n job, one machine sequencing algorithm for minimizing the number of late jobs", Management Science 15, 1968.

Extra Remark

Full book text:

INSTANCE: Set T of tasks, partial order < on T, for each task t in T a length l(t) in Z+ and a deadline d(t) in Z+, and a positive integer K <= |T|.
QUESTION: Is there a one-processor schedule sigma for T that obeys the precedence constraints, i.e., such that t < t' implies sigma(t) + l(t) <= sigma(t'), and such that there are at most K tasks t in T for which sigma(t) + l(t) > d(t)?

Reference: [Garey and Johnson, 1976]. Transformation from CLIQUE.
Comment: NP-complete even if l(t) = 1 for all t in T and < is a collection of chains [Garey and Johnson, 1976]. Can be solved in polynomial time if < is empty [Moore, 1968].

How to solve

• It can be solved by (existing) bruteforce. Enumerate all permutations (via Lehmer code), check precedences, compute completion times from task lengths, count tardy tasks, return minimum.
• It can be solved by reducing to integer programming. Binary ILP with ordering variables and tardiness indicators (same approach as existing ILP reduction for the unit-length variant).
• Other: Moore's O(n log n) greedy when precedence is empty and lengths are unit.

Example Instance

Arbitrary-length variant (W = usize)

Input:
T = {t₀, t₁, t₂, t₃, t₄} (n = 5 tasks)
Lengths: l = [3, 2, 2, 1, 2] (total processing time = 10)
Deadlines: d = [4, 3, 8, 3, 6]
Precedences: t₀ ≺ t₂, t₁ ≺ t₃

Optimal schedule (Min(2)):
σ: t₀, t₄, t₂, t₁, t₃

Pos	Task	Length	Start	Finish	Deadline	Tardy?
0	t₀	3	0	3	4	No ✓
1	t₄	2	3	5	6	No ✓
2	t₂	2	5	7	8	No ✓
3	t₁	2	7	9	3	Yes ✗
4	t₃	1	9	10	3	Yes ✗

Tardy tasks: t₁ and t₃ (both have tight deadlines that conflict with precedence). Min(2).

Precedence check: t₀(pos 0) < t₂(pos 2) ✓; t₁(pos 3) < t₃(pos 4) ✓.

Suboptimal schedules:

• Min(3): 16 schedules (e.g., σ = t₀, t₁, t₂, t₃, t₄ → t₁, t₃, t₄ all tardy)
• Min(4): 11 schedules

Out of 30 valid (precedence-respecting) permutations: 3 achieve Min(2), 16 achieve Min(3), 11 achieve Min(4).

Unit-length variant (W = One, existing behavior)

Uses the existing MinimumTardinessSequencing canonical example:
T = {t₀, t₁, t₂, t₃}, deadlines = [2, 3, 1, 4], precedences = [(0, 2)].
Optimal: Min(1) (one tardy task). See existing implementation.

Expected outcome: Min(2) for the arbitrary-length example.

Reduction Rule Crossref

• R132: MaximumClique → MinimumTardinessSequencing (existing, applies to unit-length variant)
• Existing ILP: MinimumTardinessSequencing → ILP (existing, extends naturally to arbitrary lengths)

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; planned incoming reduction from Clique
Non-trivial	✅ Pass	Distinct scheduling problem with precedence constraints and tardiness bound
Correctness	✅ Pass	All references verified: Garey & Johnson 1976/1979, Moore 1968, Lenstra 1977
Well-written	❌ Fail	Example is incoherent: states K=1 in input, fails to find a K=1 schedule, then revises K to 2 mid-example

Overall: 3 passed, 1 failed, 0 warnings

---

Usefulness

SequencingToMinimizeTardyTasks does not exist in the codebase. It is a classical NP-complete scheduling problem (Garey & Johnson A5 SS2) with a planned incoming reduction from Clique (R132). The motivation section clearly explains the problem's significance and its tractability boundary (polynomial without precedence constraints via Moore's algorithm, NP-complete with precedence constraints).

Non-trivial

This problem is genuinely distinct from all existing problems:

• Not SequencingWithReleaseTimesAndDeadlines (issue [Model] SequencingWithReleaseTimesAndDeadlines #494): That problem has release times and asks for feasibility (can all tasks meet their deadlines?). This problem has precedence constraints and asks whether at most K tasks can be tardy.
• Not BinPacking or any other existing problem: The combination of precedence constraints, deadlines, and a bound on tardy task count is a unique problem formulation.

Correctness

Reference verification:

• Garey & Johnson 1979: Confirmed in project bibliography (garey1979). Problem SS2 in the appendix.
• Garey & Johnson 1976c: The NP-completeness of this problem via reduction from Clique is established in the textbook. The specific 1976c reference is to their technical report series, consistent with their publication pattern.
• Moore 1968: Verified -- "An n job, one machine sequencing algorithm for minimizing the number of late jobs," Management Science. The O(n log n) algorithm for the case without precedence constraints is correct and well-established (also known as the Moore-Hodgson algorithm).
• Lenstra 1977: Consistent with the known result that the problem remains NP-complete even with unit task lengths and chain precedence constraints.
• The formal definition matches the Garey & Johnson formulation exactly.

Well-written

Failure: Incoherent example.
The example section is seriously flawed:

1. The Input section specifies K=1, but the author then shows three successive schedule attempts, all failing to achieve K <= 1.
2. Rather than fixing the input, the author changes K to 2 mid-example ("Revised example with K=2").
3. The final working schedule is for K=2, contradicting the original K=1 input specification.
4. The multiple failed attempts left in the issue body make the example confusing and unprofessional.

A correct example should be a single clean instance with a known answer. Either:

• Use K=2 from the start and show a clean feasible schedule, OR
• Design a different instance where K=1 is achievable.

Other items (not failure-level):

• Complexity section lacks a concrete time bound for declare_variants!. For the general case with precedence constraints, a bound like "num_tasks!" (brute-force over permutations) would be needed.
• All other template sections are present and substantive.
• Schema design is reasonable.
• Variable encoding and ILP formulation are correct.

Recommendations

• Rewrite the example with a single clean instance. For K=1 with the given precedences, try: reduce the number of tasks or adjust deadlines so that exactly one tardy task is unavoidable but achievable.
• Add a concrete worst-case complexity string for declare_variants!.

[isPANN]

Implementation note: build as optimization

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

• Objective: Minimize the number of tardy tasks (tasks finishing after their deadline) subject to precedence constraints
• Do not add a bound threshold on tardy task count — let the solver find the optimal sequence directly
• Source rule [Rule] Clique to Sequencing to Minimize Tardy Tasks #470 (Clique → this) can then support richer value mapping

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

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	Problem already exists as MinimumTardinessSequencing
Non-trivial	❌ Fail	Isomorphic to existing MinimumTardinessSequencing (G&J SS2)
Correctness	✅ Pass	All references verified (Garey & Johnson 1979, Moore 1968, Lenstra 1977)
Well-written	❌ Fail	Incoherent example; schema contradicts optimization banner; example answer is suboptimal

Overall: 1 passed, 3 failed, 0 warnings

---

Usefulness

FAIL. The problem MinimumTardinessSequencing already exists in the codebase (see src/models/misc/minimum_tardiness_sequencing.rs). It implements exactly Garey & Johnson SS2:

• Unit-length tasks with precedence constraints and deadlines
• Value = Min<usize> (optimization: minimize tardy task count)
• Fields: num_tasks, deadlines, precedences
• Already has an ILP reduction registered

The proposed SequencingToMinimizeTardyTasks is the same problem under a different name.

The only difference is the issue's schema includes a lengths field for arbitrary task lengths, but:

1. The issue's own example uses all unit lengths
2. The G&J SS2 formulation specifies NP-completeness even for unit lengths
3. If arbitrary lengths are desired, that would be a variant/extension of the existing model, not a new problem

Non-trivial

FAIL. The proposed problem is mathematically identical to the existing MinimumTardinessSequencing:

• Same input: tasks with deadlines + precedence constraints
• Same objective: minimize the number of tardy tasks
• Same feasibility: schedule must respect precedence order
• Same G&J reference (SS2)

Even if we consider the arbitrary-length generalization, it would be a trivial variant of the existing model (adding a lengths field to the existing struct), not a genuinely distinct problem with different feasibility constraints or objective.

Correctness

PASS. All cited references are real and correctly describe the claimed results:

• Garey & Johnson 1979 (already in project bibliography as garey1979): SS2 in the appendix matches the stated formulation
• Moore 1968: The Moore-Hodgson algorithm for the case without precedence constraints is well-established (O(n log n))
• Lenstra 1977: NP-completeness with unit task lengths and chain precedence constraints is a known result

The formal definition accurately reproduces the G&J formulation.

Well-written

FAIL. Multiple issues:

1. Incoherent example. The example starts with K=1, shows three failed schedule attempts, then changes K to 2 mid-section ("Revised example with K=2"). This is confusing and unprofessional. Moreover, K=1 is actually achievable for this instance — the schedule (t_1, t_3, t_5, t_2, t_4, t_6) has only 1 tardy task (verified by exhaustive enumeration over all 180 valid schedules).

2. Suboptimal claimed answer. The issue's final schedule has 2 tardy tasks, but the true optimum for this instance is 1 tardy task. The example fails to demonstrate the correct optimal solution.

3. Schema contradicts optimization banner. The issue banner says "Do not add a bound/threshold field — let the solver find the optimum directly." Yet the schema includes bound_k: u64 ("Maximum allowed number of tardy tasks K"). This is a direct contradiction.

4. Complexity section lacks a concrete expression. The section discusses various special cases but does not provide a concrete complexity string for declare_variants! (e.g., "2^num_tasks" or "factorial(num_tasks)").

Python verification of the example (exhaustive enumeration):

• Total valid schedules (respecting precedences): 180
• Minimum tardy count: 1 (achieved by 18 schedules)
• Issue's claimed schedule: 2 tardy tasks (suboptimal)
• The instance has good round-trip testability (18 optimal, 162 suboptimal solutions)

Recommendations

• Do not implement this issue. Close it as a duplicate of the existing MinimumTardinessSequencing model. If arbitrary task lengths are needed, file a separate enhancement issue to extend the existing model.
• If the contributor wants to contribute, consider adding reductions to or from MinimumTardinessSequencing (e.g., the Clique reduction mentioned in the issue as R132).

[isPANN]

Issue Quality Check — Model (Re-check)

Check	Result	Details
Usefulness	❌ Fail	Problem already exists as MinimumTardinessSequencing in the codebase
Non-trivial	❌ Fail	Isomorphic to existing MinimumTardinessSequencing (G&J SS2)
Correctness	✅ Pass	All references verified (Garey & Johnson 1979, Moore 1968, Lenstra 1977)
Well-written	❌ Fail	Incoherent example; schema contradicts optimization banner; claimed answer is suboptimal

Overall: 1 passed, 3 failed, 0 warnings

Previous check comparison: First check (2026-03-12) found 3 pass / 1 fail (missed the duplicate). Second check (2026-03-29) found 1 pass / 3 fail. This re-check confirms the second check's findings — no changes since the issue body has not been edited.

---

Usefulness

FAIL. The problem MinimumTardinessSequencing already exists in the codebase at src/models/misc/minimum_tardiness_sequencing.rs. It implements exactly Garey & Johnson SS2:

• Unit-length tasks with precedence constraints and deadlines
• Value = Min<usize> (optimization: minimize tardy task count)
• Fields: num_tasks, deadlines, precedences
• Already has an ILP reduction registered (src/rules/minimumtardinesssequencing_ilp.rs)

The proposed SequencingToMinimizeTardyTasks is the same problem under a different name.

The only difference is the issue's schema includes a lengths field for arbitrary task lengths, but: (1) the issue's own example uses all unit lengths, (2) the G&J SS2 formulation specifies NP-completeness even for unit lengths, and (3) if arbitrary lengths are desired, that would be a variant/extension of the existing model, not a new problem.

Non-trivial

FAIL. The proposed problem is mathematically identical to the existing MinimumTardinessSequencing:

• Same input: tasks with deadlines + precedence constraints
• Same objective: minimize the number of tardy tasks
• Same feasibility: schedule must respect precedence order
• Same G&J reference (SS2)

Even if we consider the arbitrary-length generalization, it would be a trivial variant of the existing model (adding a lengths field to the existing struct), not a genuinely distinct problem with different feasibility constraints or objective.

Correctness

PASS. All cited references are real and correctly describe the claimed results:

• Garey & Johnson 1979 (in project bibliography as garey1979): SS2 in the appendix matches the stated formulation
• Moore 1968: The Moore-Hodgson algorithm for the case without precedence constraints is well-established (O(n log n))
• Lenstra 1977: NP-completeness with unit task lengths and chain precedence constraints is a known result
• The formal definition accurately reproduces the G&J formulation

Well-written

FAIL. Multiple issues:

1. Incoherent example. The example starts with K=1, shows three failed schedule attempts, then changes K to 2 mid-section ("Revised example with K=2"). This is confusing and unprofessional.

2. Suboptimal claimed answer. The issue's final schedule has 2 tardy tasks, but exhaustive enumeration over all 180 valid schedules shows the true optimum is 1 tardy task (achieved by 18 schedules). For example, the schedule (t_1, t_3, t_5, t_2, t_4, t_6) has only task t_4 tardy. The issue fails to demonstrate the correct optimal solution.

3. Schema contradicts optimization banner. The issue banner says "Do not add a bound/threshold field — let the solver find the optimum directly." Yet the schema includes bound_k: u64. This is a direct contradiction.

4. Complexity section lacks a concrete expression. No concrete complexity string for declare_variants! is provided.

Python verification summary (exhaustive enumeration):

• Total valid schedules (respecting precedences): 180
• Minimum tardy count: 1 (achieved by 18 schedules)
• Tardy distribution: {1: 18, 2: 126, 3: 36}
• Issue's claimed schedule: 2 tardy tasks (suboptimal)

Recommendations

• Do not implement this issue. Close it as a duplicate of the existing MinimumTardinessSequencing model. If arbitrary task lengths are needed, file a separate enhancement issue to extend the existing model.
• If the contributor wants to contribute, consider adding reductions to or from MinimumTardinessSequencing (e.g., the Clique reduction mentioned as R132).

[isPANN]

Closing as duplicate. The problem already exists as MinimumTardinessSequencing in src/models/misc/minimum_tardiness_sequencing.rs (same GJ SS2 formulation: unit-length tasks, precedence constraints, deadlines, minimize tardy count).

If arbitrary task lengths are needed, that should be proposed as a variant extension to the existing model, not a new problem.

Closed by /fix-issue.