[Model] SchedulingWithIndividualDeadlines

[isPANN]

Motivation

SCHEDULING WITH INDIVIDUAL DEADLINES (P195) from Garey & Johnson, A5 SS11. A classical NP-complete scheduling problem where unit-length tasks with precedence constraints and individual deadlines must be assigned to m parallel processors so that every task meets its own deadline. The problem remains NP-complete even when the precedence order is an out-tree, but becomes polynomial for in-trees and for m = 2 with arbitrary precedence [Brucker, Garey, and Johnson, 1977].

Associated rules:

• R140: Vertex Cover -> Scheduling with Individual Deadlines (this model is the target)

Definition

Name: SchedulingWithIndividualDeadlines

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

Mathematical definition:

INSTANCE: Set T of tasks, each having length l(t) = 1, number m in Z+ of processors, partial order < on T, and for each task t in T a deadline d(t) in Z+.
QUESTION: Is there an m-processor schedule sigma for T that obeys the precedence constraints and meets all the deadlines, i.e., sigma(t) + l(t) <= d(t) for all t in T?

Variables

• Count: n = |T| (one discrete variable per task, choosing the time slot in which it is scheduled)
• Per-variable domain: {0, 1, ..., D_max - 1} where D_max = max_t d(t) -- the time slot assigned to each task
• Meaning: sigma(t) in {0, ..., d(t)-1} is the start time of task t. Since all tasks have unit length, task t occupies [sigma(t), sigma(t)+1). The schedule must satisfy: (1) at most m tasks per time slot, (2) if t < t' then sigma(t) + 1 <= sigma(t'), and (3) sigma(t) + 1 <= d(t) for every task t.

Schema (data type)

Type name: SchedulingWithIndividualDeadlines
Variants: none (no type parameters; all tasks have unit length)

Field	Type	Description
num_tasks	usize	Number of unit-length tasks n =
num_processors	usize	Number of identical processors m
precedences	Vec<(usize, usize)>	Edges (i, j) of the precedence DAG: task i must precede j
deadlines	Vec<u64>	Individual deadline d(t) for each task t

Complexity

• Best known exact algorithm: NP-complete by reduction from VERTEX COVER [Brucker, Garey, and Johnson, 1977]. Remains NP-complete even if the precedence order is an out-tree. Solvable in polynomial time when: (a) m = 2 and precedence is arbitrary [Garey and Johnson, 1976c], (b) precedence is an in-tree, or (c) precedence is empty (solvable by matching for arbitrary m). For the general NP-complete case, no known exact algorithm improves upon O*(D_max^n) brute-force enumeration; practical solvers use branch-and-bound or ILP formulations.

Extra Remark

Full book text:

INSTANCE: Set T of tasks, each having length l(t) = 1, number m in Z+ of processors, partial order < on T, and for each task t in T a deadline d(t) in Z+.
QUESTION: Is there an m-processor schedule sigma for T that obeys the precedence constraints and meets all the deadlines, i.e., sigma(t) + l(t) <= d(t) for all t in T?

Reference: [Brucker, Garey, and Johnson, 1977]. Transformation from VERTEX COVER.

Comment: Remains NP-complete even if < is an "out-tree" partial order (no task has more than one immediate predecessor), but can be solved in polynomial time if < is an "in-tree" partial order (no task has more than one immediate successor). Solvable in polynomial time if m = 2 and < is arbitrary [Garey and Johnson, 1976c], even if individual release times are included [Garey and Johnson, 1977b]. For < empty, can be solved in polynomial time by matching for m arbitrary, even with release times and with a single resource having 0-1 valued requirements [Blazewicz, 1977b], [Blazewicz, 1978].

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all assignments of tasks to time slots, checking precedence, processor capacity, and deadlines.)
• It can be solved by reducing to integer programming. (Binary ILP: x_{t,u} in {0,1}, sum_u x_{t,u} = 1 for each t, sum_t x_{t,u} <= m for each u, x_{t,u} = 0 for u >= d(t), and precedence constraints.)
• Other: Polynomial for m = 2 (Garey-Johnson algorithm); polynomial for in-tree precedence.

Example Instance

Input:
T = {t_1, t_2, t_3, t_4, t_5, t_6, t_7} (n = 7 unit-length tasks)
m = 3 processors
Precedences: t_1 < t_4, t_2 < t_4, t_2 < t_5, t_3 < t_5, t_3 < t_6
Deadlines: d(t_1) = 2, d(t_2) = 1, d(t_3) = 2, d(t_4) = 2, d(t_5) = 3, d(t_6) = 3, d(t_7) = 2

