Single machine scheduling to minimize total compression plus weighted flow cost is NP-hard

Guohua Wan; Benjamin P.C. Yen; Chung Lun Li

doi:10.1016/S0020-0190(01)00143-0

Single machine scheduling to minimize total compression plus weighted flow cost is NP-hard

Guohua Wan, Benjamin P.C. Yen, Chung Lun Li

Research output: Journal article publication › Journal article › Academic research › peer-review

29 Citations (Scopus)

Abstract

This article analyzes the computational complexity of a single machine scheduling problem to minimize total compression plus weighted flow cost. Vickson [Oper. Res. 28 (1980) 1155-1167] studied this problem and conjectured that it was NP-hard. The complexity of this problem remained open since then. We give a positive answer to this conjecture, showing that this problem is NP-hard.

Original language	English
Pages (from-to)	273-280
Number of pages	8
Journal	Information Processing Letters
Volume	79
Issue number	6
DOIs	https://doi.org/10.1016/S0020-0190(01)00143-0
Publication status	Published - 30 Sept 2001
Externally published	Yes

Keywords

Computational complexity
Scheduling

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

More information

10.1016/S0020-0190(01)00143-0

Cite this

@article{d916110a24d44e1bbb8f29482fe34078,

title = "Single machine scheduling to minimize total compression plus weighted flow cost is NP-hard",

abstract = "This article analyzes the computational complexity of a single machine scheduling problem to minimize total compression plus weighted flow cost. Vickson [Oper. Res. 28 (1980) 1155-1167] studied this problem and conjectured that it was NP-hard. The complexity of this problem remained open since then. We give a positive answer to this conjecture, showing that this problem is NP-hard.",

keywords = "Computational complexity, Scheduling",

author = "Guohua Wan and Yen, {Benjamin P.C.} and Li, {Chung Lun}",

year = "2001",

month = sep,

day = "30",

doi = "10.1016/S0020-0190(01)00143-0",

language = "English",

volume = "79",

pages = "273--280",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

T1 - Single machine scheduling to minimize total compression plus weighted flow cost is NP-hard

AU - Wan, Guohua

AU - Yen, Benjamin P.C.

AU - Li, Chung Lun

PY - 2001/9/30

Y1 - 2001/9/30

N2 - This article analyzes the computational complexity of a single machine scheduling problem to minimize total compression plus weighted flow cost. Vickson [Oper. Res. 28 (1980) 1155-1167] studied this problem and conjectured that it was NP-hard. The complexity of this problem remained open since then. We give a positive answer to this conjecture, showing that this problem is NP-hard.

AB - This article analyzes the computational complexity of a single machine scheduling problem to minimize total compression plus weighted flow cost. Vickson [Oper. Res. 28 (1980) 1155-1167] studied this problem and conjectured that it was NP-hard. The complexity of this problem remained open since then. We give a positive answer to this conjecture, showing that this problem is NP-hard.

KW - Computational complexity

KW - Scheduling

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

U2 - 10.1016/S0020-0190(01)00143-0

DO - 10.1016/S0020-0190(01)00143-0

M3 - Journal article

SN - 0020-0190

VL - 79

SP - 273

EP - 280

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

Single machine scheduling to minimize total compression plus weighted flow cost is NP-hard

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this