Minimizing the number of late jobs on unrelated machines

Jianzhong Du; Joseph Y.T. Leung

doi:10.1016/0167-6377(91)90032-K

Minimizing the number of late jobs on unrelated machines

Jianzhong Du, Joseph Y.T. Leung

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

7 Scopus citations

Abstract

We consider the problem of preemptively scheduling a set of independent jobs with release times on an arbitrary number of unrelated machines so as to minimize the number of late jobs. We show that the problem is NP-hard in the strong sense, giving the first strong NP-hardness result for this problem.

Original language	English (US)
Pages (from-to)	153-158
Number of pages	6
Journal	Operations Research Letters
Volume	10
Issue number	3
DOIs	https://doi.org/10.1016/0167-6377(91)90032-K
State	Published - Apr 1991
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Keywords

due date
late job
preemptive scheduling
release time
strong NP-hardness
unrelated machines

Access to Document

10.1016/0167-6377(91)90032-K

Cite this

@article{c3ce7bc4d53a4fcc9ce7860c8701b5e3,

title = "Minimizing the number of late jobs on unrelated machines",

abstract = "We consider the problem of preemptively scheduling a set of independent jobs with release times on an arbitrary number of unrelated machines so as to minimize the number of late jobs. We show that the problem is NP-hard in the strong sense, giving the first strong NP-hardness result for this problem.",

keywords = "due date, late job, preemptive scheduling, release time, strong NP-hardness, unrelated machines",

author = "Jianzhong Du and Leung, {Joseph Y.T.}",

note = "Funding Information: * The research reported here was supported in part by ONR Grant No. N00014-87-K-0833 and in part by a grant from Texas Instruments, Inc.",

year = "1991",

month = apr,

doi = "10.1016/0167-6377(91)90032-K",

language = "English (US)",

volume = "10",

pages = "153--158",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Minimizing the number of late jobs on unrelated machines

AU - Du, Jianzhong

AU - Leung, Joseph Y.T.

N1 - Funding Information: * The research reported here was supported in part by ONR Grant No. N00014-87-K-0833 and in part by a grant from Texas Instruments, Inc.

PY - 1991/4

Y1 - 1991/4

N2 - We consider the problem of preemptively scheduling a set of independent jobs with release times on an arbitrary number of unrelated machines so as to minimize the number of late jobs. We show that the problem is NP-hard in the strong sense, giving the first strong NP-hardness result for this problem.

AB - We consider the problem of preemptively scheduling a set of independent jobs with release times on an arbitrary number of unrelated machines so as to minimize the number of late jobs. We show that the problem is NP-hard in the strong sense, giving the first strong NP-hardness result for this problem.

KW - due date

KW - late job

KW - preemptive scheduling

KW - release time

KW - strong NP-hardness

KW - unrelated machines

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

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

U2 - 10.1016/0167-6377(91)90032-K

DO - 10.1016/0167-6377(91)90032-K

M3 - Article

AN - SCOPUS:24944572166

SN - 0167-6377

VL - 10

SP - 153

EP - 158

JO - Operations Research Letters

JF - Operations Research Letters

IS - 3

ER -

Minimizing the number of late jobs on unrelated machines

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this