Unary NP-hardness of single-machine scheduling to minimize the total tardiness with deadlines

DOI10.1007/s10951-019-00615-9zbMath1430.90251OpenAlexW2963195111MaRDI QIDQ2286436

Jinjiang Yuan, Rubing Chen

Publication date: 22 January 2020

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

Full work available at URL: https://doi.org/10.1007/s10951-019-00615-9

zbMATH Keywords

single-machine schedulingtardinessdeadlinesunary NP-hard

Mathematics Subject Classification ID

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

Related Items

Unnamed Item ⋮ Unary NP-hardness of preemptive scheduling to minimize total completion time with release times and deadlines ⋮ New results for scheduling to minimize tardiness on one machine with rejection and related problems ⋮ Research on construction and application for the model of multistage job shop scheduling problem ⋮ Parallel Machine Scheduling with Due Date-to-Deadline Window, Order Sharing and Time Value of Money

Cites Work

• Unnamed Item
• Unnamed Item
• Unary NP-hardness of minimizing the number of tardy jobs with deadlines
• Minimizing Total Tardiness on One Machine is NP-Hard
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• One-Machine Sequencing to Minimize Certain Functions of Job Tardiness
• Single machine scheduling with release times, deadlines and tardiness objectives