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.
- 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