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

J. J. Yuan; Edwin Tai Chiu Cheng; Chi To Ng

doi:10.1016/j.ejor.2006.02.014

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

J. J. Yuan, Edwin Tai Chiu Cheng, Chi To Ng

Research output: Journal article publication › Journal article › Academic research › peer-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 language	English
Pages (from-to)	631-633
Number of pages	3
Journal	European Journal of Operational Research
Volume	178
Issue number	2
DOIs	https://doi.org/10.1016/j.ejor.2006.02.014
Publication status	Published - 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

More information

10.1016/j.ejor.2006.02.014

http://hdl.handle.net/10397/661

Cite this

@article{022c7bbeda0b4c1391cd041c957a4461,

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

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

keywords = "NP-hardness, Scheduling, Single-variable-resource, Total weighted completion time",

author = "Yuan, {J. J.} and Cheng, {Edwin Tai Chiu} and Ng, {Chi To}",

year = "2007",

month = apr,

day = "16",

doi = "10.1016/j.ejor.2006.02.014",

language = "English",

volume = "178",

pages = "631--633",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

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

AU - Yuan, J. J.

AU - Cheng, Edwin Tai Chiu

AU - Ng, Chi To

PY - 2007/4/16

Y1 - 2007/4/16

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

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

KW - NP-hardness

KW - Scheduling

KW - Single-variable-resource

KW - Total weighted completion time

UR - http://www.scopus.com/inward/record.url?scp=33750989641&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2006.02.014

DO - 10.1016/j.ejor.2006.02.014

M3 - Journal article

SN - 0377-2217

VL - 178

SP - 631

EP - 633

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 2

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this