[Model] PreemptiveScheduling

[isPANN]

Important

Build as optimization, not decision. Value = Min<usize>.
Objective: Minimize makespan (completion time of the last task) with preemption allowed.
Do not add a bound/threshold field — let the solver find the optimum directly. See #765.

Motivation

PREEMPTIVE SCHEDULING (P196) from Garey & Johnson, A5 SS12. A fundamental NP-hard multiprocessor scheduling problem that allows tasks to be interrupted and resumed later (preemption), while requiring precedence constraints to be respected. Despite the flexibility of preemption, the problem remains NP-complete in general (reduction from 3SAT). Polynomial-time solvable for m = 2 processors, forest-structured precedence, or empty precedence with individual deadlines.

Associated rules:

• R141: 3SAT → PreemptiveScheduling (this model is the target)

Definition

Name: PreemptiveScheduling
Reference: Garey & Johnson, Computers and Intractability, A5 SS12

Mathematical definition:

INSTANCE: Set T of n tasks, number m ∈ Z⁺ of processors, partial order ≺ on T (precedence constraints), and for each t ∈ T a length l(t) ∈ Z⁺.

OBJECTIVE: Find an m-processor preemptive schedule σ that obeys the precedence constraints and minimizes the makespan (completion time of the last task).

A preemptive schedule allows subdividing each task t into subtasks t₁, t₂, …, tₖ with Σ l(tᵢ) = l(t), where subtasks run non-overlapping on any processor. At most m tasks may be processed simultaneously. Precedence constraints require that all subtasks of t complete before any subtask of t' whenever t ≺ t'.

The makespan lower bound is max(max_t l(t), ⌈Σ l(t) / m⌉, critical_path_length).

The corresponding decision problem (GJ SS12) asks whether a schedule exists with makespan ≤ D for a given deadline D ∈ Z⁺.

Variables

