[Rule] Partition to Multiprocessor Scheduling

[isPANN]

Source: Partition
Target: MultiprocessorScheduling
Motivation: This reduction maps a PARTITION instance to a MULTIPROCESSOR SCHEDULING instance by creating one task per element and fixing the number of processors to 2 with deadline D = S/2, where S is the total element sum. A balanced partition exists if and only if the two-processor schedule meets the deadline. This is the canonical restriction-based NP-completeness proof for Multiprocessor Scheduling, cited in Garey & Johnson, Section 3.2.1.
Reference: Garey & Johnson, Computers and Intractability, Section 3.2.1 item (7), p.65
Dependencies: Requires [Model] Partition (#210) and [Model] MultiprocessorScheduling (#212)

Reduction Algorithm

(7) MULTIPROCESSOR SCHEDULING
INSTANCE: A finite set A of "tasks," a "length" l(a) ∈ Z+ for each a ∈ A, a number m ∈ Z+ of "processors," and a "deadline" D ∈ Z+.
QUESTION: Is there a partition A = A_1 ∪ A_2 ∪ ⋯ ∪ A_m of A into m disjoint sets such that

max { ∑_{a ∈ A_i} l(a) : 1 ≤ i ≤ m } ≤ D ?

Proof: Restrict to PARTITION by allowing only instances in which m = 2 and D = ½∑_{a ∈ A} l(a).

Summary:

Let A = {a_1, ..., a_n} be an arbitrary PARTITION instance, where s(a_i) ∈ Z⁺ denotes the size of element a_i (corresponding to l(a) in the GJ formulation above). Let S = Σ_{i=1}^{n} s(a_i).

1. Tasks: For each element a_i ∈ A, create a scheduling task t_i with length l(t_i) = s(a_i). The task set is T = {t_1, ..., t_n}.
2. Processors and deadline: Set m = 2 processors and deadline D = S / 2. (If S is odd, no balanced partition exists; output any trivially infeasible instance, e.g., a single task with length 1 and deadline 0.)
3. Correctness: A balanced partition A' ∪ (A \ A') with each part summing to S / 2 exists if and only if assigning {t_i : a_i ∈ A'} to processor 1 and the rest to processor 2 satisfies max load ≤ D.
4. Solution extraction: Given a valid schedule σ (assignment of tasks to processors), the partition is A' = {a_i : t_i assigned to processor 1} and A \ A' = {a_i : t_i assigned to processor 2}.

Size Overhead

Symbols:

• n = number of elements in PARTITION instance (num_elements of source)
• S = Σ s(a_i) = total sum of element sizes (total_sum of source)

Target metric (code name)	Expression (using source getters)
num_tasks	num_elements (= n)
num_processors	2
deadline	total_sum / 2 (requires even total_sum; odd → infeasible)

Derivation: Each element of A maps directly to one task of the same length. Only two processors are needed (a constant). The deadline is fixed at half the total task length. Construction is O(n).

Validation Method

• Closed-loop test: construct a PARTITION instance, reduce to MULTIPROCESSOR SCHEDULING with m=2, D=S/2, solve with BruteForce by trying all 2^n assignments, verify the max-load assignment corresponds to a valid balanced partition.
• Check that the constructed instance has exactly n tasks, m = 2 processors, and D = S/2.
• Edge cases: test with odd total sum (expect infeasible: D would not be an integer), n = 1 (infeasible, single task cannot meet deadline D = s(a_1)/2 < l(t_1)).

Example

Source instance (PARTITION):
A = {4, 5, 3, 2, 6} (n = 5 elements)
Total sum S = 4 + 5 + 3 + 2 + 6 = 20
A balanced partition exists: A' = {4, 6} (sum = 10) and A \ A' = {5, 3, 2} (sum = 10).

Constructed MULTIPROCESSOR SCHEDULING instance:

Task t_i	Length l(t_i)
t_1	4
t_2	5
t_3	3
t_4	2
t_5	6

Number of processors m = 2, Deadline D = 10.

Solution:
Assign {t_1, t_5} (lengths 4, 6) to processor 1: total load = 10 ≤ D ✓
Assign {t_2, t_3, t_4} (lengths 5, 3, 2) to processor 2: total load = 10 ≤ D ✓
Max load = max(10, 10) = 10 ≤ D = 10 ✓

Solution extraction:
Partition: A' = {a_1, a_5} = {4, 6} (sum = 10) and A \ A' = {a_2, a_3, a_4} = {5, 3, 2} (sum = 10). Balanced ✓

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	Neither Partition nor Multiprocessor Scheduling exists in the codebase yet; novel reduction
Non-trivial	⚠️ Warn	Restriction-based reduction — Partition is a special case of Multiprocessor Scheduling (m=2, D=sum/2); borderline trivial but involves meaningful parameter fixing
Correctness	✅ Pass	Garey & Johnson (1979) is in the project bibliography; the restriction technique and this specific example are well-established
Well-written	❌ Fail	Multiple issues with template completeness and metric names (see details below)

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

Neither Partition nor MultiprocessorScheduling exists in the codebase (confirmed via pred show). There is no existing path between these problems. The reduction is a canonical example from Garey & Johnson and would be a meaningful addition to the reduction graph, especially as a foundation for the Sequencing and Scheduling problem family.

Result: Pass

Non-trivial

This reduction is a restriction — it shows Partition is a special case of Multiprocessor Scheduling by fixing m=2 and D=sum/2. The issue itself quotes Garey & Johnson's proof which literally says "Restrict to PARTITION by allowing only instances in which m=2 and D=½∑l(a)."

Restriction-based reductions are on the boundary: there is no gadget construction, no auxiliary variables, and no structural transformation — the source instance maps directly to a target instance with fixed parameters. However, the reduction does involve meaningful parameter fixing (choosing m and D from the source data), and the correctness argument is non-vacuous (it requires showing the bijection between balanced partitions and valid 2-processor schedules).

Result: Warn — This is a restriction, not a constructive reduction. It is a legitimate NP-completeness proof technique (GJ Section 3.2.1), but it is the simplest class of reductions. The implementation will be straightforward (essentially copy task lengths, set m=2, compute D). Consider whether the project wants to support restriction-based reductions or only constructive ones.

Correctness

Reference: Garey & Johnson, Computers and Intractability (1979), Section 3.2.1.

• The book is already in the project bibliography as garey1979.
• Multiprocessor Scheduling is problem SS8 in GJ's appendix (not SS1 as listed in references.md — references.md lists SS1, but that is the standard GJ number for this problem in their appendix).
• The restriction technique described (m=2, D=sum/2) is the standard proof that Multiprocessor Scheduling is NP-complete, widely cited across textbooks and lecture notes.
• The issue cites "Section 3.2.1 item (7), p.65" — Section 3.2.1 in GJ does discuss the restriction technique and lists Multiprocessor Scheduling as an example. The page number and item number are plausible for this section.
• The correctness argument (balanced partition ↔ valid 2-processor schedule with makespan ≤ D) is mathematically sound.

Result: Pass

Well-written

4a — Information Completeness: All template sections are present and substantive (Source, Target, Motivation, Reference, Reduction Algorithm, Size Overhead, Validation Method, Example). ✅

4b — Algorithm Completeness: The 4-step algorithm is clear and implementable: (1) create tasks from elements, (2) set m=2 and D=sum/2, (3) correctness argument, (4) solution extraction. ✅

4c — Symbol and Notation Consistency:

• The algorithm uses s(a_i) for element sizes but then switches to B_total for the total sum. The overhead table then uses total_sum as a code expression. The relationship between these symbols could be clearer, but is followable. ✅
• Problem: The overhead table references code metric names (num_tasks, num_processors, deadline) that are assumed getter methods on the target MultiprocessorScheduling type. Since this problem does not exist yet in the codebase, these cannot be verified. The total_sum / 2 expression for deadline uses a source-side metric (total_sum) which is fine, but num_processors = 2 is a constant, not a function of source metrics — this is unusual but acceptable for a restriction.
• Problem: The overhead table uses num_tasks as both a source metric and target metric name. The source problem is Partition, which likely has a different getter name (e.g., num_elements or num_items). The overhead expressions should reference source problem getter methods, not target ones. ❌

4d — Example Quality:

• The example (A = {4, 5, 3, 2, 6}) is non-trivial with 5 elements. ✅
• The solution is fully worked through with step-by-step construction. ✅
• The example is brute-force verifiable. ✅

Items to fix:

1. Overhead table metric names must reference source problem getters. Since Partition does not yet exist, the issue should clarify what the source getter names will be (e.g., num_elements for n, total_sum for S). The target metrics should use expected target getter names. Currently the table conflates source and target naming.
2. Both source and target problems are missing from the codebase. This rule requires implementing both Partition and MultiprocessorScheduling models first. The issue should note this dependency or link to corresponding [Model] issues.

Result: Fail — Overhead table metric names are inconsistent and cannot be verified against either source or target problem getters (neither problem exists yet).

Recommendations

• Consider filing [Model] issues for both Partition and Multiprocessor Scheduling before this rule can be implemented.
• The overhead for this reduction is essentially O(n) with no size blowup — this is characteristic of restriction-based reductions and is a strong point.
• The issue could note that this reduction direction (Partition → Multiprocessor Scheduling) shows Multiprocessor Scheduling is at least as hard as Partition, which is the standard NP-hardness argument direction.

[isPANN]

Fixed overhead table to use source (Partition) getter names (num_elements, total_sum) instead of target names, and added dependency links to #210 and #212.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	Neither Partition nor MultiprocessorScheduling exist in the codebase; no existing path to compare against
Non-trivial	⚠️ Warn	Restriction-based reduction (embed special case with m=2, D=S/2); no gadget or structural transformation, but it is a canonical classical reduction
Correctness	✅ Pass	Garey & Johnson (1979) Section 3.2.1, item SS1 is a real and well-established reference; garey1979 already in bibliography
Well-written	⚠️ Warn	Mostly complete and clear, but a few minor issues (see below)

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Both source (Partition) and target (MultiprocessorScheduling) are new problems not yet in the reduction graph. Dependencies on #210 and #212 are correctly noted and both issues exist. Since there is no existing path, this rule is novel. The reduction establishes the canonical NP-completeness proof for 2-processor scheduling via Partition, which is a foundational result in complexity theory.

Non-trivial

This is a restriction-based reduction, not a construction-based one. The G&J proof works by showing Partition is a special case of Multiprocessor Scheduling (set m=2 and D = total_sum/2). The "reduction" copies element sizes verbatim as task lengths and fixes two constants. There are no gadgets, auxiliary variables, or structural transformations.

That said, this is a well-known, legitimate reduction between genuinely different problem formulations (a set-partitioning problem vs. a scheduling problem). It is not a subtype coercion or same-problem identity. The two problems have different input structures and semantics. Marking as Warn rather than Fail because restriction-based reductions are accepted in complexity theory and this is the canonical example.

Correctness

The reference to Garey & Johnson (1979), Computers and Intractability, is correct. The book's Appendix lists Multiprocessor Scheduling as problem SS1 (p. 238), and Section 3.2.1 discusses restriction-based NP-completeness proofs. The claim that Multiprocessor Scheduling is NP-complete even for m=2 processors, by restriction from Partition, is confirmed by multiple independent sources including the Wikipedia articles on both the Partition problem and Multiprocessor scheduling.

The garey1979 BibTeX entry already exists in docs/paper/references.bib, so no new reference is needed.

Well-written

The issue is mostly well-structured with all required sections present and substantive. Specific observations:

Strengths:

• Clear step-by-step reduction algorithm with 4 numbered steps
• Good handling of the odd-sum edge case (step 2)
• Well-worked example with A = {4, 5, 3, 2, 6}
• Solution extraction clearly described
• Validation method covers edge cases

Minor issues to consider (warnings, not failures):

1. Notation inconsistency between sections: The issue body uses l(a) (from the G&J quote) and s(a_i) (in the summary algorithm) interchangeably for element sizes. Pick one notation and use it consistently.
2. Overhead table deadline expression: total_sum / 2 is valid as an overhead expression, but the table should clarify that this is floor division (or note the odd-sum case produces an infeasible instance, which is already mentioned in step 2).
3. Code metric names are speculative: The overhead table references num_tasks, num_processors, and deadline as getter methods on MultiprocessorScheduling, but that model does not exist yet ([Model] MultiprocessorScheduling #212). These names should be confirmed once the model is implemented. The num_elements and total_sum getters on Partition ([Model] Partition #210) are similarly unconfirmed.
4. The reduction direction could be stated more explicitly at the top. The motivation paragraph says "Setting m=2 and D=half the total task length turns the scheduling problem into exactly PARTITION" which describes the restriction direction (Scheduling -> Partition), but the actual reduction implemented goes the other direction (Partition -> Scheduling). Both directions are valid but the prose could be clearer.

Recommendations

• Once both model issues ([Model] Partition #210, [Model] MultiprocessorScheduling #212) are implemented, verify that the getter method names in the overhead table match the actual implementations.
• Consider adding a note that this is a restriction-based reduction (as opposed to a construction-based one), since the codebase may want to tag or categorize reductions by type.