[Model] MultiprocessorScheduling

[isPANN]

Motivation

MULTIPROCESSOR SCHEDULING (P192) from Garey & Johnson, A5 SS8. A fundamental NP-complete scheduling problem: given n tasks with integer lengths and m identical processors, can all tasks be completed by a global deadline D? It generalizes PARTITION (taking m=2 and D = half the total task length) and is a key target for reductions from partition-type problems. For fixed m the problem is weakly NP-hard (pseudo-polynomial DP exists); for m as part of the input it is strongly NP-hard (3-PARTITION is a special case).

Definition

Name: MultiprocessorScheduling
Reference: Garey & Johnson, Computers and Intractability, A5 SS8

Mathematical definition:

INSTANCE: Set T of tasks, number m ∈ Z+ of processors, length l(t) ∈ Z+ for each t ∈ T, and a deadline D ∈ Z+.
QUESTION: Is there an m-processor schedule for T that meets the overall deadline D, i.e., a function σ:T→Z0+ such that, for all u ≥ 0, the number of tasks t ∈ T for which σ(t) ≤ u < σ(t) + l(t) is no more than m and such that, for all t ∈ T, σ(t) + l(t) ≤ D?

Variables

• Count: n = |T| (one discrete variable per task, choosing which processor it is assigned to)
• Per-variable domain: {1, 2, ..., m} — the processor index to which the task is assigned
• Meaning: p_t ∈ {1,...,m} is the processor for task t. The total load on each processor i must not exceed D: Σ_{t: p_t = i} l(t) ≤ D for each i.

Note on formulation equivalence: The original Garey & Johnson definition uses a schedule function σ:T→Z0+ that assigns start times, with constraints on simultaneous execution and deadline satisfaction. Since tasks are independent, non-preemptive, and processors are identical, any feasible schedule can be transformed into one where tasks on each processor are packed sequentially without gaps. Therefore, the scheduling feasibility question is equivalent to the simpler assignment question: can tasks be partitioned among m processors such that no processor's total load exceeds D? This justifies using m-ary assignment variables (dims() = vec![m; n]) instead of explicit start times.

Schema (data type)

Type name: MultiprocessorScheduling
Variants: none (no type parameters; lengths are plain positive integers)

Field	Type	Description
lengths	Vec<u64>	Length l(t) of each task t ∈ T
num_processors	usize	Number of identical processors m
deadline	u64	Global deadline D; every task must finish by time D

Size fields: num_tasks (= lengths.len()), num_processors, deadline, total_length (= Σ l(t))

Complexity

• Best known exact algorithm: When m is fixed (e.g., m = 2), the problem is weakly NP-hard and can be solved by pseudo-polynomial DP in O(n · D^(m−1)) time. For general m (as part of the input), the problem is strongly NP-hard. The best known exact algorithm runs in O*(2^n) time via set partitioning [Björklund, Husfeldt & Koivisto, SIAM J. Comput. 38(2), pp. 546–563, 2009], independent of the number of processors m. [Garey & Johnson, 1979; Brucker, Lenstra & Rinnooy Kan, Annals of Discrete Mathematics 1, pp. 343–362, 1977.]
• Complexity string for declare_variants!: "2 ^ num_tasks"

Extra Remark

Full book text:

INSTANCE: Set T of tasks, number m ∈ Z+ of processors, length l(t) ∈ Z+ for each t ∈ T, and a deadline D ∈ Z+.
QUESTION: Is there an m-processor schedule for T that meets the overall deadline D, i.e., a function σ:T→Z0+ such that, for all u ≥ 0, the number of tasks t ∈ T for which σ(t) ≤ u < σ(t) + l(t) is no more than m and such that, for all t ∈ T, σ(t) + l(t) ≤ D?

Reference: Transformation from PARTITION (see Section 3.2.1).

Comment: Remains NP-complete for m = 2, but can be solved in pseudo-polynomial time for any fixed m. NP-complete in the strong sense for m arbitrary (3-PARTITION is a special case). If all tasks have the same length, then this problem is trivial to solve in polynomial time, even for "different speed" processors.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all m^n assignments of tasks to processors; check max load ≤ D.)
• It can be solved by reducing to integer programming. (Binary ILP: x_{t,i} ∈ {0,1}, Σ_i x_{t,i} = 1 for each t, Σ_t x_{t,i} · l(t) ≤ D for each i.)
• Other: Pseudo-polynomial DP for fixed m (dynamic programming over the load vector of m−1 processors).

Example Instance

Input:
T = {t_1, t_2, t_3, t_4, t_5} (n = 5 tasks)
Lengths: l(t_1) = 4, l(t_2) = 5, l(t_3) = 3, l(t_4) = 2, l(t_5) = 6
m = 2 processors, D = 10 (total sum = 20, D = 10 = sum/2).

Feasible assignment:
Processor 1: {t_1, t_5} — total load 4 + 6 = 10 ≤ D ✓
Processor 2: {t_2, t_3, t_4} — total load 5 + 3 + 2 = 10 ≤ D ✓

