[Model] SequencingWithinIntervals

[isPANN]

Motivation

SEQUENCING WITHIN INTERVALS (P5) from Garey & Johnson, Chapter 3, Section 3.2.2, p.70. A canonical NP-complete single-machine scheduling problem: given tasks each with a release time, deadline, and length, can all tasks be non-overlappingly scheduled so that each runs strictly within its allowed window? Its NP-completeness (Theorem 3.8 in GJ) is proved by reduction from PARTITION using an "enforcer" task that pins the schedule at the midpoint of the time horizon, forcing a balanced split. This is historically significant as one of the first NP-completeness results for single-machine scheduling.

Planned reductions: (1) Partition → SequencingWithinIntervals (implementing the NP-completeness reduction from GJ Theorem 3.8); (2) SequencingWithinIntervals → ILP (binary ILP encoding with ordering variables, as described in "How to solve" below).

Definition

Name: SequencingWithinIntervals
Reference: Garey & Johnson, Computers and Intractability, Chapter 3, Section 3.2.2, p.70

Mathematical definition:

INSTANCE: A finite set T of "tasks" and, for each t ∈ T, an integer "release time" r(t) ≥ 0, an integer "deadline" d(t) ≥ 0, and a "length" l(t) ∈ ℤ+, satisfying r(t) + l(t) ≤ d(t).
QUESTION: Does there exist a feasible schedule for T, that is, a function σ: T → ℤ_{≥0} such that, for each t ∈ T, σ(t) ≥ r(t), σ(t)+l(t) ≤ d(t), and, if t' ∈ T−{t}, then either σ(t')+l(t') ≤ σ(t) or σ(t') ≥ σ(t)+l(t)? (The task t is "executed" from time σ(t) to time σ(t)+l(t), cannot start executing until time r(t), must be completed by time d(t), and its execution cannot overlap the execution of any other task t'.)

Variables

• Count: n = |T| (one integer variable per task, choosing its start time)
• Per-variable domain: For each task t, σ(t) ∈ {r(t), r(t)+1, ..., d(t)−l(t)} (all valid integer start times)
• Meaning: σ(t) is the start time of task t. The constraint σ(t)+l(t) ≤ d(t) ensures t finishes before its deadline; σ(t) ≥ r(t) ensures t starts after its release time. Non-overlap constraints between all pairs of tasks are additional feasibility conditions.
• Input validity precondition: For every t ∈ T, r(t) + l(t) ≤ d(t) must hold. If this is violated for some task, the variable domain {r(t), …, d(t)−l(t)} is empty and no feasible schedule exists by construction; implementations should assert this precondition at construction time.

Schema (data type)

Type name: SequencingWithinIntervals
Variants: none (no type parameters; all times and lengths are plain non-negative integers)

Field	Type	Description
release_times	Vec<u64>	Release time r(t) ≥ 0 for each task t ∈ T
deadlines	Vec<u64>	Deadline d(t) ≥ 0 for each task t ∈ T; must satisfy d(t) ≥ r(t) + l(t)
lengths	Vec<u64>	Processing length l(t) ≥ 1 for each task t ∈ T

(All three vectors have the same length n = |T|; index i corresponds to task t_i.)

Complexity

• Best known exact algorithm: The problem is NP-complete (Garey & Johnson, Theorem 3.8, 1979). For general instances, dynamic programming over task subsets achieves O*(2^n) time: for each subset S ⊆ T, determine the earliest time by which all tasks in S can be feasibly completed, building up from single-task subsets. This is the standard subset-DP approach for single-machine scheduling. [Garey & Johnson, 1979.]
• Complexity string for declare_variants!: "2 ^ num_tasks"

Extra Remark

Full book text (verbatim):

INSTANCE: A finite set T of "tasks" and, for each t ∈ T, an integer "release time" r(t) ≥ 0, a "deadline" d(t) ∈ Z+, and a "length" l(t) ∈ Z+.
QUESTION: Does there exist a feasible schedule for T, that is, a function σ: T → Z+ such that, for each t ∈ T, σ(t) ≥ r(t), σ(t)+l(t) ≤ d(t), and, if t' ∈ T−{t}, then either σ(t')+l(t') ≤ σ(t) or σ(t') ≥ σ(t)+l(t)? (The task t is "executed" from time σ(t) to time σ(t)+l(t), cannot start executing until time r(t), must be completed by time d(t), and its execution cannot overlap the execution of any other task t'.)

Deviations from verbatim text (with justification):

1. σ: T → Z+ corrected to σ: T → ℤ_{≥0}: The book's use of Z+ is inconsistent with r(t) ≥ 0 and with Theorem 3.8's own example where σ(t_1) = 0. The standard modern formulation uses ℤ_{≥0}.
2. Precondition r(t) + l(t) ≤ d(t) made explicit: The book implicitly assumes this (otherwise the problem is trivially infeasible for that task), but does not state it in the instance description. It is added here for implementation correctness.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all n! orderings; for each ordering check whether tasks can be placed feasibly without violating release/deadline/non-overlap constraints.)
• It can be solved by reducing to integer programming. (Binary ILP with ordering variables x_{tt'} ∈ {0,1} indicating whether t precedes t', plus start-time variables; this gives an ILP with O(n^2) variables and constraints.)
• Other: Constraint programming / branch-and-bound with interval propagation is effective in practice.

Example Instance

Instance 1 (YES):
5 tasks on a single machine with overlapping availability windows:

Task	Release r	Deadline d	Length l
t₁	0	5	2
t₂	1	8	2
t₃	3	9	2
t₄	6	12	3
t₅	0	12	2

Each task can only start within its window [r, d−l], and the windows overlap, so finding a non-overlapping assignment is non-trivial. One feasible schedule: t₁ at [0, 2), t₂ at [2, 4), t₃ at [4, 6), t₄ at [6, 9), t₅ at [9, 11).

Exhaustive enumeration: Search space = 4×6×5×4×11 = 5,280 configurations. Exactly 41 feasible schedules. (Used in find_all_satisfying test)

Instance 2 (NO):
Two tasks that must both occupy [0, 2): r = [0, 0], d = [2, 2], l = [2, 2]. Each task has only one possible start time (0), so they always overlap. Search space = 1. 0 feasible schedules. (Used in find_all_satisfying empty test)

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem, but no planned reduction rules mentioned
Non-trivial	✅ Pass	Distinct feasibility constraints (scheduling with release times, deadlines, non-overlap) unlike any existing problem
Correctness	⚠️ Warn	Primary reference (GJ 1979) is established; secondary reference imprecise; complexity bound unverified
Well-written	⚠️ Warn	Mostly complete, but several issues with complexity section and notation

Overall: 1 passed, 3 warnings, 0 failed

---

Usefulness

The problem SequencingWithinIntervals does not exist in the current codebase (verified via pred show). It is a canonical NP-complete scheduling problem (problem P5 / SS5 in Garey & Johnson, Chapter 3, Section 3.2.2). It represents a genuinely new problem category — single-machine scheduling — which is not yet represented in the reduction graph.

Warning: The Motivation section does not mention any planned reduction rules that would connect this problem to the existing reduction graph. A problem without incoming or outgoing reductions is an orphan node. The issue mentions the PARTITION reduction is used in its NP-completeness proof but does not propose implementing any reduction rule. Consider specifying at least one reduction (e.g., from/to ILP, SAT, or a Partition problem if added later).

Non-trivial

This problem has genuinely distinct feasibility constraints from all 24 existing problems in the codebase. The key distinguishing features are:

• Per-variable interval constraints (release time and deadline per task) — no existing problem has this structure
• Non-overlap constraints between pairs of tasks — this is a scheduling-specific constraint absent from graph, formula, set, and algebraic problems
• Variable domains are heterogeneous (each variable has a different finite integer range) — unlike binary or uniform-domain problems

This is clearly a distinct problem, not a repackaging of any existing model. Pass.

Correctness

3a: Garey & Johnson (1979) — This is an established, authoritative reference already present in the project bibliography (garey1979 in references.bib). The claim that Sequencing Within Intervals appears in Chapter 3, Section 3.2.2, p.70, and that its NP-completeness is proved via reduction from PARTITION (Theorem 3.8), is consistent with the known structure of the GJ book. The reduction technique described (enforcer task pinning the schedule midpoint) is a well-known GJ construction. Verified (high confidence).

3b: "Lenstra & Rinnooy Kan, 1978" — This likely refers to J.K. Lenstra and A.H.G. Rinnooy Kan, "Complexity of Scheduling under Precedence Constraints," Operations Research 26(1):22-35, 1978. However, the issue does not provide a paper title, making independent verification difficult. Additionally, this reference appears in the Complexity section as support for the claim that "no known algorithm improves substantially upon O*(2^n)," but the Lenstra & Rinnooy Kan 1978 paper is about NP-completeness of scheduling under precedence constraints, not about exact algorithm time bounds. The citation does not clearly support the claim it is attached to. Warning: imprecise citation.

3c: Complexity claim — The issue states "No known algorithm improves substantially upon O*(2^n)" but does not cite a specific algorithm that achieves O*(2^n). The brute-force bound given is O(n! * n), which is far worse than 2^n. For the decision version (feasibility), dynamic programming over subsets could yield O*(2^n), but this is not stated or cited. The complexity section is vague and lacks a concrete algorithm name, author, and paper. Warning: unverified complexity bound.

3d: Deviation analysis — The issue thoughtfully documents two deviations from the verbatim GJ text (domain correction from Z+ to Z_>=0, and explicit precondition). Both are well-justified.

Well-written

4a: Information Completeness — All required template sections are present and substantive: Motivation, Name, Reference, Definition, Variables, Schema, Complexity, How to solve, Example Instance. The "Extra Remark" section with verbatim text and deviation analysis is a nice addition.

4b: Definition Completeness — The formal definition is precise and implementable. Input structure, feasibility constraints (release, deadline, non-overlap), and the decision question are all clearly stated with explicit quantifiers. Pass.

4c: Symbol and Notation Consistency — Symbols are generally consistent across sections. Minor issues:

• The Definition uses l(t) in Z+ but the Schema uses Vec<u64> — u64 includes 0, while Z+ does not. The issue should clarify whether lengths can be 0 (the Definition says Z+ which excludes 0, and the Schema description says "l(t) >= 1", which is consistent, but the Rust type u64 technically allows 0). This is a minor mismatch that should be handled by construction-time validation.
• The naming SequencingWithinIntervals follows the convention of no optimization prefix for decision/satisfaction problems, consistent with Satisfiability, Factoring, etc. Pass.

4d: Example Quality — The example is well-constructed:

• Derived from the PARTITION reduction (provides context)
• 5 tasks (non-trivial but hand-verifiable)
• Fully worked: shows source instance, all task parameters, and a complete feasible schedule with time intervals
• Correctly demonstrates the enforcer task mechanism

Minor issues:

• The example only shows a YES instance. A NO instance (or at least a note about what makes it infeasible) would strengthen the example for testing purposes, though this is not strictly required.

Recommendations

1. Add planned reduction rules to the Motivation section — at minimum, mention that PARTITION reduces to this problem (per the NP-completeness proof) or that it reduces to ILP (as mentioned in "How to solve").
2. Strengthen the Complexity section — cite a specific algorithm with a concrete time bound. For the decision problem, a subset-DP approach yields O*(2^n) time, or cite a more specific reference. The vague "No known algorithm improves substantially upon O*(2^n)" with a reference to Lenstra & Rinnooy Kan 1978 (which is about NP-completeness, not algorithms) should be corrected.
3. Provide full citation for Lenstra & Rinnooy Kan — include the paper title ("Complexity of Scheduling under Precedence Constraints," Operations Research, 1978) and verify it supports the claim.
4. Consider the u64 vs Z+ type mismatch — document in the Schema that lengths must all be >= 1 (enforced at construction), since u64 allows 0.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem, but no planned reduction rules to connect it to the graph
Non-trivial	✅ Pass	Distinct scheduling/satisfaction problem unlike any existing model
Correctness	⚠️ Warn	Core reference (GJ 1979) verified; complexity bound lacks a specific algorithm citation
Well-written	✅ Pass	All sections present and substantive; minor issues noted below

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

The problem SequencingWithinIntervals does not exist in the current codebase (confirmed via pred show). It is a canonical NP-complete scheduling problem (P5 in Garey & Johnson's appendix, Section 3.2.2). This is a historically significant problem.

However, the Motivation section does not mention any specific reduction rules that would connect this problem to the existing reduction graph. The issue mentions the PARTITION reduction used to prove NP-completeness but does not propose implementing it or any other reduction. A problem without planned reductions would be an orphan node in the graph. Recommendation: Add a subsection listing at least one planned reduction rule (e.g., Partition to SequencingWithinIntervals, or SequencingWithinIntervals to ILP/SAT).

Non-trivial

This is a genuinely distinct problem. The input structure (tasks with release times, deadlines, and processing lengths on a single machine) does not match any existing model:

• It is not a graph problem, formula problem, set problem, or algebraic problem.
• It is a satisfaction (decision) problem with Metric = bool, distinct from all 24 existing problems.
• The feasibility constraints (release times, deadlines, non-overlap) are unique to scheduling.
• It would correctly belong in src/models/misc/ given its unique input structure.

Correctness

Reference verification:

• Garey & Johnson (1979): Already in the project bibliography (garey1979). The book is the canonical reference for NP-completeness results. The claim that sequencing within intervals appears in Chapter 3, Section 3.2.2, p.70 is consistent with the book's structure (scheduling problems appear in the SS section of the appendix and are discussed in Chapter 3).
• Theorem 3.8 (PARTITION reduction): The described reduction using an "enforcer" task that pins the schedule at the midpoint is a well-known technique in scheduling NP-completeness proofs. This is consistent with the standard approach.
• Lenstra & Rinnooy Kan (1978): This paper exists — "Complexity of machine scheduling problems" (Operations Research, 1978). However, the issue does not specify what result from this paper is being cited. The paper addresses scheduling complexity more broadly (parallel machines with precedence constraints), not specifically the single-machine release-time/deadline problem.

Complexity concerns:

• The issue claims "No known algorithm improves substantially upon O*(2^n)" but does not cite a specific algorithm achieving this bound. The brute-force bound stated is O(n! * n), which is much worse than 2^n. The gap between O(n!) and O*(2^n) is not explained — what algorithm achieves 2^n? This needs a concrete citation.
• Recommendation: Either cite a specific dynamic programming or branch-and-bound algorithm that achieves O*(2^n), or use the honest bound of O(n! * n) for brute-force. For the declare_variants! complexity string, a concrete bound with citation is required.

Well-written

Strengths:

• All template sections are present and substantive (Motivation, Definition, Variables, Schema, Complexity, How to solve, Example).
• The mathematical definition is precise and directly quotes Garey & Johnson with explicit deviations documented.
• The example is fully worked with a concrete PARTITION instance, showing all task parameters and a valid schedule.
• The deviations from the verbatim book text are well-justified (sigma domain correction, precondition).

Minor issues:

• Multiple sections carry the "Unverified: AI-generated" warning. While the content appears correct, the warnings reduce confidence.
• The Lenstra & Rinnooy Kan (1978) citation in the Complexity section is vague — it is not clear which result from that paper applies here.
• The Schema uses Vec<u64> which may need consideration — the existing codebase uses u64 rarely; check whether usize or u32 would be more consistent with other models.

Recommendations

• Specify at least one planned reduction rule in the Motivation section to avoid creating an orphan node.
• Provide a concrete algorithm citation for the complexity bound (or use n! as the honest brute-force bound).
• Clarify which specific result from Lenstra & Rinnooy Kan (1978) is being referenced, or remove the citation if it is not directly relevant to this specific problem.