[Model] PrecedenceConstrainedScheduling

[isPANN]

Motivation

PRECEDENCE CONSTRAINED SCHEDULING (P193) from Garey & Johnson, A5 SS9. A fundamental NP-complete multiprocessor scheduling problem: given unit-length tasks with precedence constraints, m processors, and a deadline D, can all tasks be scheduled to meet D while respecting precedences? NP-complete via reduction from 3SAT (R138) [Ullman, 1975]. Remains NP-complete even for D = 3 [Lenstra & Rinnooy Kan, 1978a]. Solvable in polynomial time for m = 2 [Coffman & Graham, 1972], for forest-structured precedences [Hu, 1961], and for chordal complement precedences [Papadimitriou & Yannakakis, 1978b].

Associated rules:

• R138: 3SAT → Precedence Constrained Scheduling (this model is the target)

Definition

Name: PrecedenceConstrainedScheduling

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

Mathematical definition:

INSTANCE: Set T of tasks, each having length l(t) = 1, number m ∈ Z+ of processors, partial order < on T, and a deadline D ∈ Z+.
QUESTION: Is there an m-processor schedule σ for T that meets the overall deadline D and obeys the precedence constraints, i.e., such that t < t' implies σ(t') ≥ σ(t) + l(t) = σ(t) + 1?

Variables

• Count: n = |T| (one variable per task, representing the time slot it is assigned to)
• Per-variable domain: {0, 1, ..., D-1} — the time slot in which the task is executed (0-indexed)
• dims(): vec![deadline; num_tasks] — each task is assigned to one of D time slots
• Meaning: σ(t_i) ∈ {0, ..., D-1} is the time slot assigned to task t_i. At most m tasks can be assigned to the same time slot (processor capacity). If t_i < t_j in the partial order, then σ(t_j) ≥ σ(t_i) + 1. A valid schedule assigns all n tasks to time slots in {0, ..., D-1} respecting both processor capacity and precedence constraints. This is a satisfaction (decision) problem with Metric = bool.

Schema (data type)

Type name: PrecedenceConstrainedScheduling
Variants: none (tasks are unit-length; no type parameters)

Field	Type	Description
num_tasks	usize	Number of tasks n =
num_processors	usize	Number of processors m
deadline	usize	Global deadline D
precedences	Vec<(usize, usize)>	Precedence pairs (i, j) meaning t_i < t_j

Size fields: num_tasks, num_processors, deadline

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• Key getter methods: num_tasks() (= |T|), num_processors() (= m), deadline() (= D).

Complexity

• Best known exact algorithm: The problem is NP-complete [Ullman, 1975]. For m = 2, the Coffman-Graham algorithm solves it in O(n^2) time [Coffman & Graham, 1972]. For fixed m ≥ 3, the complexity is open. For variable m, the problem is strongly NP-hard. Exact algorithms for general instances use branch-and-bound or ILP formulations. The problem is W[2]-hard parameterized by the number of processors [Bodlaender & Fellows, 'W[2]-hardness of precedence constrained K-processor scheduling,' Operations Research Letters, 18(2):93-97, 1995]. A fixed-parameter algorithm based on the width w of the precedence graph runs in O(n^3 + n · w · 2^{4w}) time [van Bevern et al., 2016]. The brute-force complexity is O(D^n) for assigning each of n tasks to one of D time slots, followed by feasibility checking.
  declare_variants! guidance:

declare_variants! {
    PrecedenceConstrainedScheduling => sat, "deadline ^ num_tasks",
}

This uses the brute-force O(D^n) bound for assigning each of n tasks to one of D time slots.

Extra Remark

Full book text:

INSTANCE: Set T of tasks, each having length l(t) = 1, number m ∈ Z+ of processors, partial order < on T, and a deadline D ∈ Z+.
QUESTION: Is there an m-processor schedule σ for T that meets the overall deadline D and obeys the precedence constraints, i.e., such that t < t' implies σ(t') ≥ σ(t) + l(t) = σ(t) + 1?

Reference: [Ullman, 1975]. Transformation from 3SAT.

Comment: Remains NP-complete for D = 3 [Lenstra and Rinnooy Kan, 1978a]. Can be solved in polynomial time if m = 2 (e.g., see [Coffman and Graham, 1972]) or if m is arbitrary and < is a "forest" [Hu, 1961] or has a chordal graph as complement [Papadimitriou and Yannakakis, 1978b]. Complexity remains open for all fixed m ≥ 3 when < is arbitrary. The m = 2 case becomes NP-complete if both task lengths 1 and 2 are allowed [Ullman, 1975]. If each task t can only be executed by a specified processor p(t), the problem is NP-complete for m = 2 and < arbitrary, and for m arbitrary and < a forest, but can be solved in polynomial time for m arbitrary if < is a "cyclic forest" [Goyal, 1976].

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all assignments of n tasks to D time slots; check processor capacity ≤ m per slot and precedence constraints.)
• It can be solved by reducing to integer programming. (Binary ILP: x_{it} ∈ {0,1} = task i in time slot t; Σ_t x_{it} = 1 for each task; Σ_i x_{it} ≤ m for each slot t; precedence: Σ_t t·x_{jt} ≥ Σ_t t·x_{it} + 1 for each (i,j) ∈ precedences.)
• Other: Coffman-Graham algorithm for m = 2 [Coffman & Graham, 1972]; Hu's algorithm for forest precedences [Hu, 1961].

