On the tractability of hard scheduling problems with generalized due-dates with respect to the number of different due-dates

DOI10.1007/s10951-022-00743-9zbMath1501.90030MaRDI QIDQ2093185

Daniel Oron, Dvir Shabtay, Gur Mosheiov

Publication date: 4 November 2022

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-022-00743-9

zbMATH Keywords

scheduling; single machine; parameterized complexity; \(\mathcal{NP}\)-hard; pseudo-polynomial time algorithm; generalized due-dates

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Minimizing the maximum deviation of job completion time about a common due-date
• On the complexity of generalized due date scheduling problems
• Minimizing maximum absolute lateness and range of lateness under generalized due dates on a single machine
• Unary NP-hardness of minimizing total weighted tardiness with generalized due dates
• Single machine scheduling to minimize the number of early and tardy jobs
• Two-agent single-machine scheduling with assignable due dates
• Integer Programming with a Fixed Number of Variables
• Minimizing Total Tardiness on One Machine is NP-Hard
• One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey