Single machine scheduling with few deadlines

DOI10.4230/LIPICS.IPEC.2023.24MaRDI QIDQ6926185zbMATH OpenFDO

Authors Klaus Heeger, Danny Hermelin, Dvir Shabtay

Publication date 24 September 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2023.24

zbMATH Keywords

parameterized complexitypseudopolynomial algorithmssingle-machine schedulingtardy jobsweighted completion time

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Parameterized complexity, tractability and kernelization (68Q27) Deterministic scheduling theory in operations research (90B35)

Cites work

• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• A note on the preemptive scheduling to minimize total completion time with release time and deadline constraints
• A note on the single machine scheduling to minimize the number of tardy jobs with deadlines
• Algorithms for Scheduling Independent Tasks
• An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
• Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness
• Bin packing with fixed number of bins revisited
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• scientific article; zbMATH DE number 3550182 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2114378 (Why is no real title available?)
• scientific article; zbMATH DE number 3430360 (Why is no real title available?)
• Minimizing total completion time for preemptive scheduling with release dates and deadline constraints
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Reducibility among combinatorial problems
• Scheduling. Theory, algorithms, and systems
• Sequencing a single machine with due dates and deadlines: An ILP-based approach to solve very large instances
• Single Machine Scheduling with Deadlines to Minimize the Weighted Number of Tardy Jobs
• Single-machine scheduling with deadlines to minimize the total weighted late work
• Unary NP-hardness of minimizing the number of tardy jobs with deadlines
• Unary NP-hardness of preemptive scheduling to minimize total completion time with release times and deadlines
• Unary NP-hardness of single-machine scheduling to minimize the total tardiness with deadlines

This page was built for publication: Single machine scheduling with few deadlines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6926185)