[Model] JobShopScheduling

[isPANN]

Important

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

Motivation

JOB-SHOP SCHEDULING (P202) from Garey & Johnson, A5 SS18. One of the most studied NP-hard combinatorial optimization problems: given m processors and a set of jobs, each consisting of an ordered sequence of tasks with specified processor assignments and lengths, find a schedule that minimizes the makespan (completion time of the last task). Unlike flow-shop scheduling, each job can have a different machine routing, and consecutive tasks of the same job must be on different processors. NP-hard in the strong sense even for m = 2 [Garey, Johnson, and Sethi, 1976]. Solvable in polynomial time for m = 2 with at most 2 tasks per job [Jackson, 1956].

This should be implemented as an optimization problem (Value = Min<u64>).

Associated rules:

• R147: 3-PARTITION -> JOB-SHOP SCHEDULING (establishes strong NP-completeness for m = 2)

Definition

Name: JobShopScheduling

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

Mathematical definition:

INSTANCE: Number m in Z+ of processors, set J of jobs, each j in J consisting of an ordered collection of tasks t_k[j], 1 <= k <= n_j, for each such task t a length l(t) in Z0+ and a processor p(t) in {1,2,...,m}, where p(t_k[j]) != p(t_{k+1}[j]) for all j in J and 1 <= k < n_j.
OBJECTIVE: Find start times sigma(t_k[j]) in Z0+ such that tasks sharing a processor do not overlap (sigma_i(t) > sigma_i(t') implies sigma_i(t) >= sigma_i(t') + l(t')), each job respects precedence (sigma(t_{k+1}[j]) >= sigma(t_k[j]) + l(t_k[j])), and the makespan max_{j in J} (sigma(t_{n_j}[j]) + l(t_{n_j}[j])) is minimized.

Note: The constraint p(t_k[j]) != p(t_{k+1}[j]) (consecutive tasks of the same job must be on different processors) is part of the original Garey & Johnson formulation. Some modern job-shop formulations relax this constraint; this implementation follows the G&J definition.

Variables

• Count: One variable per task, grouped by machine. Total = sum of tasks per machine.
• Per-variable domain: Lehmer-code radices — for a machine with k tasks assigned, the radices are (k, k-1, ..., 1).
• Meaning: Each variable selects the next task from the remaining unplaced tasks on that machine, encoding a permutation of machine task orders. The schedule is reconstructed by propagating longest paths through the combined job-precedence + machine-order DAG.

Schema (data type)

Type name: JobShopScheduling
Variants: none (task lengths are non-negative integers)

Field	Type	Description
num_processors	usize	Number of machines m
jobs	Vec<Vec<(usize, u64)>>	jobs[j][k] = (processor, length) for the k-th task of job j

Complexity

• Best known exact algorithm: For m = 2 with n_j <= 2 for all j, solvable in polynomial time by Jackson's rule [Jackson, 1956]. For the general case (m >= 2 with arbitrary task counts), strongly NP-hard. The best known exact approaches use dynamic programming (Gromicho et al., 2012) or branch-and-bound (Brucker et al., 1994). Brute-force requires examining all possible orderings of tasks on each machine, giving factorial complexity.
• Complexity expression: factorial(num_tasks) (brute-force bound over machine-order permutations)

Extra Remark

Full book text:

INSTANCE: Number m in Z+ of processors, set J of jobs, each j in J consisting of an ordered collection of tasks t_k[j], 1 <= k <= n_j, for each such task t a length l(t) in Z0+ and a processor p(t) in {1,2,...,m}, where p(t_k[j]) != p(t_{k+1}[j]) for all j in J and 1 <= k < n_j, and a deadline D in Z+.
QUESTION: Is there a job-shop schedule for J that meets the overall deadline, i.e., a collection of one-processor schedules sigma_i mapping {t: p(t) = i} into Z0+, 1 <= i <= m, such that sigma_i(t) > sigma_i(t') implies sigma_i(t) >= sigma_i(t') + l(t), such that sigma(t_{k+1}[j]) >= sigma(t_k[j]) + l(t_k[j]) for all j in J and 1 <= k < n_j, and such that for all j in J sigma(t_{n_j}[j]) + l(t_{n_j}[j]) <= D?

Reference: [Garey, Johnson, and Sethi, 1976]. Transformation from 3-PARTITION.

Comment: NP-complete in the strong sense for m = 2. Can be solved in polynomial time if m = 2 and n_j <= 2 for all j in J [Jackson, 1956]. NP-complete (in the ordinary sense) if m = 2 and n_j <= 3 for all j in J, or if m = 3 and n_j <= 2 for all j in J [Gonzalez and Sahni, 1978a]. All the above results continue to hold if "preemptive" schedules are allowed [Gonzalez and Sahni, 1978a]. If in the nonpreemptive case all tasks have the same length, the problem is NP-complete for m = 3 and open for m = 2 [Lenstra and Rinnooy Kan, 1978b].

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all possible machine-order permutations; compute makespan via longest-path propagation.)
• It can be solved by reducing to integer programming. (ILP with start-time variables sigma(t), precedence constraints, and disjunctive constraints for tasks sharing a machine: for each pair (t, t') on the same machine, either sigma(t) + l(t) <= sigma(t') or sigma(t') + l(t') <= sigma(t). Minimize makespan.)
• Other: Disjunctive graph / branch-and-bound (Brucker et al., 1994); constraint programming.

Example Instance

Input:
m = 2 processors, J = {j_1, j_2, j_3, j_4, j_5} (n = 5 jobs).

Job	Task 1 (proc, len)	Task 2 (proc, len)	Task 3 (proc, len)
j_1	(P1, 3)	(P2, 4)	--
j_2	(P2, 2)	(P1, 3)	(P2, 2)
j_3	(P1, 4)	(P2, 3)	--
j_4	(P2, 5)	(P1, 2)	--
j_5	(P1, 2)	(P2, 3)	(P1, 1)

Total tasks: 12. Search space: 6! x 6! = 518400 machine-order permutations.

Optimal schedule (makespan = 19):
P1: j_1.t1[0,3], j_2.t2[3,6], j_3.t1[6,10], j_4.t2[10,12], j_5.t1[12,14], j_5.t3[17,18]
P2: j_2.t1[0,2], j_4.t1[2,7], j_1.t2[7,11], j_3.t2[11,14], j_5.t2[14,17], j_2.t3[17,19]

Machine 0 Lehmer order: [0,0,0,0,0,0], Machine 1 Lehmer order: [1,3,0,1,1,0]
Config: [0,0,0,0,0,0,1,3,0,1,1,0]
Optimal value: Min(19)

Job completion times: j_1 at 11, j_2 at 19, j_3 at 14, j_4 at 12, j_5 at 18.
Precedence: each job's tasks execute in order. ✓
No overlap on each machine. ✓
Consecutive tasks of each job are on different processors (by construction). ✓

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; classic scheduling problem from Garey & Johnson
Non-trivial	✅ Pass	Distinct feasibility constraints (machine routing, precedence, deadline) from all existing problems
Correctness	❌ Fail	Example schedule contains a precedence violation (j_5); complexity section lacks a concrete bound
Well-written	⚠️ Warn	Minor notation issues and missing complexity expression

Overall: 2 passed, 1 failed, 1 warning

---

Usefulness

JobShopScheduling does not exist in the codebase. It is a classic NP-hard scheduling problem (Garey & Johnson A5 SS18) distinct from all currently implemented problems. The motivation mentions an associated rule (3-PARTITION → JobShopScheduling) which would connect it to the reduction graph. The problem has widespread practical importance in manufacturing and operations research. Pass.

Non-trivial

The problem has genuinely distinct feasibility constraints from all existing problems in the codebase: machine-assignment of tasks, precedence ordering within jobs, no-overlap on machines, and a global deadline. This is not a variant or relabeling of any existing problem. Pass.

Correctness

References:

• Garey, Johnson, and Sethi (1976) — "The Complexity of Flowshop and Jobshop Scheduling," Mathematics of Operations Research, 1(2), 117–129. ✅ Verified. This paper establishes NP-completeness of job-shop scheduling. The claim that it is "NP-complete in the strong sense even for m = 2" is supported by the literature (the strong NP-completeness for m ≥ 2 is via reduction from 3-PARTITION).

• Jackson (1956) — "An Extension of Johnson's Results on Job Lot Scheduling." ✅ Verified. Jackson showed polynomial-time solvability for 2-machine job-shop with at most 2 tasks per job.

• Gromicho et al. (2012) and Brucker et al. (1994) — mentioned in the Complexity section as exact approaches. These are real papers but no specific time bounds are cited from them.

Example schedule error (❌ Fail):

The example schedule has a precedence violation for job j_5:

• j_5.t2 is scheduled on P2 at [14, 17] (finishes at time 17)
• j_5.t3 is scheduled on P1 at [14, 15] (starts at time 14)
• But j_5.t3 must start after j_5.t2 finishes (precedence constraint), so j_5.t3 cannot start before time 17.

This makes the claimed schedule infeasible.

Complexity section (⚠️):

The Complexity section discusses various algorithms but does not provide a concrete declare_variants!-compatible complexity string (e.g., "2^num_tasks" or similar). For implementation, a specific bound like O*(D^T) or O*(T!) would be needed for the brute-force or best-known exact algorithm.

Well-written

4a: Information Completeness — All required template sections are present. ✅

4b: Definition Completeness — The formal definition is well-formed, directly from Garey & Johnson. The decision problem formulation with a deadline D is clear. ✅

4c: Symbol and Notation Consistency:

• The Variables section defines T = sum_{j in J} n_j but this symbol is also used in the Complexity section as "O*(2^T)" — consistent. ✅
• The Schema section uses u64 for lengths and deadline, which is reasonable. ✅
• The constraint p(t_k[j]) != p(t_{k+1}[j]) (consecutive tasks of the same job must be on different processors) is included in the definition — this is a distinctive feature of the Garey & Johnson formulation, but some standard job-shop formulations do NOT require this. This should be clarified as it affects implementation. ⚠️

4d: Example Quality:

• The example is non-trivial (5 jobs, 2 machines, up to 3 tasks per job) ✅
• However, as noted above, the schedule is infeasible due to precedence violation ❌
• A corrected schedule should be provided

Recommendations

• Fix the example schedule — j_5.t3 must start at or after time 17 (after j_5.t2 finishes at 17), which means the schedule likely needs rearranging or the deadline needs increasing
• Add a concrete complexity expression for declare_variants! (e.g., "num_tasks!" for brute-force, or a specific exponential bound from the literature)
• Clarify whether the constraint that consecutive tasks must be on different processors is intentional (it matches Garey & Johnson's original formulation but is more restrictive than many modern job-shop formulations)
• The problem is a decision/satisfaction problem (Metric = bool), which should be explicitly stated in the issue

[isPANN]

Issue Quality Check — Model (Re-check)

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; planned rule R147 (3-PARTITION → JobShopScheduling)
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems including FlowShopScheduling
Correctness	⚠️ Warn	All 6 references verified; O*(2^T) complexity claim is imprecise — not a stated literature result
Well-written	❌ Fail	Example schedule has a precedence violation; missing concrete complexity expression

Overall: 2 passed, 1 warning, 1 failed

Previously (2026-03-12): 2 passed, 1 failed (Correctness), 1 warning (Well-written). This re-check reclassifies the example error under Well-written (where it belongs per the check structure) and downgrades Correctness to a warning since all references are legitimate.

---

Usefulness

JobShopScheduling does not exist in the codebase (pred show returns "Unknown problem"). The closest existing problem is FlowShopScheduling, which is fundamentally different: flow-shop requires all jobs to visit machines in the same fixed order, while job-shop allows each job to have a different machine routing. The issue mentions R147 (3-PARTITION → JobShopScheduling) as a planned rule, which would connect it to the reduction graph. Classic NP-hard scheduling problem from Garey & Johnson A5 SS18. Pass.

Non-trivial

Job-shop scheduling has genuinely distinct feasibility constraints from all 112 existing problem types:

• Per-job machine routing (each job specifies its own processor sequence)
• Precedence ordering within jobs (task k+1 starts after task k finishes)
• No-overlap on each machine (disjunctive constraints)
• Consecutive tasks of the same job must be on different processors (G&J formulation)
• Global deadline constraint

This is not a variant, relabeling, or restriction of FlowShopScheduling or any other existing problem. Pass.

Correctness

Reference verification (all 6 confirmed):

#	Reference	Verified	Notes
1	Garey, Johnson, Sethi (1976)	✅	Math. of Operations Research 1(2):117-129. Strong NP-completeness for m ≥ 2 via 3-PARTITION confirmed
2	Jackson (1956)	✅	Naval Research Logistics Quarterly 3:201-203. Poly-time for m=2, n_j ≤ 2 confirmed
3	Gonzalez & Sahni (1978a)	✅	Operations Research 26(1):36-52. NP-complete for m=2/n_j≤3 and m=3/n_j≤2 confirmed
4	Lenstra & Rinnooy Kan (1978b)	✅	Operations Research 26(1):22-35. Unit-length task results confirmed
5	Gromicho et al. (2012)	✅	Computers & OR 39(12):2968-2977. DP approach adapting Held-Karp confirmed
6	Brucker et al. (1994)	✅	Discrete Applied Math. 49:107-127. Branch-and-bound confirmed

Complexity claim (⚠️): The issue states "O*(2^T) where T is the total number of tasks" via Held-Karp style DP. This is not a precisely stated result from the literature. Gromicho et al. (2012) adapted the Held-Karp Bellman equation but their actual complexity is more nuanced than a clean O*(2^T) — the state space for job-shop is more complex than TSP because it must encode per-machine scheduling information. The issue should either cite Gromicho et al.'s actual complexity theorem or soften the claim.

Definition correctness: The formal definition is taken directly from Garey & Johnson and is mathematically well-formed. ✅

Representation feasibility (3e): usize for processors, u64 for lengths/deadline, Vec<Vec<(usize, u64)>> for jobs — can represent all standard job-shop instances. ✅

Well-written

4a: Information Completeness — All required template sections are present. ✅

4b: Definition Completeness — The formal definition from G&J is precise and implementable. The decision problem formulation with deadline D is clear. ✅

4c: Symbol/Notation Consistency:

• Symbols are generally consistent across sections ✅
• The constraint p(t_k[j]) ≠ p(t_{k+1}[j]) (consecutive tasks must be on different processors) is part of the G&J formulation but more restrictive than many modern job-shop formulations — this should be explicitly noted as a design choice ⚠️
• The issue does not explicitly state this is a satisfaction problem (Metric = bool) ⚠️

4d: Example Quality (❌ Fail):

Precedence violation confirmed by Python validator:

• j_5.t2 is scheduled on P2 at [14, 17] (finishes at time 17)
• j_5.t3 is scheduled on P1 at [14, 15] (starts at time 14)
• But t3 must start after t2 finishes → j_5.t3 cannot start before time 17

The claimed schedule is infeasible.

Python validation stats (instance quality is good despite the schedule error):

• 2 machines, 5 jobs, 12 total tasks
• Minimum feasible makespan: 19 (tight — at D=18 zero feasible orderings exist)
• At D=20: 1,888 feasible orderings out of 518,400 total (99.6% infeasible) → non-trivial ✅
• The instance itself is well-designed; only the claimed schedule needs correction

Missing concrete complexity expression: The Complexity section discusses algorithms but provides no declare_variants!-compatible expression (e.g., "factorial(num_jobs)" or a specific exponential bound). This is needed for implementation.

Items to fix

1. [Must fix] Correct the example schedule — j_5.t3 must start at or after time 17. A valid schedule with makespan 19 exists per the solver.
2. [Must fix] Add a concrete complexity expression for declare_variants! (e.g., "factorial(num_jobs)" for brute-force, matching FlowShopScheduling's approach)
3. [Should fix] Explicitly state this is a satisfaction problem (Metric = bool, implements SatisfactionProblem)
4. [Nice to have] Clarify the consecutive-different-processor constraint as a deliberate G&J formulation choice

Recommendations

• The Gromicho et al. (2012) DP is the best known exact algorithm with a provably better-than-brute-force bound — consider citing the actual complexity theorem rather than the informal O*(2^T) analogy
• The FlowShopScheduling model already exists with complexity "factorial(num_jobs)" — JobShopScheduling should use a similar or more precise expression

[isPANN]

Fix-issue changelog

• Fixed example schedule: Replaced infeasible schedule (j_5.t3 started at 14 before j_5.t2 finished at 17) with a verified optimal schedule (makespan 19). All constraints validated programmatically.
• Added concrete complexity expression: factorial(num_jobs) for declare_variants!, consistent with FlowShopScheduling
• Softened O(2^T) claim*: Properly attributed to Gromicho et al. (2012) with caveat about actual complexity being more nuanced than a simple O*(2^T)
• Explicitly noted satisfaction problem: Added Metric = bool / SatisfactionProblem statement in Motivation
• Clarified consecutive-processor constraint: Added note that this follows the original G&J formulation
• Added non-triviality stats: 1888/518400 feasible orderings at D=20, minimum makespan 19

Applied by /fix-issue.