1
$\begingroup$

The problem $1||\Sigma w_jU_j$ of minimizing the weighted number of tardy jobs in a single machine is NP-hard. This is well known and can be shown by reducing the knapsack problem to it.

Also, when the jobs have arrival times, the problem $1|r_j|\Sigma U_j$ of minimizing the number of tardy jobs in a single machine is NP-hard.

However, I was reading Minimizing the Number of Tardy Job Units Under Release Time Constraints and it proposes polytime algorithms for both problems. Am I missing something?

The only thing that I can think of is that when preemption is allowed, both problems become easy?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.