I have to prove the NP-Completeness of the following problem:

PROBLEM OF PROCESS PLANNING

Entry: Jobs $ P_1, …, P_n $ with duration $ t_1, .., t_n $ and slots $ l_i, r_i $ for each job, which means that the job must start and end in the interval $[l_i,r_i]$. There is only one processor and it can only do one job.

Result: Is there a schedule so that each job can be done on time?

For example:

The answer is yes, because there is a timetable for all jobs.

My idea is a reduction of Partition Problem to 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 } $ such as $ 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 each work 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 it only works if there are two sets that have A as the sum.