Kaul, MatthiasMatthiasKaulMnich, MatthiasMatthiasMnichMolter, HendrikHendrikMolter2024-12-102024-12-10202419th International Symposium on Parameterized and Exact Computation (IPEC 2024)https://hdl.handle.net/11420/52333We study the fundamental scheduling problem 1 | rj | wjUj: 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 | rj | wjUj 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 | rj | wjUj 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 | rj | wjUj is known to be weakly para-NP-hard even if w# + d# + r# is constant, and Heeger and Hermelin [ESA, 2024] recently showed (weak) W[1]-hardness parameterized by p# or w# even if r# is constant. Algorithmically, we show that 1 | rj | wjUj 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 | rj | wjUj is (strongly) W[1]-hard when parameterized by d# +r# even if w# is constant. Our results provide a nearly complete picture of the complexity of 1 | rj | wjUj for p#, w#, d#, and r# as parameters, and extend those of Hermelin et al. [Annals of Operations Research, 2021] for the problem 1 || wjUj without release dates.enhttps://creativecommons.org/licenses/by/4.0/Computer Science, Information and General Works::004: Computer SciencesContribution to Conferencehttps://doi.org/10.15480/882.1386210.4230/LIPIcs.IPEC.2024.1910.15480/882.13862Contribution to Conference