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

DOI10.1007/S10951-019-00615-9MaRDI QIDQ2286436zbMATH OpenOpenAlexFDO

Authors Rubing Chen, Jinjiang Yuan

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

deadlinessingle-machine schedulingtardinessunary NP-hard

Mathematics Subject Classification ID

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

Recommendations

• 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 minimizing total weighted tardiness with generalized due dates
• Unary NP-hardness of minimizing the total deviation with generalized or assignable due dates
• Single-machine scheduling to minimize the total earliness and tardiness is strongly NP-hard

Cites work

• scientific article; zbMATH DE number 3550186 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Minimizing Total Tardiness on One Machine is NP-Hard
• One-Machine Sequencing to Minimize Certain Functions of Job Tardiness
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Single machine scheduling with release times, deadlines and tardiness objectives
• Unary NP-hardness of minimizing the number of tardy jobs with deadlines

Cited in

(15)

• Unary NP-hardness of minimizing total weighted tardiness with generalized due dates
• A special case of the single-machine total tardiness problem is NP-hard
• A note on the complexity of two supply chain scheduling problems
• New results for scheduling to minimize tardiness on one machine with rejection and related problems
• Unary NP-hardness of preemptive scheduling to minimize total completion time with release times and deadlines
• Unary NP-hardness of minimizing the total deviation with generalized or assignable due dates
• Unary NP-hardness of minimizing the number of tardy jobs with deadlines
• Single-machine scheduling to minimize the total earliness and tardiness is strongly NP-hard
• Parallel machine scheduling with due date-to-deadline window, order sharing and time value of money
• Multi-agent single machine scheduling problem with transportation constraints
• Single-machine primary-secondary scheduling with total tardiness being the primary criterion
• Single-machine scheduling with positional deadlines, time deadlines, and due date assignment for minimizing total weighted tardiness
• Single machine scheduling with few deadlines
• Research on construction and application for the model of multistage job shop scheduling problem
• NP-hardness of the single-variable-resource scheduling problem to minimize the total weighted completion time

This page was built for publication: Unary NP-hardness of single-machine scheduling to minimize the total tardiness with deadlines

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