Unary NP-hardness of minimizing the total deviation with generalized or assignable due dates

DOI10.1016/J.DAM.2015.03.011MaRDI QIDQ2352264zbMATH OpenOpenAlexFDO

Authors Yuan Gao, Jinjiang Yuan

Publication date 30 June 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2015.03.011

zbMATH Keywords

assignable due datesgeneralized due datessingle machine schedulingunary NP-hard

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Unary NP-hardness of minimizing total weighted tardiness with generalized due dates
• Strong NP-hardness of minimizing total deviation with generalized and periodic due dates
• A single machine scheduling with generalized and periodic due dates to minimize total deviation
• Unary NP-hardness of single-machine scheduling to minimize the total tardiness with deadlines
• scientific article; zbMATH DE number 4172724

Cites work

• Earliness–Tardiness Scheduling Problems, II: Deviation of Completion Times About a Restrictive Common Due Date
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the complexity of generalized due date scheduling problems
• Single machine scheduling with assignable due dates
• Single machine scheduling with release and due date assignment to minimize the weighted number of late jobs

Cited in

(14)

• Unary NP-hardness of minimizing total weighted tardiness with generalized due dates
• 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
• A single machine scheduling with generalized and periodic due dates to minimize total deviation
• Single machine scheduling with rejection and generalized parameters
• Unary NP-hardness of single-machine scheduling to minimize the total tardiness with deadlines
• Strong NP-hardness of minimizing total deviation with generalized and periodic due dates
• Unary NP-hardness of minimizing the number of tardy jobs with deadlines
• Just-in-time scheduling with generalized due dates and identical due date intervals
• Minimizing tardiness scheduling measures with generalized due-dates and a maintenance activity
• Order acceptance and scheduling with delivery under generalized parameters
• Two-machine permutation flow shop scheduling with generalized due dates to minimize total late work
• Scheduling with assignable due dates, two competing agents and late work related criteria
• Single-machine preemptive scheduling with assignable due dates or assignable weights to minimize total weighted late work

This page was built for publication: Unary NP-hardness of minimizing the total deviation with generalized or assignable due dates

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