[Model] SequencingWithReleaseTimesAndDeadlines

[isPANN]

Motivation

SEQUENCING WITH RELEASE TIMES AND DEADLINES (P185) from Garey & Johnson, A5 SS1. A fundamental single-machine scheduling feasibility problem: given n tasks each with a processing time, release time, and deadline, can all tasks be non-preemptively scheduled on one processor such that each task starts after its release time and finishes by its deadline? This is the first problem in the Sequencing and Scheduling section of Garey & Johnson's appendix and is strongly NP-complete (by reduction from 3-PARTITION). It becomes polynomial when all task lengths are 1, when preemptions are allowed, or when all release times are 0.

Associated rules:

• R131: 3-Partition -> Sequencing with Release Times and Deadlines (as target)

Definition

Name: SequencingWithReleaseTimesAndDeadlines

Reference: Garey & Johnson, Computers and Intractability, A5 SS1

Mathematical definition:

INSTANCE: Set T of tasks and, for each task t in T, a length l(t) in Z+, a release time r(t) in Z0+, and a deadline d(t) in Z+.
QUESTION: Is there a one-processor schedule for T that satisfies the release time constraints and meets all the deadlines, i.e., a one-to-one function sigma:T->Z0+, with sigma(t) > sigma(t') implying sigma(t) >= sigma(t') + l(t'), such that, for all t in T, sigma(t) >= r(t) and sigma(t) + l(t) <= d(t)?

Variables

• Count: n = |T| (one variable per task, representing the task scheduled in that position)
• Per-variable domain: Permutation encoding — variable i has domain {0, 1, ..., n-1-i}, selecting which remaining task to schedule next
• dims(): vec![n, n-1, ..., 2, 1] — each position picks from the remaining unscheduled tasks (same encoding as MinimumTardinessSequencing)
• Meaning: The configuration encodes a permutation of tasks. During evaluate, tasks are scheduled left-to-right: each task starts at max(release_time, current_time). The schedule is feasible (returns true) iff for all tasks: sigma(t) >= r(t) and sigma(t) + l(t) <= d(t). This is a satisfaction (decision) problem with Metric = bool.

Schema (data type)

Type name: SequencingWithReleaseTimesAndDeadlines
Variants: none (no type parameters; all values are plain positive integers)

Field	Type	Description
lengths	Vec<u64>	Processing time l(t) for each task t in T
release_times	Vec<u64>	Release time r(t) for each task t (>= 0)
deadlines	Vec<u64>	Deadline d(t) for each task t (> 0)

Size fields: num_tasks

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• Key getter method: num_tasks() (= |T| = lengths.len()).

Complexity

• Best known exact algorithm: The problem is strongly NP-complete, so no pseudo-polynomial-time algorithm exists unless P = NP. A subset DP over scheduled task sets runs in O(2^n · n) time: for each subset S ⊆ T, compute the earliest time all tasks in S can finish, then extend by one task. Brute-force enumeration of all n! orderings gives O(n! · n). When all task lengths are 1, the problem is solvable in O(n log n) by earliest-deadline-first scheduling. When preemption is allowed, it is also polynomial. [Garey & Johnson, 1977; Lenstra, Rinnooy Kan & Brucker, 1977.]

declare_variants! guidance:

declare_variants! {
    SequencingWithReleaseTimesAndDeadlines => sat, "2^num_tasks",
}

This uses the subset DP bound O(2^n · n), the best known exact algorithm for the general case.

Extra Remark

Full book text:

INSTANCE: Set T of tasks and, for each task t in T, a length l(t) in Z+, a release time r(t) in Z0+, and a deadline d(t) in Z+.
QUESTION: Is there a one-processor schedule for T that satisfies the release time constraints and meets all the deadlines, i.e., a one-to-one function sigma:T->Z0+, with sigma(t) > sigma(t') implying sigma(t) >= sigma(t') + l(t'), such that, for all t in T, sigma(t) >= r(t) and sigma(t) + l(t) <= d(t)?

Reference: [Garey and Johnson, 1977b]. Transformation from 3-PARTITION (see Section 4.2).

Comment: NP-complete in the strong sense. Solvable in pseudo-polynomial time if the number of allowed values for r(t) and d(t) is bounded by a constant, but remains NP-complete (in the ordinary sense) even when each can take on only two values. If all task lengths are 1, or "preemptions" are allowed, or all release times are 0, the general problem can be solved in polynomial time, even under "precedence constraints" [Lawler, 1973], [Lageweg, Lenstra, and Rinnooy Kan, 1976]. Can also be solved in polynomial time even if release times and deadlines are allowed to be arbitrary rationals and there are precedence constraints, so long as all tasks have equal length [Carlier, 1978], [Simons, 1978], [Garey, Johnson, Simons, and Tarjan, 1978], or preemptions are allowed [Blazewicz, 1976].

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all n! orderings of tasks; for each ordering greedily assign start times and check feasibility.)
• It can be solved by reducing to integer programming. (ILP: integer start-time variables sigma_t, constraints sigma_t >= r(t), sigma_t + l(t) <= d(t), and disjunctive constraints for non-overlap: sigma_t + l(t) <= sigma_{t'} or sigma_{t'} + l(t') <= sigma_t for all pairs.)
• Other: Branch-and-bound with constraint propagation (practical exact solver for moderate n).

Example Instance

Input:
T = {t_1, t_2, t_3, t_4, t_5} (n = 5 tasks)
Lengths: l(t_1) = 3, l(t_2) = 2, l(t_3) = 4, l(t_4) = 1, l(t_5) = 2
Release times: r(t_1) = 0, r(t_2) = 1, r(t_3) = 5, r(t_4) = 0, r(t_5) = 8
Deadlines: d(t_1) = 5, d(t_2) = 6, d(t_3) = 10, d(t_4) = 3, d(t_5) = 12

Feasible schedule:

• sigma(t_4) = 0, runs [0, 1) -- r=0 <= 0, finish 1 <= d=3
• sigma(t_1) = 1, runs [1, 4) -- r=0 <= 1, finish 4 <= d=5
• sigma(t_2) = 4, runs [4, 6) -- r=1 <= 4, finish 6 <= d=6
• sigma(t_3) = 6, runs [6, 10) -- r=5 <= 6, finish 10 <= d=10
• sigma(t_5) = 10, runs [10, 12) -- r=8 <= 10, finish 12 <= d=12

All tasks within their release-deadline windows, no overlaps. Feasible schedule exists.

Answer: YES.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; planned incoming reduction from 3-Partition
Non-trivial	✅ Pass	Distinct single-machine scheduling satisfaction problem, no equivalent in codebase
Correctness	✅ Pass	All references verified: Garey & Johnson 1977/1979, Lenstra et al. 1977
Well-written	⚠️ Warn	Variable encoding ambiguous (start time vs permutation); complexity lacks concrete bound for declare_variants!

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

SequencingWithReleaseTimesAndDeadlines does not exist in the codebase. It is a classical strongly NP-complete scheduling problem (Garey & Johnson A5 SS1) with a planned incoming reduction from 3-Partition (R131). While only one associated rule is listed, this is a fundamental scheduling problem that could serve as a hub for further scheduling-related reductions. The motivation section clearly explains the problem's significance and tractability boundary (polynomial for unit lengths, preemptive case, or zero release times).

Non-trivial

This problem is genuinely distinct from all existing problems in the codebase:

• Not BinPacking: BinPacking minimizes the number of bins for items with sizes; this is a feasibility problem with time constraints (release times, deadlines, processing times) on a single machine.
• Not PaintShop: PaintShop minimizes color switches; this is a scheduling feasibility problem.
• The combination of release times, deadlines, processing times, and non-overlap constraints makes this a unique problem with distinct feasibility conditions.

Correctness

Reference verification:

• Garey & Johnson 1979: Confirmed in project bibliography (garey1979). Problem SS1 in the appendix.
• Garey & Johnson 1977b: Verified — refers to "Strong NP-Completeness Results: Motivation, Examples, and Implications," JACM 25(3), 1978 (the 1977b label may refer to the technical report version). Establishes strong NP-completeness via reduction from 3-Partition.
• Lenstra, Rinnooy Kan & Brucker 1977: Verified — "Complexity of machine scheduling problems," Annals of Discrete Mathematics 1:343-362. Surveys and classifies scheduling problem complexity.
• The formal definition matches the standard Garey & Johnson formulation exactly.
• Strong NP-completeness claim is correct. Polynomial-time special cases (unit lengths, preemptive, zero release times) are well-established.

Well-written

Strengths:

• All template sections present and substantive.
• Example is well-constructed: 5 tasks with a fully verified feasible schedule showing all constraint checks.
• Schema design is clean with appropriate field types.
• ILP formulation in "How to solve" is correct (binary disjunctive constraints for non-overlap).
• The "Extra Remark" section with the full Garey & Johnson text is valuable for implementers.

Warnings:

• Variable encoding ambiguity: The Variables section mentions two alternatives ("start time" or "permutation of tasks") without committing to one. For implementation, a clear choice is needed. The start-time encoding with domain {0, 1, ..., H-1} is more natural for this problem but creates a large domain; a permutation encoding with domain {0, ..., n-1} is more compact but requires greedy start-time assignment during evaluation.
• Complexity bound: The section correctly describes the problem as strongly NP-complete but doesn't provide a concrete time bound for declare_variants!. A bound like "num_tasks!" (factorial) for brute-force, or a tighter bound if known, would be needed.

Recommendations

• Settle on a single variable encoding (recommend permutation of n tasks, with greedy left-to-right start time assignment during evaluate).
• Add a concrete worst-case complexity string for declare_variants!.
• Consider listing additional outgoing reduction rules if known — having only one incoming rule makes this a leaf node in the reduction graph.

[zazabap]

Fix-issue changelog

• Variables section rewritten: Removed ambiguous dual encoding (start time vs permutation). Now uses permutation encoding with dims = [n, n-1, ..., 2, 1], consistent with MinimumTardinessSequencing
• Added declare_variants! guidance: sat marker with complexity "2^num_tasks" (subset DP bound)
• Added Size fields and Notes: Documented num_tasks size field, Metric = bool, SatisfactionProblem trait
• Updated complexity narrative: Added subset DP description (O(2^n · n)) as the best known exact algorithm

Applied by /fix-issue.