How to generate an instance for an NP_hard proof, where each element has two inputs?

Question

I want to prove the NP-hardness of an scheduling problem. The problem seems to be NP-hard in the ordinary sense, so I am trying with the Partition Problem, precisely the Equal Cardinality Partition (ECP). So we have:

(ECP): Let $X = \{x_1, x_2, \dots, x_{2n}\}$ be a set of positive integers, does there exist a partition of $X$ into two subsets $X_1$ and $X_2$, such that $\sum_{x_i \in X_1}x_i = \sum_{x_i \in X_2}x_i = B$, where $B$ is a positive integer, and such that $|X_1|=|X_2|$?

The inputs for my scheduling problem are a set of $n$ jobs, where each job has a processing time $p_i$ and a due date $d_i$. So, my instance has jobs where processing times are linked to the integers from the Partition problem, i.e. $p_i=x_i$.

The issue that I have is this: If I assign a common due date for all jobs, i.e. $d_i=d$, then the problem is not NP-hard. So, how I can generate the instance with non-equal due dates? For example, can I use the same integers $x_i$ for the due dates (e.g. $d_i=B-x_i$)? Is it Ok if I use the job id ($i$) in the due dates (e.g. $d_i=B-2i^2$)?

p.s. I realized that I cannot use the $x_i$ of one job in the due date of another job, as then those jobs will be related to each other thai is not correct. Actually, that makes even very simple problems to be NP-hard.

Answer 1

As you noted yourself, the problem in general is NP-hard. You can reduce from Partition by letting due date $d = B = (\sum X)/2$, where $X$ is the input to Partition, and let there be two processes.

The proof is quite straight forward and left as an exercise.

Answer 2

So, let resolve the issue with this problem first.

The single machine scheduling problem is considered. There is a set of jobs $J=\{J_1,J_2,...,J_n\}$, each job has a processing time $p_i$ and a due date $d_i$. Lateness of a job is $L_i=C_i-d_i$, where $C_i$ is the completion time of the job. The problem is to minimize the maximum lateness $L_{max}$.

We know that this problem can be polynomially solved with sequencing jobs in EDD (Earliest Due Date). However, I have a reduction from the ECP to this problem. That means my reduction is not correct, because if it is true, then the problem should be NP_hard, while it is not.

The ECP problem is defined above, and here is the instance of the scheduling problem.

There is a set $J$ of $2n$ jobs that can be partitioned into two subsets: $J_1=\{J_i|p_i=x_i, d_i=B\}$ and $J_2=\{J_i|p_i=2x_i, d_i=3B\}$. Does there exists a schedule with $L_{max}<=0$?

If the ECP has a solution, then we can use elements of $X_1$ in $J_1$ and elements of $X_2$ in $J_2$ and the problem has a solution. And if ECP does not have a solution, (e.g. $\sum X_1=B-1$, or $\sum X_1 = B+1$), then the scheduling problem does not have a solution as well.

So this reduction seems correct to me. However, something must be wrong as the considered scheduling problem is not NP-hard. What is my mistake?