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

DOI10.1016/J.EJOR.2006.02.014zbMATH Open1107.90024OpenAlexW2000384174MaRDI QIDQ859949FDOQ859949

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

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

zbMATH Keywords

schedulingNP-hardnesstotal weighted completion timesingle-variable-resource

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Cites Work

• A multiple-criterion model for machine scheduling
• Title not available (Why is that?)
• Sequencing independent jobs with a single resource

Cited In (4)

• Title not available (Why is that?)
• 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

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)