The NP-completeness of the n/m/parallel/Cmaxpreemptive due-date scheduling problem

Edwin Tai Chiu Cheng; C. C.S. Sin

doi:10.1016/0895-7177(90)90375-W

The NP-completeness of the n/m/parallel/C_maxpreemptive due-date scheduling problem

Edwin Tai Chiu Cheng
, C. C.S. Sin

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

1 Citation (Scopus)

Abstract

We present a proof of the NP-completeness of the problem to schedule n simultaneously available jobs on m parallel machines to minimize the maximum job completion time subject to no jobs being tardy.

Original language	English
Pages (from-to)	93-94
Number of pages	2
Journal	Mathematical and Computer Modelling
Volume	13
Issue number	3
DOIs	https://doi.org/10.1016/0895-7177(90)90375-W
Publication status	Published - 1 Jan 1990
Externally published	Yes

ASJC Scopus subject areas

Modelling and Simulation
Computer Science Applications

More information

10.1016/0895-7177(90)90375-W

Cite this

@article{730edb9eea89499a881e53499a0fb9cb,

title = "The NP-completeness of the n/m/parallel/Cmaxpreemptive due-date scheduling problem",

abstract = "We present a proof of the NP-completeness of the problem to schedule n simultaneously available jobs on m parallel machines to minimize the maximum job completion time subject to no jobs being tardy.",

author = "Cheng, \{Edwin Tai Chiu\} and Sin, \{C. C.S.\}",

year = "1990",

month = jan,

day = "1",

doi = "10.1016/0895-7177(90)90375-W",

language = "English",

volume = "13",

pages = "93--94",

journal = "Mathematical and Computer Modelling",

issn = "0895-7177",

publisher = "Elsevier Ltd",

number = "3",

}

TY - JOUR

T1 - The NP-completeness of the n/m/parallel/Cmaxpreemptive due-date scheduling problem

AU - Cheng, Edwin Tai Chiu

AU - Sin, C. C.S.

PY - 1990/1/1

Y1 - 1990/1/1

N2 - We present a proof of the NP-completeness of the problem to schedule n simultaneously available jobs on m parallel machines to minimize the maximum job completion time subject to no jobs being tardy.

AB - We present a proof of the NP-completeness of the problem to schedule n simultaneously available jobs on m parallel machines to minimize the maximum job completion time subject to no jobs being tardy.

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

U2 - 10.1016/0895-7177(90)90375-W

DO - 10.1016/0895-7177(90)90375-W

M3 - Journal article

SN - 0895-7177

VL - 13

SP - 93

EP - 94

JO - Mathematical and Computer Modelling

JF - Mathematical and Computer Modelling

IS - 3

ER -

The NP-completeness of the n/m/parallel/C_maxpreemptive due-date scheduling problem

Abstract

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this