Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/18394
Title: Single machine parallel batch scheduling subject to precedence constraints
Authors: Cheng, TCE 
Ng, CT 
Yuan, JJ
Liu, ZH
Keywords: Parallel batching
Scheduling
Single machine
Issue Date: 2004
Publisher: John Wiley & Sons
Source: Naval research logistics, 2004, v. 51, no. 7, p. 949-958 How to cite?
Journal: Naval research logistics 
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.
URI: http://hdl.handle.net/10397/18394
ISSN: 0894-069X
EISSN: 1520-6750
DOI: 10.1002/nav.20035
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

12
Last Week
0
Last month
1
Citations as of Sep 23, 2017

WEB OF SCIENCETM
Citations

13
Last Week
0
Last month
0
Citations as of Sep 22, 2017

Page view(s)

67
Last Week
1
Last month
Checked on Sep 25, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.