• Count: n × D_max, where D_max = Σ l(t) (upper bound on makespan). Each variable x_{t,u} indicates whether task t is being processed at time slot u.
• Per-variable domain: {0, 1} (binary: processing or not at this time slot)
• Meaning: config[t × D_max + u] = 1 means task t is being processed at time u. A valid schedule satisfies: (1) Σ_u x_{t,u} = l(t) for all tasks, (2) Σ_t x_{t,u} ≤ m for all time slots, (3) precedence constraints are respected (all time slots for predecessor t complete before any time slot for successor t'). The makespan is the last time slot u with any x_{t,u} = 1.

dims() returns [2; n × D_max].

Schema (data type)

Type name: PreemptiveScheduling
Variants: none (no type parameters)

Field	Type	Description	Getter
lengths	Vec<usize>	Processing time l(t) for each task t	num_tasks() → self.lengths.len()
num_processors	usize	Number of identical processors m	num_processors()
precedences	Vec<(usize, usize)>	Edges (i, j) of the precedence DAG	num_precedences() → self.precedences.len()

Problem type: Optimization (minimization)
Value type: Min<usize>

Complexity

• Decision complexity: NP-complete by reduction from 3SAT (Ullman, 1975), even with unit-length tasks.
• Best known exact algorithm: ILP or constraint programming formulations. Brute-force over all possible time-slot assignments is O(2^(n·D_max)).
• Complexity string for declare_variants!: "2^(num_tasks * num_tasks)" (brute-force over binary schedule matrices; D_max ≤ Σ l(t) ≤ n · max_l ≤ n²)
• Special cases:
  • m = 2 processors: polynomial (Muntz & Coffman, 1969)
  • Forest precedence: polynomial (Muntz & Coffman, 1970)
  • Empty precedence with individual deadlines: polynomial (Horn, 1974)
• References:
  • [Ullman, 1975] J. D. Ullman, "NP-complete scheduling problems", JCSS 10, 1975.
  • [Muntz & Coffman, 1969] R. R. Muntz and E. G. Coffman, "Optimal preemptive scheduling on two-processor systems", IEEE Trans. Computers, 1969.
  • [Muntz & Coffman, 1970] R. R. Muntz and E. G. Coffman, "Preemptive scheduling of real-time tasks on multiprocessor systems", JACM 17(2), 1970.
  • [Horn, 1974] W. A. Horn, "Some simple scheduling algorithms", Naval Research Logistics Quarterly 21, 1974.

Extra Remark

Full book text:

INSTANCE: Set T of tasks, number m in Z+ of processors, partial order < on T, length l(t) in Z+ for each t in T, and an overall deadline D in Z+.
QUESTION: Is there an m-processor "preemptive" schedule for T that obeys the precedence constraints and meets the overall deadline? (Such a schedule sigma is identical to an ordinary m-processor schedule, except that we are allowed to subdivide each task t in T into any number of subtasks t1, t2, ..., tk such that sum_{i=1}^{k} l(ti) = l(t) and it is required that sigma(ti + 1) >= sigma(ti)+l(ti) for 1 <= i < k. The precedence constraints are extended to subtasks by requiring that every subtask of t precede every subtask of t' whenever t < t'.)

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

Comment: Can be solved in polynomial time if m = 2 [Muntz and Coffman, 1969], if < is a "forest" [Muntz and Coffman, 1970], or if < is empty and individual task deadlines are allowed [Horn, 1974].

Note: The original GJ formulation is a decision problem with deadline D. This issue reformulates it as an optimization problem (minimize makespan). The decision version is recovered by checking whether the optimal makespan ≤ D.

How to solve

• It can be solved by (existing) bruteforce. The search space 2^(n·D_max) is too large for practical brute-force enumeration.
• It can be solved by reducing to integer programming. Binary ILP: x_{t,u} ∈ {0,1} for each task t and time slot u; Σ_u x_{t,u} = l(t); Σ_t x_{t,u} ≤ m; precedence ordering constraints; minimize makespan variable.
• Other: Polynomial-time algorithms for special cases (m=2, forest precedence, empty precedence).

Example Instance

Input:
T = {t₁, t₂, t₃, t₄, t₅} (n = 5 tasks), m = 2 processors
Lengths: l(t₁) = 2, l(t₂) = 1, l(t₃) = 3, l(t₄) = 2, l(t₅) = 1
Precedences: t₁ ≺ t₃, t₂ ≺ t₄

Total work = 2 + 1 + 3 + 2 + 1 = 9.
Work lower bound: ⌈9/2⌉ = 5.
Critical path: max(l(t₁)+l(t₃), l(t₂)+l(t₄)) = max(2+3, 1+2) = 5.
Lower bound: max(5, 5) = 5.

Optimal preemptive schedule (makespan = 5):

Time	Proc 1	Proc 2	Notes
0	t₁ (1/2)	t₂ (1/1 ✓)	t₂ completes
1	t₁ (2/2 ✓)	t₅ (1/1 ✓)	t₁, t₅ complete
2	t₃ (1/3)	t₄ (1/2)	t₁ done → t₃ eligible; t₂ done → t₄ eligible
3	t₃ (2/3)	t₄ (2/2 ✓)	t₄ completes
4	t₃ (3/3 ✓)	idle	t₃ completes

Makespan = 5 = lower bound. Optimal.

Suboptimal feasible schedule (makespan = 6):

Time	Proc 1	Proc 2
0	t₂ (✓)	t₅ (✓)
1	t₁ (1/2)	idle
2	t₁ (✓)	t₄ (1/2)
3	t₃ (1/3)	t₄ (✓)
4	t₃ (2/3)	idle
5	t₃ (✓)	idle

Makespan = 6 > 5. Valid but suboptimal (t₁ starts late, wasting processor capacity).

Expected outcome: Min(5)

Reduction Rule Crossref

• R141: Satisfiability (3SAT) → PreemptiveScheduling
• Direct ILP: PreemptiveScheduling → ILP (binary time-slot assignment model)

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph; associated rule R141 (3SAT → PreemptiveScheduling) planned
Non-trivial	✅ Pass	Distinct scheduling problem with preemption, precedence, and deadlines — not isomorphic to any existing model
Correctness	✅ Pass	Ullman 1975 (JCSS 10(3):384–393) verified; Muntz & Coffman 1969/1970 verified; Garey & Johnson A5 SS12 consistent
Well-written	❌ Fail	Example section contains multiple failed drafts; no concrete best-known complexity bound; symbol inconsistencies

Overall: 3 passed, 0 warnings, 1 failed

---

Usefulness

PreemptiveScheduling does not exist in the current codebase. The problem is a classic NP-complete scheduling problem from Garey & Johnson (A5 SS12) with a planned reduction from 3SAT (R141), which would connect it to the existing formula-based problems.

Non-trivial

This is a genuinely distinct problem. The input structure (task set with precedence DAG, processor count, task lengths, deadline) differs fundamentally from all existing models:

• Not a graph optimization problem (MIS, MaxClique, etc.)
• Not a formula/circuit problem (SAT, CircuitSAT)
• Not a set system (SetCovering, SetPacking)
• Not an algebraic problem (QUBO, ILP, CVP)
• The preemption mechanism (tasks can be split across time slots and processors) adds structural complexity beyond standard multiprocessor scheduling.

Correctness

All cited references verified:

• Ullman, 1975: "NP-complete scheduling problems," JCSS 10(3):384–393. Confirms NP-completeness of preemptive scheduling via reduction from 3SAT (which Ullman also defines in the same paper). The claim about unit-length tasks being NP-complete is also supported.
• Muntz & Coffman, 1969/1970: Two papers on optimal preemptive scheduling. The 1969 paper (IEEE Trans. Computers) covers two-processor systems; the 1970 paper (JACM) covers the level algorithm for trees. Polynomial-time claims verified.
• Horn, 1974: Known result for empty precedence with individual deadlines — consistent with the literature.
• Garey & Johnson, 1979: A5 SS12 classification confirmed.

No issues found with the correctness of cited results.

Well-written

Failures:

1. Example section is poorly presented. The section contains three failed attempts at constructing a valid schedule, visible as "Revised:", "Revised again:", crossed-out reasoning, and inline debugging ("Wait, let me preempt t_3"). The final example works but the drafting process should have been cleaned up before submission. An issue example should show only the final, correct worked instance.

2. No specific best-known complexity bound. The Complexity section says "No known improvement over O*(2^(n*D)) brute-force enumeration" — this is not a best-known algorithm citation but rather a trivial upper bound. For declare_variants!, a concrete complexity string is needed. The issue should either:

   • Cite a specific exact algorithm with a proven bound, or
   • State that the trivial O*(2^(n*D)) bound is the best known with a citation confirming no improvement exists.

3. Symbol inconsistency. The Variables section introduces a binary formulation x_{t,p,u} (task × processor × time), but this 3-index formulation is never referenced in the Schema or Example sections. The Schema uses simpler fields. The Variables section should align with the actual implementation strategy.

4. Pervasive "Unverified" warnings. Multiple sections carry <!-- Unverified: AI-generated --> disclaimers, indicating the content has not been human-reviewed. While not a structural defect, it reduces confidence.

Recommendations

• Clean up the Example section to show only the final correct instance with a clear step-by-step schedule.
• Research whether there is a better exact algorithm than brute-force for general preemptive scheduling (e.g., ILP-based approaches or FPT algorithms parameterized by number of processors).
• Align the Variables section with the Schema — either use x_{t,u} (binary, task × time) matching the simpler schema, or expand the schema to include processor assignment.

[isPANN]

Implementation note: build as optimization

This model should be implemented as an optimization problem (Value = Min<usize> or similar), not a decision problem with a bound field.

• Objective: Minimize makespan (completion time of the last task) with preemption allowed, subject to precedence constraints
• Do not add a deadline D as a threshold — let the solver find the minimum makespan directly
• Same family as JobShopScheduling ([Model] JobShopScheduling #510) and OpenShopScheduling ([Model] OpenShopScheduling #506) — all should be Min(makespan)

See #765 for context on the decision-vs-optimization policy.

[isPANN]

Issue Quality Check — Model

(Re-check after implementation note re: optimization redesign)

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph; associated rule R141 (3SAT → PreemptiveScheduling) planned
Non-trivial	✅ Pass	Distinct from PrecedenceConstrainedScheduling (variable task lengths + preemption mechanism)
Correctness	✅ Pass	Ullman 1975 (JCSS 10(3):384–393) verified; Muntz & Coffman 1969/1970 verified
Well-written	❌ Fail	Example has multiple failed drafts; inconsistent with optimization redesign; example too tight for round-trip testing

Overall: 3 passed, 0 warnings, 1 failed

Previously (2026-03-12): 3 passed, 1 failed (Well-written) → Now: 3 passed, 1 failed (Well-written) — same verdict, but new failure items from the optimization redesign.

---

Usefulness

PreemptiveScheduling does not exist in the current codebase. It is distinct from the existing PrecedenceConstrainedScheduling (which has unit-length tasks and no preemption). The planned reduction from 3SAT (R141) connects it to the formula-based subgraph.

Non-trivial

The input structure (task set with variable lengths, precedence DAG, processor count, and preemption capability) differs meaningfully from all existing scheduling models:

• PrecedenceConstrainedScheduling — unit-length tasks, no preemption
• MultiprocessorScheduling — no precedence, no preemption
• FlowShopScheduling / JobShopScheduling — machine-sequence constraints, not precedence DAGs with preemption

The preemption mechanism (tasks can be split across time slots and processors) is a genuine structural addition.

Correctness

All cited references verified:

• Ullman, 1975: "NP-Complete Scheduling Problems," JCSS 10(3):384–393. Confirms NP-completeness of preemptive scheduling via reduction from 3SAT. Paper is already in the project bibliography (ullman1975).
• Muntz & Coffman, 1969: IEEE Transactions on Computers 18(11):1014–1020, on optimal two-processor preemptive scheduling. Claim verified.
• Muntz & Coffman, 1970: JACM 17(2):324–338, level algorithm for tree-structured precedence. Claim verified.
• Horn, 1974: Known result for empty precedence with individual deadlines — consistent with scheduling literature.
• Garey & Johnson, 1979: A5 SS12 classification confirmed.

No contradictions found with the project knowledge base or external sources.

Well-written

Failures:

1. Example section contains multiple failed drafts. The example shows three abandoned attempts with inline debugging ("Revised:", "Revised again:", "Wait, let me preempt t_3"). Only the final instance is correct, but the drafting artifacts should be cleaned up.

2. Inconsistency with optimization redesign. The implementation note (comment by @isPANN) specifies Value = Min<usize> with no deadline field — minimize makespan directly. However, the entire issue body is written around the decision formulation with deadline D. Sections that need updating:

   • Definition: Currently asks "Is there a schedule meeting deadline D?" — should ask "What is the minimum makespan?"
   • Schema: The deadline field should be removed per the redesign
   • Variables: The formulation uses x_{t,p,u} indexed over time slots 0..D-1, which depends on a deadline bound
   • Example: Framed as "YES/NO, does a schedule exist within D=4?" — should instead state the optimal makespan

3. Example lacks round-trip testing diversity. Python verification confirms:

   • The final example (n=5, m=2, lengths=[2,2,2,1,1], precedences: t1<t4, t2<t5) has optimal makespan = 4
   • Total work = 8 = 2×4 = m×makespan, so this is a tight instance where every feasible schedule that fits within D=4 is automatically optimal
   • There are 12 feasible schedules at D=4, all with makespan exactly 4 — zero suboptimal feasible solutions
   • For the optimization formulation, a round-trip test cannot distinguish a correct reduction from one that returns any feasible schedule, since all feasible schedules are optimal
   • Recommendation: use an instance where total work < m×D and precedence constraints force suboptimal makespans

4. No concrete complexity bound for declare_variants!. The Complexity section says "No known improvement over O*(2^(n*D)) brute-force enumeration." For the optimization version (no deadline D), the complexity parameter should be expressed in terms of problem size fields only (e.g., num_tasks, num_processors). A complexity string like 2^(num_tasks * D) is not valid when D is removed from the schema.

5. Pervasive "Unverified" warnings. Multiple sections carry <!-- Unverified: AI-generated --> disclaimers, reducing confidence in the content.

Recommendations

• Rewrite the issue body to match the optimization formulation: remove deadline from schema, redefine the objective as minimizing makespan, and update the example to show the optimal makespan value.
• Replace the example with one that has multiple distinct feasible makespans. For instance, use an instance where precedence constraints force some schedules to have strictly larger makespan than the optimum.
• Research FPT algorithms for preemptive scheduling parameterized by number of processors or number of precedence edges, which may give a tighter complexity bound than brute-force.
• Clean up all draft artifacts and remove "Unverified" markers after human review.

[isPANN]

Issue Quality Check — Model (Re-check)

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph; planned 3SAT → PreemptiveScheduling reduction (R141)
Non-trivial	✅ Pass	Distinct from all 7 existing scheduling models — preemption + precedence DAG + variable task lengths
Correctness	✅ Pass	Ullman 1975 (JCSS 10(3):384–393) verified in project bibliography; Muntz & Coffman refs verified
Well-written	❌ Fail	Example contains multiple failed drafts; body inconsistent with optimization redesign; example too tight for round-trip testing; no concrete complexity bound

Overall: 3 passed, 0 warnings, 1 failed

Previous checks: 2026-03-12 (3 passed, 1 failed — Well-written), 2026-03-29 (3 passed, 1 failed — Well-written). → No change in verdict. The issue body has not been updated since the last re-check. All previously identified Well-written failures remain.

---

Usefulness

PreemptiveScheduling does not exist in the codebase (confirmed via pred show). The problem is distinct from the 7 existing scheduling models: FlowShopScheduling, JobShopScheduling, MultiprocessorScheduling, PrecedenceConstrainedScheduling, ResourceConstrainedScheduling, SchedulingWithIndividualDeadlines, StaffScheduling. The planned reduction from 3SAT (R141) would connect it to the formula-based subgraph.

Non-trivial

The preemption mechanism (tasks can be split across non-contiguous time slots and different processors) is a genuine structural feature not present in any existing model:

• PrecedenceConstrainedScheduling — unit-length tasks, no preemption
• MultiprocessorScheduling — no precedence, no preemption
• FlowShopScheduling / JobShopScheduling — machine-sequence constraints, not precedence DAGs with preemption

Correctness

All cited references verified:

• Ullman, 1975: "NP-Complete Scheduling Problems," JCSS 10(3):384–393. Already in project bibliography (ullman1975). Confirms NP-completeness of preemptive scheduling via reduction from 3SAT.
• Muntz & Coffman, 1969/1970: Polynomial-time results for m=2 and tree-structured precedence. Consistent with the literature.
• Horn, 1974: Empty precedence with individual deadlines. Consistent.
• Garey & Johnson, 1979: A5 SS12 classification confirmed.

Well-written

Failures (unchanged from previous check):

1. Example section contains multiple failed drafts. The body shows three abandoned attempts with inline debugging ("Revised:", "Revised again:", "Wait, let me preempt t_3"). Only the final instance is correct, but the drafting artifacts must be cleaned up.

2. Inconsistency with optimization redesign. The implementation note (comment by @isPANN, 2026-03-24) specifies Value = Min<usize> with no deadline field. However, the entire issue body still uses the decision formulation with deadline D. Sections needing update:

   • Definition: Still asks "Is there a schedule meeting deadline D?" — should minimize makespan
   • Schema: Still includes deadline field — should be removed
   • Variables: Uses x_{t,p,u} indexed over 0..D-1 — depends on a deadline bound
   • Example: Framed as YES/NO within D=4 — should state optimal makespan value

3. Example too tight for round-trip testing. Python verification confirms:

   • Optimal makespan = 4, total work = 8 = 2 × 4 = m × makespan (tight)
   • At D=4: 12 feasible schedules, all with makespan exactly 4 — zero suboptimal feasible solutions
   • A buggy reduction that returns any feasible schedule would pass a round-trip test
   • Need an instance where precedence constraints force some schedules to have strictly larger makespan

4. No concrete complexity bound for declare_variants!. The Complexity section says "No known improvement over O*(2^(n*D)) brute-force enumeration" — this is a trivial upper bound, not a best-known algorithm citation. For the optimization version (no deadline D in schema), the complexity parameter cannot reference D.

5. Pervasive unverified markers. Multiple sections carry <!-- Unverified: AI-generated --> disclaimers.

Recommendations

• Rewrite the issue body to match the optimization formulation: remove deadline, define objective as minimizing makespan, update example to report optimal makespan value.
• Replace the example with one that has multiple distinct feasible makespans (e.g., add asymmetric precedence chains that force idle time, so total_work < m × optimal_makespan).
• Research FPT or ILP-based exact algorithms for preemptive scheduling that give tighter complexity bounds than brute-force.
• Clean up all draft artifacts and remove unverified markers.

[isPANN]

Fix-issue changelog

• Replaced broken example (multiple failed draft attempts) with clean 5-task, 2-processor instance
• New example: optimal makespan = 5 (= lower bound), suboptimal at 6, verified by Python
• Reformulated as optimization (removed deadline field, Value = Min<usize>)
• Added getter methods (num_tasks(), num_processors(), num_precedences())
• Added complexity string 2^(num_tasks * num_tasks) for declare_variants!
• Unchecked brute-force (search space too large), ILP as primary solver
• Removed all "Unverified" markers from verified content
• Added important banner per Upgrade 17 decision models to optimization versions #765 convention
• Cleaned up Definition with explicit lower bound formula

Applied by /fix-issue.