[Model] SequencingWithDeadlinesAndSetUpTimes

[isPANN]

Motivation

SEQUENCING WITH DEADLINES AND SET-UP TIMES (P190) from Garey & Johnson, A5 SS6. A single-processor scheduling problem where tasks belong to different "compiler" classes, and switching between classes incurs a set-up time penalty. The question is whether all tasks can meet their individual deadlines given these switching costs. NP-complete even with equal set-up times (via reduction from PARTITION, R136). Can be solved in pseudo-polynomial time when the number of distinct deadlines is bounded by a constant.

Associated rules:

• R136: PARTITION → SequencingWithDeadlinesAndSetUpTimes (this model is the target)

Definition

Name: SequencingWithDeadlinesAndSetUpTimes
Reference: Garey & Johnson, Computers and Intractability, A5 SS6

Mathematical definition:

INSTANCE: Set C of "compilers," set T of n tasks, for each t ∈ T a length l(t) ∈ Z⁺, a deadline d(t) ∈ Z⁺, and a compiler k(t) ∈ C, and for each c ∈ C a "set-up time" s(c) ∈ Z⁰⁺.

QUESTION: Is there a one-processor schedule σ for T (a permutation of tasks) that meets all task deadlines, where whenever two consecutively scheduled tasks t and t' have different compilers (k(t) ≠ k(t')), the start of t' is delayed by the set-up time s(k(t'))?

Formally: for consecutively scheduled tasks t, t' with σ(t) < σ(t'), if k(t) ≠ k(t'), then σ(t') ≥ σ(t) + l(t) + s(k(t')). A schedule is feasible if σ(t) + l(t) ≤ d(t) for all t ∈ T.

This is a satisfaction (feasibility) problem: Value = Or.

Variables

• Count: n = |T|. The configuration is a permutation of the n tasks.
• Per-variable domain: n (each position selects a task index 0..n−1)
• Meaning: config[i] = j means task j is scheduled in position i. Start times are computed left-to-right: for the task at position i, the start time equals the finish time of position i−1, plus the set-up time s(k(t)) if the compiler changed. A configuration is valid if it is a permutation. evaluate() returns Or(true) if all deadlines are met, Or(false) otherwise.

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

Schema (data type)

Type name: SequencingWithDeadlinesAndSetUpTimes
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()
deadlines	Vec<u64>	Deadline d(t) for each task t
compilers	Vec<usize>	Compiler index k(t) for each task t	num_compilers() → distinct compiler count
setup_times	Vec<u64>	Set-up time s(c) for each compiler c ∈ C

Problem type: Satisfaction (feasibility)
Value type: Or

Complexity

• Decision complexity: NP-complete (Bruno & Downey, 1978; transformation from PARTITION). Remains NP-complete even if all set-up times are equal.
• Best known exact algorithm: Brute-force over all n! permutations, checking deadline feasibility for each. Worst-case time: factorial(num_tasks).
• Complexity string for declare_variants!: "factorial(num_tasks)"
• Special cases: Can be solved in pseudo-polynomial time when the number of distinct deadlines is bounded by a constant. The related problem with "changeover costs" is also NP-complete even with equal costs.
• References:
  • [Bruno & Downey, 1978] J. Bruno and P. Downey, "Sequencing tasks with set-up times", 1978.
  • [Garey & Johnson, 1979] M. R. Garey and D. S. Johnson, Computers and Intractability, A5 SS6.

Extra Remark

Full book text:

INSTANCE: Set C of "compilers," set T of tasks, for each t ∈ T a length l(t) ∈ Z+, a deadline d(t) ∈ Z+, and a compiler k(t) ∈ C, and for each c ∈ C a "set-up time" l(c) ∈ Z0+.
QUESTION: Is there a one-processor schedule σ for T that meets all the task deadlines and that satisfies the additional constraint that, whenever two tasks t and t' with σ(t) < σ(t') are scheduled "consecutively" (i.e., no other task t'' has σ(t) < σ(t'') < σ(t')) and have different compilers (i.e., k(t) ≠ k(t')), then σ(t') ≥ σ(t) + l(t) + l(k(t'))?

