Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
So job 0 is to make use of the subset that sums to W and the deadline is to ensure that the rest of jobs not in the summing subset can also be scheduled. –  zeion Jul 29 '13 at 18:30
    
@zeion Correct. –  Alex Becker Jul 29 '13 at 23:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.