Unary NP-hardness of minimizing total weighted tardiness with generalized due dates

DOI10.1016/J.ORL.2015.12.006MaRDI QIDQ1785477zbMATH OpenOpenAlexFDO

Authors Yuan Gao, Jinjiang Yuan

Publication date 28 September 2018

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2015.12.006

zbMATH Keywords

single machine schedulingtotal weighted tardinessgeneralized due datesunary NP-hard

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Unary NP-hardness of minimizing the total deviation with generalized or assignable due dates
• Unary NP-hardness of single-machine scheduling to minimize the total tardiness with deadlines
• scientific article; zbMATH DE number 4172724
• Unary NP-hardness of minimizing the number of tardy jobs with deadlines
• Minimizing Total Tardiness on One Machine is NP-Hard

Cites work

• scientific article; zbMATH DE number 4172724 (Why is no real title available?)
• scientific article; zbMATH DE number 167292 (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
• On the complexity of generalized due date scheduling problems
• Single machine scheduling with assignable due dates

Cited in

(15)

• Unary NP-hardness of single-machine scheduling to minimize the total tardiness with deadlines
• Unary NP-hardness of minimizing the number of tardy jobs with deadlines
• A single machine scheduling with generalized and periodic due dates to minimize total deviation
• Order acceptance and scheduling with delivery under generalized parameters
• Just-in-time scheduling with generalized due dates and identical due date intervals
• Single-machine scheduling with periodic due dates to minimize the total earliness and tardy penalty
• Scheduling with generalized and periodic due dates under single- and two-machine environments
• Strong NP-hardness of minimizing total deviation with generalized and periodic due dates
• Unary NP-hardness of minimizing the total deviation with generalized or assignable due dates
• Minimizing tardiness scheduling measures with generalized due-dates and a maintenance activity
• Min–max version of single-machine scheduling with generalized due dates under scenario-based uncertainty
• Single machine scheduling with rejection and generalized parameters
• On the tractability of hard scheduling problems with generalized due-dates with respect to the number of different due-dates
• Minimizing Total Tardiness on One Machine is NP-Hard
• Two-machine ordered flow shop scheduling with generalized due dates

This page was built for publication: Unary NP-hardness of minimizing total weighted tardiness with generalized due dates

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