Answer: YES — a valid schedule meeting deadline D = 10 exists.

Exhaustive enumeration: Search space = 2⁵ = 32 configurations. Exactly 2 feasible assignments: {t₁,t₅}/{t₂,t₃,t₄} and its mirror (loads 10/10 each). (Used in find_all_satisfying test)

Instance 2 (NO, same tasks with D = 9):
Same 5 tasks, m = 2, D = 9. Total length = 20 > 2 × 9 = 18, so no assignment can satisfy the deadline. Search space = 32. 0 feasible assignments. (Used in find_all_satisfying empty test)

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; clear scheduling use case
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	⚠️ Warn	Reference journal name is incorrect; complexity claim is reasonable but not independently verified beyond brute-force
Well-written	⚠️ Warn	Minor issues: variable encoding simplification needs justification; u64 field types questionable

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Pass. MultiprocessorScheduling does not exist in the codebase (confirmed via pred show). The 24 existing problems do not include it. The motivation is concrete and well-argued: it is Garey & Johnson A5 SS8, a fundamental NP-complete scheduling problem that generalizes PARTITION. The issue correctly identifies that it would serve as a reduction target from partition-type problems and is a classic problem in the scheduling category (SS) which is currently unrepresented in the reduction graph. The issue also identifies both brute-force and ILP solver paths.

Non-trivial

Pass. MultiprocessorScheduling has genuinely distinct feasibility constraints from all existing problems. While it is related to BinPacking (both involve assigning items to bins with capacity constraints), the problems are structurally different: BinPacking minimizes the number of bins for a fixed capacity, while MultiprocessorScheduling is a decision problem asking whether a fixed number of processors can meet a deadline. The input structure (task lengths + processor count + deadline) is unique. It is not a variant or renaming of any existing problem.

Correctness

Warn. Two issues found:

1. Reference journal name is wrong. The issue cites "Lenstra, Rinnooy Kan & Brucker, Op. Res., 1977" but the actual paper is: Brucker, Lenstra & Rinnooy Kan, "Complexity of Machine Scheduling Problems," Annals of Discrete Mathematics, Vol. 1, pp. 343-362, 1977. The author order is also different (Brucker is first author). This is not a fatal error since the paper exists and does address scheduling complexity, but it should be corrected.

2. Complexity claim is reasonable but imprecise. The issue states "No known exact algorithm improves upon O*(2^n) brute-force enumeration" for general m. This is a reasonable claim — the naive approach is O(m^n) and inclusion-exclusion / subset-based DP approaches can achieve O*(2^n) (independent of m). However, no specific citation is given for this 2^n bound. The Garey & Johnson reference establishes NP-completeness but does not provide exact algorithm bounds. A more precise citation would strengthen this claim (e.g., the set partitioning approach of Bjorklund, Husfeldt & Koivisto 2009, already in the project bibliography, which solves k-way partitioning in O*(2^n) time).

The Garey & Johnson 1979 reference itself is correct and already in the project bibliography.

Well-written

Warn. The issue is generally well-structured and follows the template, but has some issues:

1. Variable encoding simplification needs justification. The issue defines variables as processor assignments p_t in {1,...,m}, then states the feasibility reduces to checking per-processor load sums. This is correct but glosses over the fact that the original Garey & Johnson definition uses a schedule function sigma:T->Z+ (start times), where feasibility requires both non-overlapping on each processor AND meeting the deadline. The issue's simplification to a pure assignment problem (where tasks on the same processor are sequenced greedily) is valid because tasks are independent and non-preemptive on identical machines, but this equivalence should be stated explicitly rather than assumed.

2. Field types. The schema uses Vec<u64> and u64 for lengths, num_processors, and deadline. Most existing problems in the codebase use usize for counts and i32/u32 for values. Using u64 is unusual — the issue should justify this choice or align with codebase conventions (likely Vec<u64> for lengths is fine since Garey & Johnson specify Z+, but num_processors as usize would be more idiomatic).

3. All template sections are present and substantive — Motivation, Name, Reference, Definition, Variables, Schema, Complexity, How to solve, and Example Instance are all filled in with meaningful content.

4. Example quality is good. The 5-task, 2-processor example is small enough to verify by hand, has a known feasible solution, and exercises the constraints meaningfully.

5. Naming convention. The name MultiprocessorScheduling follows the project convention for problems without an explicit optimization direction (it is a satisfaction/decision problem).

Recommendations

• Fix the reference: Brucker, Lenstra & Rinnooy Kan, Annals of Discrete Mathematics 1 (1977), pp. 343-362.
• Cite Bjorklund, Husfeldt & Koivisto (2009) for the O*(2^n) exact algorithm bound (already in project bibliography as bjorklund2009).
• Add a sentence justifying why the schedule function sigma can be replaced by a pure processor-assignment variable without loss of generality.
• Consider using usize for num_processors to match codebase conventions.