I have to prove the NP completeness of the following problem:

PROCESS SCHEDULING PROBLEM

Input: Jobs $ P_1, …, P_n $ with the duration $ t_1, .., t_n $ and time windows $ l_i, r_i $ For every job, ie job, I have to start and end in the interval $[l_i,r_i]$, There is only one processor and he can only do one job.

Issue: Is there a schedule for all work to be done on time?

For example:

The answer is Yes, because there is a schedule for all jobs.

My idea is a reduction of the partition problem on PSP.

So given a partition instance $ a_1, a_2, .., a_n $ With $ sum_ {i = 0} ^ n a_i = 2A. $ Is there an index set? $ I subseteq {1, .., n } $ so that $ sum_ {i in I} a_i = A $?

So I have a partition instance $ a_1, …, a_n $ are jobs $ J_1, .., J_n $ with times $ a_1, …, a_n $ and $ l_i = 0, r_i = 2A + 1 $ for every job 1 to n.

We add a new job $ J_ {n + 1} $ With $ t_ {n + 1} = 1, l_ {n + 1} = A, r_ {n + 1} = A + 1 $,

Is this construction correct?

So the idea is that I force the last job to be between A and A + 1, so I have a separation of 2, and this only works if there are two sets of A in total.