Key points are not available for this paper at this time.
We study the fundamental scheduling problem 1 rⱼ wⱼ Uⱼ: schedule a set of n jobs with weights, processing times, release dates, and due dates on a single machine, such that each job starts after its release date and we maximize the weighted number of jobs that complete execution before their due date. Problem 1 rⱼ wⱼ Uⱼ generalizes both Knapsack and Partition, and the simplified setting without release dates was studied by Hermelin et al. Annals of Operations Research, 2021 from a parameterized complexity viewpoint. Our main contribution is a thorough complexity analysis of 1 rⱼ wⱼ Uⱼ in terms of four key problem parameters: the number p_\# of processing times, the number w_\# of weights, the number d_\# of due dates, and the number r_\# of release dates of the jobs. 1 rⱼ wⱼ Uⱼ is known to be weakly para-NP-hard even if w_\#+d_\#+r_\# is constant, and Heeger and Hermelin ESA, 2024 recently showed (weak) W1-hardness parameterized by p_\# or w_\# even if r_\# is constant. Algorithmically, we show that 1 rⱼ wⱼ Uⱼ is fixed-parameter tractable parameterized by p_\# combined with any two of the remaining three parameters w_\#, d_\#, and r_\#. We further provide pseudo-polynomial XP-time algorithms for parameter r_\# and d_\#. To complement these algorithms, we show that 1 rⱼ wⱼ Uⱼ is (strongly) W1-hard when parameterized by d_\#+r_\# even if w_\# is constant. Our results provide a nearly complete picture of the complexity of 1 rⱼ wⱼ Uⱼ for p_\#, w_\#, d_\#, and r_\# as parameters, and extend those of Hermelin et al. Annals of Operations Research, 2021 for the problem 1 wⱼ Uⱼ without release dates.
Kaul et al. (Fri,) studied this question.