NP-hardness of the single-variable-resource scheduling problem to minimize the total weighted completion time

DOI10.1016/J.EJOR.2006.02.014MaRDI QIDQ859949zbMATH OpenOpenAlexFDO

Authors N. E. Zubov

Publication date 22 January 2007

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10397/661

zbMATH Keywords

schedulingNP-hardnesstotal weighted completion timesingle-variable-resource

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Recommendations

• Strong NP-hardness of the single-variable-resource scheduling problem to minimize the total weighted completion time
• Minimizing total weighted completion time on a single machine subject to non-renewable resource constraints
• New complexity and approximability results for minimizing the total weighted completion time on a single machine subject to non-renewable resource constraints
• scientific article; zbMATH DE number 2219122
• The single machine total weighted completion time scheduling problem with the sum-of-processing time based models: strongly NP-hard
• scientific article; zbMATH DE number 1322689
• Unary NP-hardness of single-machine scheduling to minimize the total tardiness with deadlines
• The single-processor scheduling problem with time restrictions: complexity and related problems
• Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations
• scientific article; zbMATH DE number 3891075

Cites work

• scientific article; zbMATH DE number 167292 (Why is no real title available?)
• A multiple-criterion model for machine scheduling
• Sequencing independent jobs with a single resource

Cited in

(4)

• Single machine scheduling to minimize total compression plus weighted flow cost is NP-hard.
• Strong NP-hardness of the single-variable-resource scheduling problem to minimize the total weighted completion time
• Single-machine past-sequence-dependent setup times scheduling with resource allocation and learning effect
• scientific article; zbMATH DE number 2219122 (Why is no real title available?)

This page was built for publication: NP-hardness of the single-variable-resource scheduling problem to minimize the total weighted completion time

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