A Deadline Gap Can Hide Subset Sum

Interval scheduling feels simple because each job already tells us where it lives. If job has release time , strict deadline , and processing time

then the job either occupies its whole interval or it does not. There is no room to slide it around.

The moment is allowed to be smaller than , 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

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 and target , let

Build one special job :

For each number , build one ordinary job :

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

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

and the final strict deadline is . Since the first release time is , any feasible schedule must keep the machine busy throughout .

The special job forces the slot . Therefore exactly units of ordinary processing must occur before time . The ordinary processing times are precisely the numbers in . So the ordinary jobs placed before the special job form a subset whose sum is .

Conversely, if some subset of sums to , schedule those jobs in , schedule the special job in , and schedule all remaining ordinary jobs after . The remaining processing time is

which exactly fits in .

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.