Partition → Two-machine flexible blocking Complexity open
Unsolved
Why this question matters
The question asks whether assignment flexibility causes hardness even with just two machines.
The target permits variable job order but fixes two machines and bufferless blocking. Other flexibility and buffering models require separate reductions.
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 allows a variable job order. Each job has a mandatory first operation on machine one, flexible intermediate operations, and a final operation on machine two, with positive processing times, no buffer, and no overtaking. Seek an order and legal splits meeting the deadline.
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.
The order itself is free, so soundness must exclude schedules that evade the intended partition by reordering jobs.
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.