[Model] FlowShopScheduling

[isPANN]

Motivation

FLOW-SHOP SCHEDULING (P199) from Garey & Johnson, A5 SS15. A classical NP-complete scheduling problem: given m processors and a set of jobs, each consisting of m tasks (one per processor) that must be processed in processor order 1, 2, ..., m, can all jobs be completed by a global deadline D? The flow-shop constraint requires each job to visit every machine in the same fixed order, with no job allowed to start its task on machine i+1 until its task on machine i is completed. NP-complete in the strong sense for m = 3 [Garey, Johnson, and Sethi, 1976]; solvable in polynomial time for m = 2 via Johnson's rule [Johnson, 1954].

Associated rules:

• R144: 3-PARTITION -> FLOW-SHOP SCHEDULING (establishes strong NP-completeness for m = 3)

Definition

Name: FlowShopScheduling

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

Mathematical definition:

INSTANCE: Number m in Z+ of processors, set J of jobs, each job j in J consisting of m tasks t1[j],t2[j], ..., tm[j], a length l(t) in Z0+ for each such task t, and an overall deadline D in Z+.
QUESTION: Is there a flow-shop schedule for J that meets the overall deadline, where such a schedule is identical to an open-shop schedule with the additional constraint that, for each j in J and 1 <= i < m, sigma_{i+1}(j) >= sigma_i(j) + l(t_i[j])?

Variables

• Count: n = |J| (one variable per job, representing its position in the permutation schedule)
• Per-variable domain: {0, 1, ..., n-1} -- the position of job j in the job sequence (for permutation schedules, which are optimal for m = 2 [Johnson, 1954]; for m >= 3, permutation schedules are not always optimal but provide a natural restricted encoding)
• Meaning: pi(j) in {0, ..., n-1} is the position of job j in the processing sequence. In a flow-shop, once the sequence is fixed, the start times on each machine are determined by the precedence and no-overlap constraints. The schedule is feasible iff all jobs complete by time D.

Schema (data type)

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

Field	Type	Description
num_processors	usize	Number of machines m
task_lengths	Vec<Vec<u64>>	task_lengths[j][i] = length of task t_{i+1}[j] on machine i+1
deadline	u64	Global deadline D; every job must finish by time D

Complexity

• Best known exact algorithm: For m = 2, solvable in O(n log n) by Johnson's rule [Johnson, 1954]. For m = 3, the problem is strongly NP-hard; a dynamic programming approach achieves O*(3^n) time [exact exponential algorithms for 3-machine flowshop, Shang, Lente, Liedloff & T'Kindt, 2018]. For general m (part of input), strongly NP-hard; brute-force over n! permutations gives O(n! * mn) time. No known algorithm with complexity significantly better than O(n!) for general m.

Extra Remark

Full book text:

INSTANCE: Number m in Z+ of processors, set J of jobs, each job j in J consisting of m tasks t1[j],t2[j], ..., tm[j], a length l(t) in Z0+ for each such task t, and an overall deadline D in Z+.
QUESTION: Is there a flow-shop schedule for J that meets the overall deadline, where such a schedule is identical to an open-shop schedule with the additional constraint that, for each j in J and 1 <= i < m, sigma_{i+1}(j) >= sigma_i(j) + l(t_i[j])?

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

Comment: NP-complete in the strong sense for m = 3. Solvable in polynomial time for m = 2 [Johnson, 1954]. The same results hold if "preemptive" schedules are allowed [Gonzalez and Sahni, 1978a], although if release times are added in this case, the problem is NP-complete in the strong sense, even for m = 2 [Cho and Sahni, 1978]. If the goal is to meet a bound K on the sum, over all j in J, of sigma_m(j) + l(t_m[j]), then the non-preemptive problem is NP-complete in the strong sense even if m = 2 [Garey, Johnson, and Sethi, 1976].

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all n! permutations of jobs; for each, compute the schedule greedily and check if makespan <= D.)
• It can be solved by reducing to integer programming. (ILP with binary variables x_{j,k} = 1 if job j is in position k; add precedence constraints for each machine and no-overlap constraints.)
• Other: Johnson's algorithm for m = 2.

Example Instance

Input:
m = 3 machines, J = {j_1, j_2, j_3, j_4, j_5} (n = 5 jobs)

Job	Machine 1	Machine 2	Machine 3
j_1	3	4	2
j_2	2	3	5
j_3	4	1	3
j_4	1	5	4
j_5	3	2	3

Deadline D = 25.

Feasible schedule (sequence j_3, j_1, j_5, j_4, j_2):

Machine 1: j_3[0,4], j_1[4,7], j_5[7,10], j_4[10,11], j_2[11,13]
Machine 2: j_3[4,5], j_1[7,11], j_5[11,13], j_4[13,18], j_2[18,21]
Machine 3: j_3[5,8], j_1[11,13], j_5[13,16], j_4[18,22], j_2[22,27]

