Partition → Common-delay coupled-task deadline feasibility Complexity open
Unsolved
Why this question matters
A hardness result would isolate the effect of deadlines in a highly uniform coupled-task scheduling model.
Results for general coupled tasks do not directly classify deadline feasibility when both the first-operation length and the intervening delay equal the same value.
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.
On one machine, each job has a first operation of common length p, an exact delay p, a second operation of length b_i, and a deadline d_i. Binary integer start times must avoid overlap and meet every deadline; zero-length second operations are allowed.
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.
Local ordering gadgets must compose under the common delay. Restricted pair-orientation tests have not supplied a general construction.
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.