On the tractability of hard scheduling problems with generalized due-dates with respect to the number of different due-dates
From MaRDI portal
Publication:2093185
DOI10.1007/s10951-022-00743-9zbMath1501.90030OpenAlexW4283446493MaRDI 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
schedulingsingle machineparameterized complexity\(\mathcal{NP}\)-hardpseudo-polynomial time algorithmgeneralized due-dates
Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
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