I found this proof for showing that Scheduling with Release Time is NP-Hard by reduction to Subset-sum, but I don't understand it:
Scheduling With Release Time:
Given a set of $n$ jobs with processing time $t_i$, release time $r_i$, and eadline $d_i$, is it possible to schedule all jobs on a single machine such that job $i$ is processed with a contiguous slot of $t_i$ time units in the interval [$r_i$, $d_i$]?
Claim: SUBSET-SUM $\leq_p$ SCHEDULE-RELEASE-TIMES.
Prof: Given an instance of SUBSET-SUM $w_1, … , w_n$, and target $W$,
Create $n$ jobs with processing time $t_i = w_i$, release time $r_i = 0$, and no deadline ($d_i = 1 + \sum_j w_j$)
Create job 0 with $t_0$ = 1, release time $r_0 = W$, and deadline $d_0 = W + 1$
My understanding: so there is some subset of $t_i$ such that their sum adds up to exact $W$, which is the release time of one special job called job 0 and the rest of the jobs have no release / deadline restrictions. I guess the rest of the jobs that are not part of this set will be scheduled after job 0. But I don't understand how this can ensure they don't overlap and how that notation makes the jobs have no deadline. I dont understand how this proof works in general.
Best Answer
Note that the jobs do not have "no deadline", in fact the choice of deadline is crucial. You have $n+1$ jobs which take total time $1+\sum_j w_j$. Since all of their deadlines are at most $1+\sum_j w_j$, the only way all of them can be successfully scheduled on one machine is if they can be performed back-to-back with no gaps in them. But job $0$ must be performed from time $W$ to $W+1$, so they can only be performed back-to-back with no gaps if some subset of the jobs takes exactly $W$ time, i.e. if the instance of SUBSET-SUM is YES. Conversely, if the instance of SUBSET-SUM is YES, then we have some set of jobs we can schedule back-to-back with no gaps from time $0$ to $W$, and if we then schedule the remaining jobs back-to-back after time $W+1$ we meet the deadline.