A Deadline Gap Can Hide Subset Sum

Interval scheduling feels simple because each job already tells us where it lives. If job $j$ has release time $r_j$, strict deadline ${\bar{d}}_j$, and processing time

$$p_j={\bar{d}}_j-r_j,$$

then the job either occupies its whole interval $[r_j,{\bar{d}}_j)$ or it does not. There is no room to slide it around.

The moment $p_j$ is allowed to be smaller than ${\bar{d}}_j-r_j$, the interval becomes a window. The schedule must decide where inside that window the job should go. That small freedom is enough to hide subset sum.

The feasibility problem

$$1\mid r_j,{\bar{d}}_j\mid -$$

asks whether all jobs can be scheduled on one machine, respecting release times and strict deadlines. There is no optimisation objective. The question is only whether a feasible schedule exists.

Given a subset sum instance with multiset $S$ and target $T$, let

$$W=\sum _{s\in S}s.$$

Build one special job $x$:

$$\underset{\text{release time}}{\underbrace{r_x=T}},\underset{\text{strict deadline}}{\underbrace{{\bar{d}}_x=T+1}},\underset{\text{processing time}}{\underbrace{p_x=1}}$$

For each number $s\in S$, build one ordinary job $j_s$:

$$\underset{\text{release time}}{\underbrace{r_{j_s}=0}},\underset{\text{strict deadline}}{\underbrace{{\bar{d}}_{j_s}=W+1}},\underset{\text{processing time}}{\underbrace{p_{j_s}=s}}$$

The special job has only one possible place: it must run from $T$ to $T+1$. The ordinary jobs have a long common window, but together they occupy exactly all remaining processing time before $W+1$.

The reduction works because the machine has no spare time. All jobs have total processing time

$$W+1,$$

and the final strict deadline is $W+1$. Since the first release time is $0$, any feasible schedule must keep the machine busy throughout $[0,W+1)$.

The special job forces the slot $[T,T+1)$. Therefore exactly $T$ units of ordinary processing must occur before time $T$. The ordinary processing times are precisely the numbers in $S$. So the ordinary jobs placed before the special job form a subset whose sum is $T$.

Conversely, if some subset of $S$ sums to $T$, schedule those jobs in $[0,T)$, schedule the special job in $[T,T+1)$, and schedule all remaining ordinary jobs after $T+1$. The remaining processing time is

$$W-T,$$

which exactly fits in $[T+1,W+1)$.

So a feasible schedule exists exactly when the subset sum instance has a solution. The insight is that hardness does not come from many machines or a complicated objective. It already appears on one machine, with no objective, as soon as jobs have flexible windows instead of fixed intervals.