Complexity of a scheduling problem with controllable processing times

Byung Cheon Choi; Joseph Y.T. Leung; Michael L. Pinedo

doi:10.1016/j.orl.2009.10.011

Complexity of a scheduling problem with controllable processing times

Byung Cheon Choi
, Joseph Y.T. Leung
, Michael L. Pinedo

Computer Science

Research output: Contribution to journal › Article › peer-review

12 Scopus citations

Abstract

We consider the problem of scheduling a set of independent jobs on a single machine so as to minimize the total weighted completion time, subject to the constraint that the total compression cost is less than or equal to a fixed amount. The complexity of this problem is mentioned as an open problem. In this note we show that the problem is NP-hard.

Original language	English (US)
Pages (from-to)	123-126
Number of pages	4
Journal	Operations Research Letters
Volume	38
Issue number	2
DOIs	https://doi.org/10.1016/j.orl.2009.10.011
State	Published - Mar 2010

All Science Journal Classification (ASJC) codes

Software
Management Science and Operations Research
Industrial and Manufacturing Engineering
Applied Mathematics

Keywords

Controllable processing time
NP-hard
Single machine
Total weighted completion time

Access to Document

10.1016/j.orl.2009.10.011

Cite this

@article{658072a46d1e4cd390647f743e2e4839,

title = "Complexity of a scheduling problem with controllable processing times",

abstract = "We consider the problem of scheduling a set of independent jobs on a single machine so as to minimize the total weighted completion time, subject to the constraint that the total compression cost is less than or equal to a fixed amount. The complexity of this problem is mentioned as an open problem. In this note we show that the problem is NP-hard.",

keywords = "Controllable processing time, NP-hard, Single machine, Total weighted completion time",

author = "Choi, \{Byung Cheon\} and Leung, \{Joseph Y.T.\} and Pinedo, \{Michael L.\}",

note = "Funding Information: Byung-Cheon Choi was supported in part by the Korea Research Foundation Grant KRF-2008-357-D00289. Joseph Y-T. Leung was supported in part by the NSF Grant DMI-0556010. Michael L. Pinedo was supported in part by the NSF Grant DMI-0555999. ",

year = "2010",

month = mar,

doi = "10.1016/j.orl.2009.10.011",

language = "English (US)",

volume = "38",

pages = "123--126",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Complexity of a scheduling problem with controllable processing times

AU - Choi, Byung Cheon

AU - Leung, Joseph Y.T.

AU - Pinedo, Michael L.

N1 - Funding Information: Byung-Cheon Choi was supported in part by the Korea Research Foundation Grant KRF-2008-357-D00289. Joseph Y-T. Leung was supported in part by the NSF Grant DMI-0556010. Michael L. Pinedo was supported in part by the NSF Grant DMI-0555999.

PY - 2010/3

Y1 - 2010/3

N2 - We consider the problem of scheduling a set of independent jobs on a single machine so as to minimize the total weighted completion time, subject to the constraint that the total compression cost is less than or equal to a fixed amount. The complexity of this problem is mentioned as an open problem. In this note we show that the problem is NP-hard.

AB - We consider the problem of scheduling a set of independent jobs on a single machine so as to minimize the total weighted completion time, subject to the constraint that the total compression cost is less than or equal to a fixed amount. The complexity of this problem is mentioned as an open problem. In this note we show that the problem is NP-hard.

KW - Controllable processing time

KW - NP-hard

KW - Single machine

KW - Total weighted completion time

UR - https://www.scopus.com/pages/publications/75949090344

UR - https://www.scopus.com/pages/publications/75949090344#tab=citedBy

U2 - 10.1016/j.orl.2009.10.011

DO - 10.1016/j.orl.2009.10.011

M3 - Article

AN - SCOPUS:75949090344

SN - 0167-6377

VL - 38

SP - 123

EP - 126

JO - Operations Research Letters

JF - Operations Research Letters

IS - 2

ER -

Complexity of a scheduling problem with controllable processing times

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this