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?