Reference: [Bruno and Downey, 1978]. Transformation from PARTITION.

Comment: Remains NP-complete even if all set-up times are equal. The related problem in which set-up times are replaced by "changeover costs," and we want to know if there is a schedule that meets all the deadlines and has total changeover cost at most K, is NP-complete even if all changeover costs are equal. Both problems can be solved in pseudo-polynomial time when the number of distinct deadlines is bounded by a constant. If the number of deadlines is unbounded, it is open whether these problems are NP-complete in the strong sense.

How to solve

• It can be solved by (existing) bruteforce. Enumerate all n! permutations; for each, compute start times including set-up penalties for compiler switches; check all deadlines.
• It can be solved by reducing to integer programming. Binary ILP: x_{ij} ∈ {0,1} (task i in position j), with set-up time constraints for compiler switches and deadline constraints.
• Other: Pseudo-polynomial DP when the number of distinct deadlines is bounded by a constant.

Example Instance

Input:
C = {c₀, c₁} (2 compilers), setup_times = [1, 2] (switch to c₀ costs 1, switch to c₁ costs 2)
T = {t₁, t₂, t₃, t₄, t₅} (n = 5 tasks)

Task	Length	Deadline	Compiler
t₁	2	4	c₀
t₂	3	11	c₁
t₃	1	3	c₀
t₄	2	16	c₁
t₅	2	7	c₀

Total processing time = 2 + 3 + 1 + 2 + 2 = 10. With setup costs, actual completion depends on compiler switches.

Feasible schedule (YES instance):
σ: t₃, t₁, t₅, t₂, t₄ (group c₀ tasks first, then c₁ — one switch)

Task	Compiler	Setup	Start	Finish	Deadline	Meets?
t₃	c₀	—	0	1	3	✓
t₁	c₀	—	1	3	4	✓
t₅	c₀	—	3	5	7	✓
t₂	c₁	+2	7	10	11	✓
t₄	c₁	—	10	12	16	✓

All deadlines met. Answer: Or(true).

Infeasible schedules (confirming non-triviality):

1. σ = (t₁, t₂, t₃, t₄, t₅): t₃ finishes at 9 > deadline 3, t₅ finishes at 13 > deadline 7. ✗
2. σ = (t₁, t₃, t₅, t₄, t₂): t₂ finishes at 12 > deadline 11 (switch c₁→c₀→c₁ adds extra setups). ✗
3. σ = (t₂, t₁, t₃, t₅, t₄): t₁ finishes at 6 > deadline 4. ✗

Out of 120 permutations, only 2 are feasible (both group all c₀ tasks before c₁ tasks), confirming the setup-time constraint is the binding factor.

Expected outcome: Or(true)

Reduction Rule Crossref

• R136: Partition → SequencingWithDeadlinesAndSetUpTimes
• Direct ILP: SequencingWithDeadlinesAndSetUpTimes → ILP (binary ordering + setup + deadline constraints)

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph
Non-trivial	✅ Pass	Distinct from existing problems; compiler set-up times add unique scheduling structure
Correctness	✅ Pass	Reference verified: Bruno & Downey, 1978, SIAM J. Computing 7, pp. 393-404
Well-written	❌ Fail	Example modifies the input instance mid-way to achieve feasibility; set-up time notation is ambiguous

Overall: 3 passed, 1 failed, 0 warnings

---

Usefulness

The problem SequencingWithDeadlinesAndSetUpTimes does not exist in the current codebase. It introduces a new scheduling variant with compiler/class-dependent set-up times, which is structurally unique. The motivation mentions a concrete associated rule (PARTITION reduction). Two solver paths are identified (brute-force and ILP). Pass.

Non-trivial

This problem adds a genuinely new dimension: tasks belong to classes (compilers) and switching between classes incurs set-up time penalties. This is distinct from the other scheduling problems (SS3 tardy task weight, SS4 weighted completion time, SS5 weighted tardiness) and from all existing graph/formula/set/algebraic problems. The feasibility constraint (all tasks must meet their deadlines including set-up overhead) is structurally different. Pass.