Makespan = 27 > 25. Let us try sequence j_4, j_1, j_5, j_3, j_2:

Machine 1: j_4[0,1], j_1[1,4], j_5[4,7], j_3[7,11], j_2[11,13]
Machine 2: j_4[1,6], j_1[6,10], j_5[10,12], j_3[12,13], j_2[13,16]
Machine 3: j_4[6,10], j_1[10,12], j_5[12,15], j_3[15,18], j_2[18,23]

Makespan = 23 <= 25. ✓

Answer: YES -- a valid flow-shop schedule meeting deadline D = 25 exists.

Exhaustive enumeration: Search space = 5! = 120 permutations. Exactly 99 permutations have makespan ≤ 25. (Used in find_all_satisfying test)

Instance 2 (NO):
m = 2 machines, 2 jobs each with task lengths [5, 5], D = 10. Both orderings give makespan 15 > 10. Search space = 2! = 2. 0 feasible schedules. (Used in find_all_satisfying empty test)

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph; associated rule R144 (3-PARTITION → this) planned
Non-trivial	✅ Pass	Distinct scheduling problem with fixed machine-order constraint — not isomorphic to any existing model
Correctness	⚠️ Warn	All references verified, but permutation schedule optimality claim needs qualification
Well-written	✅ Pass	Example is fully worked with explicit start times; concrete O*(3^n) bound for m=3 cited

Overall: 3 passed, 1 warning, 0 failed

---

Usefulness

FlowShopScheduling does not exist in the current codebase. The problem is a classic NP-complete scheduling problem from Garey & Johnson (A5 SS15) with a planned reduction from 3-PARTITION (R144).

Non-trivial

This is a genuinely distinct problem. The flow-shop constraint (each job must visit machines in fixed order 1, 2, ..., m, with each task completing before the next starts) creates a fundamentally different structure from:

• Open-shop scheduling (tasks in any order)
• Preemptive scheduling (tasks can be interrupted)
• All other existing models in the codebase

Correctness

All cited references verified:

• Garey, Johnson & Sethi, 1976: "The Complexity of Flowshop and Jobshop Scheduling," Mathematics of Operations Research 1(2):117–129. NP-completeness in the strong sense for m ≥ 3 by reduction from 3-PARTITION confirmed.
• Johnson, 1954: Johnson's rule for two-machine flow shop, O(n log n) polynomial algorithm — confirmed as a classical result.
• Shang, Lenté, Liedloff & T'Kindt, 2018: "Exact exponential algorithms for 3-machine flowshop scheduling problems," Journal of Scheduling 21(2). O*(3^n) DP algorithm confirmed.

Warning: The Variables section states that permutation schedules are "a natural encoding for general m" and are "optimal for m = 2." While correct for m = 2, for m ≥ 3 permutation schedules are not always optimal — non-permutation schedules can achieve shorter makespans. The issue should clarify that the permutation encoding is an approximation/heuristic choice for m ≥ 3, not an exact encoding.

Well-written

The issue is well-structured overall:

• Example quality is high. Two job sequences are tried with fully explicit start times for all jobs on all machines. The first attempt fails (makespan 27 > 25), the second succeeds (makespan 23 ≤ 25). Non-uniform processing times across machines demonstrate the flow-shop structure well.
• Concrete complexity bound provided: O*(3^n) for m = 3 with a citation (Shang, Lenté et al., 2018).
• Schema is clean with clear field descriptions.
• Brute-force and ILP solver paths both identified.

Minor items (not failures):

• For general m (part of input), no specific complexity bound beyond O(n! × mn) — acceptable since the problem is strongly NP-hard and no major improvement over enumeration is known for arbitrary m.
• The task_lengths field description uses 0-based indexing for the array but 1-based for machine numbering — could be clearer but not ambiguous.

Recommendations

• Clarify in the Variables section that permutation schedules are not always optimal for m ≥ 3.
• Consider citing the full author list for the O*(3^n) result: Shang, Lenté, Liedloff & T'Kindt (2018), not just "Lente et al."

[zazabap]

Changelog

Two fixes applied to the issue body:

1. Citation fix (mechanical): Changed "Lente et al., 2018" to "Shang, Lente, Liedloff & T'Kindt, 2018" in the Complexity section, providing full author attribution for the 3-machine flowshop exact algorithm reference.

2. Variables section fix (substantive, Q1 option A): Updated the permutation schedule claim from "which are optimal for m = 2 and a natural encoding for general m" to "which are optimal for m = 2 [Johnson, 1954]; for m >= 3, permutation schedules are not always optimal but provide a natural restricted encoding". This clarifies that permutation schedules are only provably optimal for m = 2 (Johnson's rule) and explicitly notes they are not always optimal for m >= 3.