Source: 3-Partition
Target: Flow-Shop Scheduling
Motivation: Establishes that Flow-Shop Scheduling is NP-complete in the strong sense even for a fixed number of processors m = 3, by encoding the strongly NP-complete 3-Partition problem into a 3-machine flow-shop instance where meeting the makespan deadline requires grouping jobs into triples that exactly fill time slots on each machine.
Reference: Garey, Johnson & Sethi, "The complexity of flowshop and jobshop scheduling," Mathematics of Operations Research 1 (1976), pp. 117–129. Also cited in Garey & Johnson, Computers and Intractability, Appendix A5.3, p.241.

GJ Source Entry

[SS15] FLOW-SHOP SCHEDULING
INSTANCE: Number m E Z+ of processors, set J of jobs, each job j E J consisting of m tasks t_1[j], t_2[j], ..., t_m[j], a length l(t) E Z_0+ for each such task t, and an overall deadline D E 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 E J and 1 <= i < m, σ_{i+1}(j) >= σ_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 E J, of σ_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].

Reduction Algorithm

Given a 3-PARTITION instance: a set A = {a_1, ..., a_{3m}} of 3m positive integers with sizes s(a_i), bound B such that B/4 < s(a_i) < B/2 and sum of all s(a_i) = mB, construct a 3-machine flow-shop instance as follows:

1. Processors: Set the number of machines to 3.
2. Jobs: Create 3m "element jobs" and (m−1) "separator jobs." Total jobs: 3m + (m−1) = 4m − 1.
3. Element jobs: For each element a_i (i = 1, ..., 3m), create a job j_i with identical task lengths on all three machines:
   • l(t_1[j_i]) = l(t_2[j_i]) = l(t_3[j_i]) = s(a_i)
4. Separator jobs: Let L = mB + 1. For each separator s_k (k = 1, ..., m−1), create a job with task lengths:
   • l(t_1[s_k]) = 0, l(t_2[s_k]) = L, l(t_3[s_k]) = 0
     The 0-length tasks are valid (FlowShopScheduling uses Z_0+). The large L value on machine 2 creates "walls" that force element jobs to be grouped into triples between separators.
5. Deadline: D = mB + (m−1)L = mB + (m−1)(mB + 1). This is exactly the makespan achievable when elements are perfectly partitioned into triples of sum B on each machine, with separator gaps in between on machine 2.

Correctness:

• If a valid 3-partition exists (A_1, ..., A_m each of size 3 summing to B), schedule the element jobs in group k in the k-th time slot of length B on each machine, separated by the separator jobs on machine 2. The makespan exactly meets D.
• If the flow-shop schedule meets deadline D, then the separator jobs on machine 2 force exactly 3 element jobs (since B/4 < s(a_i) < B/2, each slot fits exactly 3 elements) to fit into each gap of size B, yielding a valid 3-partition.

Solution extraction: Given a feasible schedule, read off which element jobs fall between the k-th and (k+1)-th separator on machine 2; these form partition group A_k.

Size Overhead

Source getters: num_elements (= 3m), num_groups (= m), bound (= B).

Note: deadline is a regular field of FlowShopScheduling, not a size field, so it does not appear in the overhead table. Its value is num_groups * bound + (num_groups - 1) * (num_groups * bound + 1).

Derivation: 3m element jobs + (m−1) separator jobs = num_elements + num_groups − 1 total jobs. Each job has 3 tasks (one per machine). Construction is O(num_elements).

Validation Method

• Closed-loop test: construct a 3-PARTITION instance with 3m = 6 elements (m = 2 triples), reduce to a 3-machine flow-shop instance, solve by brute-force enumeration of all (4m−1)! permutation schedules, verify that a feasible schedule exists iff a valid 3-partition exists.
• Check that the constructed instance has exactly 3 machines, 4m − 1 jobs, and the correct deadline.
• Edge cases: test with an instance where no valid 3-partition exists (expect no feasible schedule), and test with a trivially partitionable instance.

Example

Source instance (3-PARTITION):
A = {a_1, ..., a_6} with sizes s = {6, 7, 7, 6, 8, 6}, B = 20, m = 2 (sum = 40 = 2 × 20).
Constraint: B/4 = 5 < s(a_i) < 10 = B/2 for all i. ✓

Valid 3-partition: A_1 = {7, 7, 6} (sum = 20), A_2 = {6, 8, 6} (sum = 20).

Constructed Flow-Shop instance:

• Machines: 3
• L = mB + 1 = 2 × 20 + 1 = 41
• Jobs: 6 element jobs + 1 separator job = 7 jobs
• Element job task lengths (identical on all 3 machines):

• Deadline D = 2 × 20 + 1 × 41 = 81

Solution:
Schedule group 1 (j_2, j_3, j_4) in time slot [0, 20] on each machine, then separator s_1 on machine 2 at [20, 61], then group 2 (j_1, j_5, j_6) in time slot [61, 81] on each machine. All jobs finish by D = 81.

Solution extraction:

• Group 1 jobs: j_2, j_3, j_4 → A_1 = {7, 7, 6} (sum = 20) ✓
• Group 2 jobs: j_1, j_5, j_6 → A_2 = {6, 8, 6} (sum = 20) ✓

References

• [Garey, Johnson, and Sethi, 1976]: [Garey1976f] M. R. Garey, D. S. Johnson, and R. Sethi (1976). "The complexity of flowshop and jobshop scheduling." Mathematics of Operations Research 1, pp. 117–129.
• [Johnson, 1954]: [Johnson1954] Selmer M. Johnson (1954). "Optimal two- and three-stage production schedules with setup times included." Naval Research Logistics Quarterly 1, pp. 61–68.
• [Gonzalez and Sahni, 1978a]: [Gonzalez1978b] T. Gonzalez and S. Sahni (1978). "Flowshop and jobshop schedules: complexity and approximation." Operations Research 26, pp. 36–52.
• [Cho and Sahni, 1978]: [Cho1978] Y. Cho and S. Sahni (1978). "Preemptive scheduling of independent jobs with release and due times on open, flow, and job shops."