Scheduling groups of unit length jobs on two identical parallel machines

Zhaohui Liu; Wenci Yu; Edwin Tai Chiu Cheng

doi:10.1016/S0020-0190(99)00026-5

Scheduling groups of unit length jobs on two identical parallel machines

Zhaohui Liu, Wenci Yu, Edwin Tai Chiu Cheng

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

9 Citations (Scopus)

Abstract

The problem of scheduling groups of unit length jobs with group sub-lotting on two identical parallel machines to minimize the total completion time is known to be NP-hard. In this paper, we present a pseudopolynomial-time algorithm for the problem, thus establishing that the problem is NP-hard in the ordinary sense. We also show that the problem remains NP-hard even for the case with any fixed positive set-up time.

Original language	English
Pages (from-to)	275-281
Number of pages	7
Journal	Information Processing Letters
Volume	69
Issue number	6
DOIs	https://doi.org/10.1016/S0020-0190(99)00026-5
Publication status	Published - 26 Mar 1999

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

More information

10.1016/S0020-0190(99)00026-5

Cite this

@article{5ebb10dddd9348ceaea04392fb76098a,

title = "Scheduling groups of unit length jobs on two identical parallel machines",

abstract = "The problem of scheduling groups of unit length jobs with group sub-lotting on two identical parallel machines to minimize the total completion time is known to be NP-hard. In this paper, we present a pseudopolynomial-time algorithm for the problem, thus establishing that the problem is NP-hard in the ordinary sense. We also show that the problem remains NP-hard even for the case with any fixed positive set-up time.",

author = "Zhaohui Liu and Wenci Yu and Cheng, {Edwin Tai Chiu}",

year = "1999",

month = mar,

day = "26",

doi = "10.1016/S0020-0190(99)00026-5",

language = "English",

volume = "69",

pages = "275--281",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

T1 - Scheduling groups of unit length jobs on two identical parallel machines

AU - Liu, Zhaohui

AU - Yu, Wenci

AU - Cheng, Edwin Tai Chiu

PY - 1999/3/26

Y1 - 1999/3/26

N2 - The problem of scheduling groups of unit length jobs with group sub-lotting on two identical parallel machines to minimize the total completion time is known to be NP-hard. In this paper, we present a pseudopolynomial-time algorithm for the problem, thus establishing that the problem is NP-hard in the ordinary sense. We also show that the problem remains NP-hard even for the case with any fixed positive set-up time.

AB - The problem of scheduling groups of unit length jobs with group sub-lotting on two identical parallel machines to minimize the total completion time is known to be NP-hard. In this paper, we present a pseudopolynomial-time algorithm for the problem, thus establishing that the problem is NP-hard in the ordinary sense. We also show that the problem remains NP-hard even for the case with any fixed positive set-up time.

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

U2 - 10.1016/S0020-0190(99)00026-5

DO - 10.1016/S0020-0190(99)00026-5

M3 - Journal article

SN - 0020-0190

VL - 69

SP - 275

EP - 281

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

Scheduling groups of unit length jobs on two identical parallel machines

Abstract

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this