3-SAT → Two-machine preemptive unit-job in-tree scheduling with release dates and total completion bound Complexity open
Unsolved
Why this question matters
Moderate: hardness would resolve a classical two-processor boundary for minimizing mean completion time under task dependencies. It would not follow merely from hardness when the number of processors is part of the input.
Chen and coauthors explicitly leave P2|pmtn,in-tree,r_j,p_j=1|sum C_j open. Wang and Bellenguez later prove strong NP-hardness when the processor count is arbitrary, which does not settle fixed two processors.
The reduction to construct
An explicit Boolean 3-CNF formula is given, with YES if satisfiable and NO otherwise.
The input is a finite set of unit-processing-time jobs, nonnegative integer release times, in-tree precedence arcs (each job has at most one successor), and an integer bound B, all explicitly or in binary as appropriate. Preemption is allowed on two identical processors, but a job cannot run on both simultaneously. Output YES exactly when some feasible schedule respects releases and precedence and has sum of completion times at most B; otherwise NO.
Construct deterministic polynomial-time F and G from 3-SAT to this fixed two-machine decision problem with exact YES/NO equivalence. A positive result proves NP-hardness for the case left open by the normal-form scheduling papers.
High: with one machine, no release dates, or an out-tree, related cases are polynomial. The normal-form theorem bounds preemption structure and offers a finite certificate, but a reduction must make Boolean choices persist across overlapping releases without letting preemption lower the cost spuriously.
What a complete answer must include
Give explicit job, release, precedence and threshold construction; prove the scheduling equivalence including fractional preemption, and bound integer and rational encoding lengths. Later verification should solve small positive and negative instances independently.
References
- Normal-form preemption sequences for an open problem in scheduling theory ↗
- Three notes on scheduling unit-length jobs with precedence constraints to minimize the total completion time ↗
Literature checked 2026-09-26. Checked the 2016 Journal of Scheduling primary normal-form article and the 2021 arbitrary-machine follow-up abstract; searched 2026-09-26 for 'P2 pmtn in-tree release dates sum Cj complexity', 'two machine preemptive in-tree total completion NP-hard' and 2024-26 follow-ups. No matching fixed-two classification surfaced in indexed coverage; this older target has a larger unindexed-work risk. Gates 1-4 pass provisionally; Gate 5 holds on a preemption-safe gadget; Gate 6 was not assessed.