Feasible schedule:
Time slot 0: {t_1, t_2, t_3} (3 tasks <= 3 processors; t_2 must finish by 1, so it starts at 0)
Time slot 1: {t_4, t_6, t_7} (3 tasks <= 3 processors; t_4 predecessors t_1,t_2 done; t_6 predecessor t_3 done; t_7 has no predecessors)
Time slot 2: {t_5} (1 task; predecessors t_2,t_3 done; d(t_5) = 3, finishes at 3 <= 3)

Check deadlines:

• t_1: starts 0, finishes 1 <= 2
• t_2: starts 0, finishes 1 <= 1
• t_3: starts 0, finishes 1 <= 2
• t_4: starts 1, finishes 2 <= 2
• t_5: starts 2, finishes 3 <= 3
• t_6: starts 1, finishes 2 <= 3
• t_7: starts 1, finishes 2 <= 2

Answer: YES -- all tasks meet their individual deadlines.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel scheduling problem not in reduction graph; has planned reduction from Vertex Cover
Non-trivial	✅ Pass	Distinct from #501 and #502 — adds individual per-task deadlines with precedence constraints
Correctness	✅ Pass	Brucker, Garey & Johnson 1977 reference verified; in-tree/out-tree complexity distinction confirmed
Well-written	⚠️ Warn	No concrete complexity string for declare_variants!

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

The problem does not exist in the current codebase. It is a classical NP-complete scheduling problem from Garey & Johnson (A5 SS11) with a planned reduction from Vertex Cover. It differs from PrecedenceConstrainedScheduling (which has a global deadline) by giving each task its own individual deadline, and it differs from ResourceConstrainedScheduling (which has resource bounds but no precedence). This adds a genuinely new node to the reduction graph. Pass.

Non-trivial

This is genuinely distinct from all existing problems and from the other scheduling issues. The feasibility constraint uniquely combines: (1) precedence constraints (partial order on tasks), (2) processor capacity (at most m tasks per time slot), and (3) individual per-task deadlines d(t). The per-task deadline structure makes this fundamentally different from PrecedenceConstrainedScheduling (global deadline D) and ResourceConstrainedScheduling (resource bounds, no precedence). Pass.

Correctness

• Brucker, Garey & Johnson (1977): Verified. "Scheduling equal-length tasks under tree-like precedence constraints to minimize maximum lateness," Mathematics of Operations Research 2, 275-284 (1977). Establishes NP-completeness via reduction from Vertex Cover. ✅
• Out-tree NP-completeness: Verified. The distinction between in-tree (polynomial) and out-tree (NP-complete) for scheduling with individual deadlines is a well-established result in the scheduling literature. ✅
• m = 2 polynomial solvability: Garey & Johnson (1976c/1977b) established polynomial-time algorithms for the two-processor case. Consistent with the literature. ✅
• In-tree polynomial solvability: The Brucker-Garey-Johnson algorithm produces optimal schedules for in-tree precedences in O(n log n) time. ✅
• Blazewicz (1977b, 1978): Referenced in Extra Remark for the empty precedence case with release times and 0-1 resource requirements. Not directly verified but consistent with the Garey & Johnson book attribution. ✅

Well-written

Well-structured and complete, with one minor issue:

1. All template sections present: Motivation ✅, Name ✅, Reference ✅, Definition ✅, Variables ✅, Schema ✅, Complexity ⚠️, How to solve ✅, Example ✅.

2. No concrete complexity string: The Complexity section discusses NP-completeness and brute-force O*(D_max^n) but does not provide a parseable expression for declare_variants!. Something like "max_deadline ^ num_tasks" would be needed.

3. Definition clarity: The mathematical definition is directly from Garey & Johnson and is precise. The condition sigma(t) + l(t) <= d(t) is clear. ✅

4. Schema design: Clean and minimal. The precedences as Vec<(usize, usize)> and deadlines as Vec<u64> are appropriate. ✅

5. Example: Good quality with 7 tasks, 3 processors, mixed deadlines, and non-trivial precedence structure. The schedule is hand-verifiable and demonstrates tight deadline constraints (t_2 must start at slot 0 due to d(t_2) = 1). ✅

6. Variables section: Correctly identifies the domain with D_max, and states all three constraint types clearly. ✅

Recommendations

• Add a concrete complexity string suitable for declare_variants!.