Example Instance

Input:
n = 8 tasks: T = {t_1, t_2, t_3, t_4, t_5, t_6, t_7, t_8}
m = 3 processors, D = 4 time slots.
Precedences:

• t_1 < t_3
• t_1 < t_4
• t_2 < t_4
• t_2 < t_5
• t_3 < t_6
• t_4 < t_7
• t_5 < t_7
• t_6 < t_8
• t_7 < t_8

Feasible schedule:

Time slot	Tasks (up to 3 per slot)
1	t_1, t_2
2	t_3, t_4, t_5
3	t_6, t_7
4	t_8

Check precedences:

• t_1(1) < t_3(2) ✓, t_1(1) < t_4(2) ✓
• t_2(1) < t_4(2) ✓, t_2(1) < t_5(2) ✓
• t_3(2) < t_6(3) ✓, t_4(2) < t_7(3) ✓
• t_5(2) < t_7(3) ✓, t_6(3) < t_8(4) ✓
• t_7(3) < t_8(4) ✓

Processor capacity: max tasks per slot = 3 ≤ m = 3 ✓
All tasks complete by slot 4 = D ✓

Answer: YES — a valid 3-processor schedule meeting deadline D = 4 exists.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel scheduling problem not in reduction graph; has planned reduction from 3SAT
Non-trivial	✅ Pass	Distinct multiprocessor scheduling problem with precedence + capacity + deadline constraints
Correctness	✅ Pass	All references verified (Ullman 1975, Coffman & Graham 1972, Lenstra & Rinnooy Kan 1978)
Well-written	⚠️ Warn	No concrete complexity string for declare_variants!; Bodlaender & Fellows citation incomplete

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

The problem does not exist in the current codebase. It is a fundamental NP-complete multiprocessor scheduling problem from Garey & Johnson (A5 SS9) with at least one planned reduction rule (3SAT -> PrecedenceConstrainedScheduling). The scheduling domain is currently unrepresented in the reduction graph. Pass.

Non-trivial

This is a genuinely distinct problem. The feasibility constraint combines: (1) precedence constraints (partial order), (2) processor capacity (at most m tasks per time slot), and (3) a deadline bound D. No existing problem has this combination. The closest existing problems are graph-based or set-based — this has a fundamentally different input structure (DAG + integer parameters). Pass.

Correctness

• Ullman (1975): Verified. "NP-Complete Scheduling Problems," Journal of Computer System Sciences, Vol. 10, No. 3, 1975, pp. 384-393. Establishes NP-completeness of precedence-constrained scheduling via reduction from 3SAT. ✅
• Coffman & Graham (1972): Verified. The Coffman-Graham algorithm solves the 2-processor case optimally in O(n^2) time. Published in Acta Informatica 1(3), 1972. ✅
• Lenstra & Rinnooy Kan (1978): Verified. "Complexity of scheduling under precedence constraints," Operations Research 26(1), 1978. Establishes NP-completeness for D = 3. ✅
• Hu (1961): Well-known result for forest-structured precedences. ✅
• Papadimitriou & Yannakakis (1978): Chordal complement precedences result. ✅
• Bodlaender & Fellows: ⚠️ Citation is incomplete — no year, no paper title. The O(n^3 + n * w * 2^{4w}) FPT bound needs a full citation.

Well-written

Mostly complete and well-structured, with minor issues:

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

2. No concrete complexity string: The Complexity section is narrative but does not provide a parseable expression for declare_variants!. The brute-force bound O(D^n) is mentioned. A concrete string like "deadline ^ num_tasks" would be needed.

3. Bodlaender & Fellows citation: Missing year and paper title. Should be completed for verifiability.

4. Schema design: Clean and minimal. The precedences field as Vec<(usize, usize)> is appropriate for a DAG edge list. The num_tasks field is slightly redundant if it can be inferred from the maximum index in precedences, but having it explicit is fine for clarity.

5. Example: Well-constructed with 8 tasks, 3 processors, deadline 4. All precedence checks are shown step by step. The table format is clear. ✅

6. Variables section: Correctly identifies the domain as {1, ..., D} per task, with capacity and precedence constraints. ✅

Recommendations

• Complete the Bodlaender & Fellows citation with year and paper title.
• Add a concrete complexity string suitable for declare_variants!.