The NP-completeness of the n/m/parallel/C_ preemptive due-date scheduling problem

DOI10.1016/0895-7177(90)90375-WMaRDI QIDQ583101zbMATH OpenOpenAlexFDO

Authors C. C. S. Sin, T. C. Edwin Cheng

Publication date 1990

Published in Mathematical and Computer Modelling (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0895-7177(90)90375-w

zbMATH Keywords

m parallel machinesmaximum job completion timeNP-completenesspreemptive due-date schedulingsimultaneously available jobs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Recommendations

• scientific article; zbMATH DE number 1757970
• scientific article; zbMATH DE number 232395
• Preemptive scheduling with deadlines on parallel machines
• scientific article; zbMATH DE number 969090
• A two-machine preemptive openshop scheduling problem: An elementary proof of NP-completeness

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Preemptive Scheduling with Due Dates
• Survey of scheduling research involving due date determination decisions
• The NP-completeness of the \(n/m/parallel/C_{\max}\) preemptive due-date scheduling problem

Cited in

(4)

• The proof on the NP-completeness of two batching scheduling problems
• scientific article; zbMATH DE number 1757970 (Why is no real title available?)
• Two coNP-complete schedule analysis problems
• The NP-completeness of the \(n/m/parallel/C_{\max}\) preemptive due-date scheduling problem

This page was built for publication: The NP-completeness of the \(n/m/parallel/C_{\max}\) preemptive due-date scheduling problem

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