2026-07-30T06:01:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19443 2024-03-06T11:04:04Z ddc:004 open_access

Single Machine Scheduling with Few Deadlines Heeger, Klaus Hermelin, Danny Shabtay, Dvir Single-machine scheduling weighted completion time tardy jobs pseudopolynomial algorithms parameterized complexity We study single-machine scheduling problems with few deadlines. We focus on two classical objectives, namely minimizing the weighted number of tardy jobs and the total weighted completion time. For both problems, we give a pseudopolynomial-time algorithm for a constant number of different deadlines. This algorithm is complemented with an ETH-based, almost tight lower bound. Furthermore, we study the case where the number of jobs with a nontrivial deadline is taken as parameter. For this case, the complexity of our two problems differ: Minimizing the total number of tardy jobs becomes fixed-parameter tractable, while minimizing the total weighted completion time is W[1]-hard. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Klaus Heeger and Danny Hermelin and Dvir Shabtay 2023 Is Part Of LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2023.24 urn:nbn:de:0030-drops-194434 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.24 eng https://creativecommons.org/licenses/by/4.0/legalcode