Options
Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates
Citation Link: https://doi.org/10.15480/882.13862
Publikationstyp
Contribution to Conference
Date Issued
2024
Sprache
English
TORE-DOI
First published in
Number in series
321
Citation
19th International Symposium on Parameterized and Exact Computation (IPEC 2024)
Contribution to Conference
Publisher DOI
Publisher
Dagstuhl Publishing
We 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.
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.
DDC Class
004: Computer Sciences
Loading...
Name
LIPIcs.IPEC.2024.19.pdf
Size
800.51 KB
Format
Adobe PDF