On the NP-completeness of the n/m/parallel/σi∈m{σwjσtj} scheduling problem

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

doi:10.1016/0893-9659(89)90095-5

On the NP-completeness of the n/m/parallel/σ_i∈m{σw_jσt_j} scheduling problem

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

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

1 Citation (Scopus)

Abstract

We present in this paper a proof of the NP-completeness of the problem to schedule n simultaneously available jobs on m parallel machines to minimize the weighted sum of machine makespans.

Original language	English
Pages (from-to)	389-390
Number of pages	2
Journal	Applied Mathematics Letters
Volume	2
Issue number	4
DOIs	https://doi.org/10.1016/0893-9659(89)90095-5
Publication status	Published - 1 Jan 1989
Externally published	Yes

ASJC Scopus subject areas

Applied Mathematics

More information

10.1016/0893-9659(89)90095-5

Cite this

@article{46f8b8b52b48496c8eb5c5bb24241619,

title = "On the NP-completeness of the n/m/parallel/σi∈m{σwjσtj} scheduling problem",

abstract = "We present in this paper a proof of the NP-completeness of the problem to schedule n simultaneously available jobs on m parallel machines to minimize the weighted sum of machine makespans.",

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

year = "1989",

month = jan,

day = "1",

doi = "10.1016/0893-9659(89)90095-5",

language = "English",

volume = "2",

pages = "389--390",

journal = "Applied Mathematics Letters",

issn = "0893-9659",

publisher = "Elsevier Ltd",

number = "4",

}

TY - JOUR

T1 - On the NP-completeness of the n/m/parallel/σi∈m{σwjσtj} scheduling problem

AU - Sin, C. C.S.

AU - Cheng, Edwin Tai Chiu

PY - 1989/1/1

Y1 - 1989/1/1

N2 - We present in this paper a proof of the NP-completeness of the problem to schedule n simultaneously available jobs on m parallel machines to minimize the weighted sum of machine makespans.

AB - We present in this paper a proof of the NP-completeness of the problem to schedule n simultaneously available jobs on m parallel machines to minimize the weighted sum of machine makespans.

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

U2 - 10.1016/0893-9659(89)90095-5

DO - 10.1016/0893-9659(89)90095-5

M3 - Journal article

VL - 2

SP - 389

EP - 390

JO - Applied Mathematics Letters

JF - Applied Mathematics Letters

SN - 0893-9659

IS - 4