Balanced Partition → Three-type unrelated-machine scheduling Complexity open
Solution submitted Research history & proof on GitHub ↗
Why this question matters
The question asks whether a fixed number of job types suffices for exact scheduling tractability under compressed multiplicities.
A fixed number of job types does not fix the number of machines or the multiplicities. Results using expanded job lists do not settle this compressed-input endpoint.
The reduction to construct
The source gives an even number of positive binary integer weights. A valid subset contains exactly half the weights and has half their total sum; otherwise the output is NO-SOLUTION.
The source asks for half the input weights with half their total sum. The target has three job types in high-multiplicity encoding, positive integer processing times on unrelated machines, and a makespan bound. An output is an integer assignment-count matrix.
Construct deterministic polynomial-time maps F and G: F sends every legal source instance to a legal target instance, and G(x,y) is a valid source output for every valid output y of F(x). Preserve the stated threshold, domain and promises. The requested complexity conclusion is NP-hardness for the stated target problem.
Counts, capacity constraints and arbitrary feasible assignments must all decode without expanding the high-multiplicity instance.
What a complete answer must include
Give explicit construction and recovery algorithms, a general proof for every legal input and every valid target output, and polynomial runtime and encoding-size bounds. Specify finite output encodings and handle NO-SOLUTION outputs when applicable. Tests compare recovered source outputs with independent source solutions.
References
Literature checked 2026-09-16. This summarizes the archived literature search on the date above. Unpublished, unindexed and overlooked work remains outside coverage; no new novelty assessment was performed.