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.

  • $\begingroup$ Isn't it the case that if you have two processes and let $d_i = B = (\Sigma X) / 2$ you get a problem equivalent to ECP? $\endgroup$ – Pål GD Jan 1 '19 at 13:32
  • $\begingroup$ Yes. The problem with two processors (machines) is equivalent to ECP. But my problem is a class of single machine scheduling. Let me bring the issue with another example. We know that for a generic single machine problem with due dates, maximum lateness is minimized when jobs are sorted in EDD (earliest due date). But, if I generate an instance like what follows, the problem is NP-hard! So for sure something is wrong in my reduction. $\endgroup$ – Mostafa Jan 1 '19 at 13:40
  • 1
    $\begingroup$ So what is the problem you want to show to be NP-hard? Can you update the question? $\endgroup$ – Pål GD Jan 1 '19 at 13:42
  • $\begingroup$ Here is the instance: $J_1=\{J_i|p_i=x_i, d_i=B\}$ and $J_2=\{J_i|p_i=2x_i, d_i=3B\}$. Then the problem whether there exists a solution with maximum lateness less than 0 is NP-hard. $\endgroup$ – Mostafa Jan 1 '19 at 13:42
  • $\begingroup$ The instance generated in my previous comment is NP-hard, but we know that the problem is polynomially solvable with EDD. So, what is wrong in my reduction? What are the restrictions on generating the instance? $\endgroup$ – Mostafa Jan 1 '19 at 13:45

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.

  • $\begingroup$ But the single machine scheduling with maximum lateness is not NP-hard. So why the following instance is NP-hard? $J1={Ji|pi=xi,di=B}$ and $J2={Ji|pi=2xi,di=3B}$. This is what I cant understand. $\endgroup$ – Mostafa Jan 1 '19 at 14:41
  • 1
    $\begingroup$ I don't understand your question. There is no such thing as a single NP-hard instance. A problem might be NP-hard. $\endgroup$ – Pål GD Jan 1 '19 at 15:09

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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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