Consider the problem of scheduling jobs with different lengths on a single machine while the jobs have the same release times and different due dates. The goal is to schedule the maximum number of scheduled jobs such that none of the scheduled jobs is late. Can this problem solved in polynomial time if jobs are non-preemptive? What about the case of preemptive jobs? If there exists a polynomial time for it, please describe the best polynomial time algorithm you know. Otherwise, please provide the proof of NP-HARDNESS.

I searched for it, and the only papers I found the 2 papers below:

https://www.jstor.org/stable/pdf/2628449.pdf https://www.jstor.org/stable/pdf/2628520.pdf I am surprised that I could not find any papers published after 1990. Moreover, the second paper has not explicitly claimed that his algorithm is polynomial time. Is it a polynomial time algorithm?

  • 1
    $\begingroup$ The solution in the Moore's paper seems to answer your question: it provides an $O(n^2)$ algorithm (where $n$ is the number of jobs) which seems to be reducible to $O(n\log(n))$. The optimality proof works if the job can be preempted and restarted later (and the algorithm does not produce any preemptions), so the paper applies to both cases. Does this answer your question? Otherwise, please, specify the problem you want to solve in more details. $\endgroup$
    – fiktor
    Sep 14, 2023 at 5:19
  • $\begingroup$ I usually use this wiki (see notations here) for all the known results. And yes, both the problems that you asked are polynomial time. $\endgroup$ Sep 15, 2023 at 10:10
  • $\begingroup$ I know that wiki, but its results are very old.@InuyashaYagami $\endgroup$ Sep 17, 2023 at 17:21


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.