Correctness

Reference verification:

1. Bruno & Downey, 1978 — Confirmed. "Complexity of task sequencing with deadlines, set-up times and changeover costs," SIAM Journal on Computing 7(4), pp. 393-404. The paper establishes NP-completeness via reduction from PARTITION and shows the problem remains NP-complete even with equal set-up times. ✅

2. Garey & Johnson, SS6 — The definition in the issue matches the standard formulation from Computers and Intractability. The Extra Remark section faithfully reproduces the book text. ✅

3. Pseudo-polynomial time for bounded number of distinct deadlines — Consistent with the G&J comment. ✅

Verdict: Pass.

Well-written

4a: Information Completeness — All required sections present: Motivation, Definition, Variables, Schema, Complexity, How to solve, Example Instance. ✅

4b: Definition Completeness — The formal definition is precise, taken from G&J. Input (compilers, tasks with lengths/deadlines/compiler assignments, set-up times), feasibility (schedule meeting all deadlines with set-up constraints), and decision question are clearly stated. ✅

4c: Symbol and Notation Consistency — There is an ambiguity in the set-up time notation. The G&J definition uses l(c) for set-up time of compiler c, but l(t) is already used for task length. The issue inherits this from G&J but it could cause confusion during implementation. The Schema uses distinct field names (lengths vs setup_times), which is better. Minor concern. ⚠️

4d: Example Quality — This is the critical failure. The example starts with a concrete instance (5 tasks, K implicit as deadline feasibility), then tries 6 different schedules, all of which fail. The author then modifies the input instance by changing d(t_2) from 12 to 15 to make a schedule feasible. An example that requires changing the problem definition to work is not a valid example — it suggests the original instance may be infeasible, and the author couldn't find a feasible schedule. A proper example must:

