# Complexity Theory – NP Completeness of the PROCESS SCHEDULE PROBLEM

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.

Posted on Categories Articles