Partition → Fixed-order three-machine flexible blocking Complexity open
Solution submitted Research history & proof on GitHub ↗
Why this question matters
The question isolates assignment complexity after sequencing choices have been removed.
The cited scheduling classification asks about the fixed-order assignment problem. Hardness with variable order or different blocking semantics does not settle the stated model.
The reduction to construct
The source gives positive binary integer weights. A valid output is a subset whose sum is half the total, or NO-SOLUTION if no such subset exists.
The target fixes the job order on three machines and permits varying operation patterns with positive integer processing times. Choose legal operation assignments meeting a makespan bound in the nonpreemptive blocking model, or report NO-SOLUTION.
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.
Soundness must inspect every assignment mode under operation-level blocking semantics. The proposed theorem is weak hardness and does not cover identical operation patterns.
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.