Given a set of $n$ jobs with processing time $t_i$, release time $r_i$, and deadline $d_i$, can we schedule all $K$ number of jobs ($0 \le K$)on a single machine. Reduce SubsetSum to Schedule. The solution goes as Given an instance of SUBSET-SUM $\{a_1,..,a_n\}$ and $T$. Design $r_i = 0$, $d_i = 1+\sum_i a_i$ , $p_i = a_i$ where $p_i$ is process time for $n$ jobs and create another job with release time $T$,process time 1, and deadline $T+1$ (so create $n+1$ jobs). We show that an instance can be accepted by Subset sum iff our designed $n+1$ jobs all can be accepted by schedule.
However, I'm confused here, because if a SubsetSum takes an array [1,1,2] and the target = 6. Then, SubsetSum would return False; but this instance according to transformation would give a set of job (0,1,5), (0,1,5), (0,2,5), (6,1,7). The first element is release time, second is process time, third is deadline. Schedule Problem can schedule all of these jobs without overlap or miss deadline. So SubsetSum() return False but Schedule return True
Best Answer
Maybe this answer is very late but since I was studying this topic I thought I may give it a shot.
To reduce Subset Sum to Scheduling (with release time and deadline restriction) you have to do the following:
(where $\pi_1$ is the decision problem 1 (Subset Sum) and $\pi_2$ is decision problem 2 (Scheduling))
Where $Y_{\pi_j}$ are the instances of the decision problem $\pi_{j}$ which have a solution, roughly speaking.
The transformation is done in the following way:
Given $S = \{s_1,...,s_n\}$ a set of positive integers to which there is a subset S' such that its elements add up to $k$ and the sum of the whole set is $x$. (You have to pick an instance of the problem that is solvable). You define jobs $\{p_1,...,p_n\}$ such that $r_i = 0$, $t_i = s_i$ and $d_i = x + 1$ for every $p_i$ (release time, duration of the job and deadline respectively). This instance solves the scheduling problem because you can arrange the jobs in any order and they will always meet their deadline.
Now the converse, let's suppose we started with a solvable instance of the Scheduling problem. To make things work, let's take the set $\{p_1,p_2,...,p_n,p_{n+1}\}$ where the first $n$ jobs are defined the same as before and job $p_{n+1}$ has the following property: $r_i = k$,$t_i = 1$,$d_i = k+1$.
The extra job has to be done in $[k,k+1]$, but there would still be $x$ units of time available in the time interval $[0,x+1]$. Since this instance is solvable,you have $\{p_{i_1},...,p_{i_m}\} = S' $ processes that can fit before job $p_{n+1}$ and another sequence of jobs after. The set $S'$ solves your Subset Sum instance.
Remember the release time $r_i$ indicate only at what time the job is available (it does not need to be done at that moment, but it does have to be done before its deadline $d_i$)
TLDR: I believe you did not perform the transformation correctly.
Please correct me if you think I made a mistake at some point, I'm trying to understand this topic as well.
Cheers!