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

13
Last Week
0
Last month
1
Citations as of Nov 8, 2018

WEB OF SCIENCETM
Citations

13
Last Week
0
Last month
0
Citations as of Nov 14, 2018

Page view(s)

103
Last Week
3
Last month
Citations as of Nov 12, 2018

Google ScholarTM

Check

Altmetric


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