Complexity of two dual criteria scheduling problems

Yumei Huo; J. Y.T. Leung; Hairong Zhao

doi:10.1016/j.orl.2006.01.007

Complexity of two dual criteria scheduling problems

Yumei Huo, J. Y.T. Leung, Hairong Zhao

Computer Science

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

14 Scopus citations

Abstract

In this article we answer the complexity question of two dual criteria scheduling problems which had been open for a long time. We show that both problems are binary NP-hard.

Original language	English (US)
Pages (from-to)	211-220
Number of pages	10
Journal	Operations Research Letters
Volume	35
Issue number	2
DOIs	https://doi.org/10.1016/j.orl.2006.01.007
State	Published - Mar 2007

All Science Journal Classification (ASJC) codes

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

Keywords

Dual criteria
NP-hard
Single machine

Access to Document

10.1016/j.orl.2006.01.007

Cite this

@article{2ee77fdd8d9f4b739f97741ab3f4c19f,

title = "Complexity of two dual criteria scheduling problems",

abstract = "In this article we answer the complexity question of two dual criteria scheduling problems which had been open for a long time. We show that both problems are binary NP-hard.",

keywords = "Dual criteria, NP-hard, Single machine",

author = "Yumei Huo and Leung, {J. Y.T.} and Hairong Zhao",

note = "Funding Information: The work of the second author is supported in part by the National Science Foundation Grant DMI-0300156. The authors would like to thank George Vairaktarakis for bringing the problems to their attention.",

year = "2007",

month = mar,

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

language = "English (US)",

volume = "35",

pages = "211--220",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - Complexity of two dual criteria scheduling problems

AU - Huo, Yumei

AU - Leung, J. Y.T.

AU - Zhao, Hairong

N1 - Funding Information: The work of the second author is supported in part by the National Science Foundation Grant DMI-0300156. The authors would like to thank George Vairaktarakis for bringing the problems to their attention.

PY - 2007/3

Y1 - 2007/3

N2 - In this article we answer the complexity question of two dual criteria scheduling problems which had been open for a long time. We show that both problems are binary NP-hard.

AB - In this article we answer the complexity question of two dual criteria scheduling problems which had been open for a long time. We show that both problems are binary NP-hard.

KW - Dual criteria

KW - NP-hard

KW - Single machine

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

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

U2 - 10.1016/j.orl.2006.01.007

DO - 10.1016/j.orl.2006.01.007

M3 - Article

AN - SCOPUS:33847037972

SN - 0167-6377

VL - 35

SP - 211

EP - 220

JO - Operations Research Letters

JF - Operations Research Letters

IS - 2

ER -

Complexity of two dual criteria scheduling problems

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this