Single machine parallel batch scheduling subject to precedence constraints

Edwin Tai Chiu Cheng; Chi To Ng; J. J. Yuan; Z. H. Liu

doi:10.1002/nav.20035

Single machine parallel batch scheduling subject to precedence constraints

Edwin Tai Chiu Cheng, Chi To Ng, J. J. Yuan, Z. H. Liu

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

17 Citations (Scopus)

Abstract

We consider the single machine parallel batch scheduling problems to minimize makespan and total completion time, respectively, under precedence relations. The complexities of these two problems are reported as open in the literature. In this paper, we settle these open questions by showing that both problems are strongly NP-hard, even when the precedence relations are chains. When the processing times of jobs are directly agreeable or inversely agreeable with the precedence relations, there is an O(n2) time algorithm to minimize the makespan.

Original language	English
Pages (from-to)	949-958
Number of pages	10
Journal	Naval Research Logistics
Volume	51
Issue number	7
DOIs	https://doi.org/10.1002/nav.20035
Publication status	Published - 1 Oct 2004

Keywords

Parallel batching
Scheduling
Single machine

ASJC Scopus subject areas

Modelling and Simulation
Ocean Engineering
Management Science and Operations Research

More information

10.1002/nav.20035

Cite this

@article{cb3fe62de5e94f4fb89157ffa0123e4b,

title = "Single machine parallel batch scheduling subject to precedence constraints",

abstract = "We consider the single machine parallel batch scheduling problems to minimize makespan and total completion time, respectively, under precedence relations. The complexities of these two problems are reported as open in the literature. In this paper, we settle these open questions by showing that both problems are strongly NP-hard, even when the precedence relations are chains. When the processing times of jobs are directly agreeable or inversely agreeable with the precedence relations, there is an O(n2) time algorithm to minimize the makespan.",

keywords = "Parallel batching, Scheduling, Single machine",

author = "Cheng, {Edwin Tai Chiu} and Ng, {Chi To} and Yuan, {J. J.} and Liu, {Z. H.}",

year = "2004",

month = oct,

day = "1",

doi = "10.1002/nav.20035",

language = "English",

volume = "51",

pages = "949--958",

journal = "Naval Research Logistics",

issn = "0894-069X",

publisher = "John Wiley & Sons Inc.",

number = "7",

}

TY - JOUR

T1 - Single machine parallel batch scheduling subject to precedence constraints

AU - Cheng, Edwin Tai Chiu

AU - Ng, Chi To

AU - Yuan, J. J.

AU - Liu, Z. H.

PY - 2004/10/1

Y1 - 2004/10/1

N2 - We consider the single machine parallel batch scheduling problems to minimize makespan and total completion time, respectively, under precedence relations. The complexities of these two problems are reported as open in the literature. In this paper, we settle these open questions by showing that both problems are strongly NP-hard, even when the precedence relations are chains. When the processing times of jobs are directly agreeable or inversely agreeable with the precedence relations, there is an O(n2) time algorithm to minimize the makespan.

AB - We consider the single machine parallel batch scheduling problems to minimize makespan and total completion time, respectively, under precedence relations. The complexities of these two problems are reported as open in the literature. In this paper, we settle these open questions by showing that both problems are strongly NP-hard, even when the precedence relations are chains. When the processing times of jobs are directly agreeable or inversely agreeable with the precedence relations, there is an O(n2) time algorithm to minimize the makespan.

KW - Parallel batching

KW - Scheduling

KW - Single machine

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

U2 - 10.1002/nav.20035

DO - 10.1002/nav.20035

M3 - Journal article

SN - 0894-069X

VL - 51

SP - 949

EP - 958

JO - Naval Research Logistics

JF - Naval Research Logistics

IS - 7

ER -

Single machine parallel batch scheduling subject to precedence constraints

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this