1. Define the instance once
2. Show a feasible schedule exists (or prove infeasibility if that's the answer)
3. Not modify the instance to fit the solution

This is a Fail — the example needs to be redesigned from scratch with an instance that has a known feasible schedule. ❌

Verdict: Fail.

Recommendations

• Design a new example from scratch: start with a feasible schedule, then derive the deadlines from it (reverse-engineering ensures feasibility). For instance, pick an order, compute completion times with set-ups, then set deadlines slightly above the completion times.
• Consider using a smaller example (3-4 tasks, 2 compilers) that is easier to verify by hand.
• Clarify the set-up time notation: in implementation, use distinct names (e.g., task_lengths and setup_times) to avoid the l(t) vs l(c) ambiguity inherited from G&J.

[isPANN]

Issue Quality Check — Model (Re-check)

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph; concrete reduction from PARTITION planned
Non-trivial	✅ Pass	Distinct from existing scheduling problems; compiler set-up times add unique structure
Correctness	✅ Pass	Bruno & Downey (1978) verified in SIAM J. Computing 7(4); G&J SS6 definition matches
Well-written	❌ Fail	Example modifies input mid-way; ILP companion issue not linked; complexity expression missing

Overall: 3 passed, 1 failed, 0 warnings

Comparison with previous check (2026-03-12): Same verdicts — 3 passed, 1 failed. The Well-written failure persists with the same core issue (broken example). This re-check additionally flags two items not caught previously: (1) missing ILP companion issue link, and (2) missing concrete complexity expression.

---

Usefulness

The problem SequencingWithDeadlinesAndSetUpTimes does not exist in the current codebase. While several scheduling problems already exist (FlowShopScheduling, JobShopScheduling, MinimumTardinessSequencing, SchedulingWithIndividualDeadlines, SequencingWithReleaseTimesAndDeadlines, etc.), none model compiler-class-dependent set-up times. The issue mentions a concrete associated rule (PARTITION reduction, R136 from G&J). Two solver paths are identified (brute-force and ILP). Pass.

Non-trivial

This problem adds a genuinely distinct dimension: tasks belong to compiler classes, and switching between classes incurs a set-up time penalty that depends on the destination class. This is structurally different from SchedulingWithIndividualDeadlines (no set-up times), SequencingWithReleaseTimesAndDeadlines (release times but no class-switching costs), and all other existing scheduling models. The feasibility constraint incorporating class-dependent switching overhead is a novel structural feature. Pass.

Correctness

Reference verification:

1. Bruno & Downey, 1978 — Confirmed. "Complexity of Task Sequencing with Deadlines, Set-Up Times and Changeover Costs," SIAM Journal on Computing 7(4), pp. 393-404. NP-completeness via reduction from PARTITION is established; the paper also proves NP-completeness for equal set-up times.

2. Garey & Johnson, A5 SS6 — The definition in the issue matches the standard G&J formulation. The Extra Remark section faithfully reproduces the book commentary about equal set-up times and pseudo-polynomial time for bounded distinct deadlines.

3. Pseudo-polynomial time claim — Consistent with G&J commentary.

Pass.

Well-written

4a: Information Completeness

• Motivation: present and concrete. ✅
• Name: follows conventions. ✅
• Reference: Bruno & Downey cited. ✅
• Definition: precise, from G&J. ✅
• Variables: present and clear. ✅
• Schema: field table provided. ✅
• Complexity: present but incomplete — gives only brute-force O(n! * n). The skill requires a concrete complexity expression for the best known exact algorithm (e.g., n! * n or a tighter bound). The issue says "exact algorithms rely on branch-and-bound or ILP formulations" without citing a specific algorithm or bound. ❌
• How to solve: ILP box is checked, but no companion [Rule] SequencingWithDeadlinesAndSetUpTimes to ILP issue is linked as required when claiming direct ILP solvability. ❌
• Example Instance: present but broken (see 4d). ❌

4b: Definition Completeness — The formal definition is precise and taken directly from G&J. Input, feasibility, and decision question are clearly stated. ✅

4c: Symbol and Notation Consistency — The l(t) / l(c) overloading is inherited from G&J and creates ambiguity (same function name l for both task length and set-up time). The Schema resolves this with distinct field names (lengths vs setup_times), so this is a minor concern. ⚠️

4d: Example Quality — Critical failure (unchanged from previous check). The example starts with a concrete instance (5 tasks, 2 compilers), then tries 6 different schedules, all of which fail with the original deadlines. The author then modifies the input by changing d(t_2) from 12 to 15. Python verification confirms:

• Original instance (d_2=12): 0 feasible schedules out of 120 — the instance is provably infeasible
• Adjusted instance (d_2=15): 4 feasible schedules out of 120 — the claimed schedule (t_3, t_1, t_5, t_2, t_4) is verified correct with start times 0, 2, 5, 11, 15

An example that requires retroactively modifying the problem input is not valid. The example must define the instance once and demonstrate a solution (or prove infeasibility). ❌

Verdict: Fail.

Recommendations

• Example: Design a new example from scratch using the "reverse-engineering" approach: pick a feasible schedule order, compute completion times with set-ups, then set deadlines at or slightly above the completion times. This guarantees feasibility. Consider a smaller instance (3-4 tasks, 2 compilers) for easier hand-verification.
• Complexity: Cite a specific best-known exact algorithm with a concrete time bound expression, or state factorial(num_tasks) * num_tasks as the brute-force baseline if no better algorithm is known.
• ILP companion: Either file a [Rule] SequencingWithDeadlinesAndSetUpTimes to ILP issue and link it, or uncheck the ILP box.
• Notation: Consider renaming the set-up time in the definition to avoid the l(t) / l(c) overloading (e.g., use s(c) for set-up times).

[isPANN]

Fix-issue changelog

• Replaced broken example (infeasible instance with mid-example deadline change) with a correct 5-task instance
• New example: 2/120 permutations feasible, verified by brute-force Python script
• Added getter methods (num_tasks(), num_compilers())
• Added concrete complexity string factorial(num_tasks) for declare_variants!
• Added explicit problem type: satisfaction, Value = Or
• Added dims() mapping (permutation encoding)
• Added ILP solvability and direct ILP crossref
• Cleaned up Definition formatting (optimization-style INSTANCE/QUESTION)

Applied by /fix-issue.