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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

4 Citations (Scopus)

Abstract

Baker and Nuttle [K.R. Baker, H.L.W. Nuttle, Sequencing independent jobs with a single resource, Naval Research Logistics Quarterly 27 (1980) 499-510] studied the following single-variable-resource scheduling problem: sequencing n jobs for processing by a single resource to minimize a function of job completion times, when the availability of the resource varies over time. When the objective function to be minimized is the total weighted completion time, Baker and Nuttle conjectured that the problem is NP-hard. We show in this note that the conjecture is true.
Original languageEnglish
Pages (from-to)631-633
Number of pages3
JournalEuropean Journal of Operational Research
Volume178
Issue number2
DOIs
Publication statusPublished - 16 Apr 2007

Keywords

  • NP-hardness
  • Scheduling
  • Single-variable-resource
  • Total weighted completion time

ASJC Scopus subject areas

  • Information Systems and Management
  • Management Science and Operations Research
  • Statistics, Probability and Uncertainty
  • Applied Mathematics
  • Modelling and Simulation
  • Transportation

Cite this