Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/654
Title: Scheduling a batch-processing machine subject to precedence constraints, release dates and identical processing times
Authors: Cheng, TCE 
Yuan, JJ
Yang, AF
Keywords: Scheduling
Batch processing
Precedence constraints
Release dates
Identical processing times
Algorithms
Issue Date: Apr-2005
Publisher: Pergamon Press
Source: Computers and operations research, Apr. 2005, v. 32, no. 4, p. 849-859 How to cite?
Journal: Computers and operations research 
Abstract: We consider the single machine parallel-batching scheduling problem with precedence relations, release dates and identical processing times to minimize a regular objective function. When the processing times are unit, we give an O(n²) time optimal algorithm. When there are no precedence relations, we solve this problem by dynamic programming in O(n³) time. When the precedence relations are "layerly complete", we solve this problem by a dynamic programming algorithm that runs in O(n[sup 7]) time. For the total weighted completion time minimization problem, we give an O(n²) time [3/2]-approximation algorithm. For the makespan minimization problem, we give an O(n²) time optimal algorithm and an expression of the minimum makespan.
URI: http://hdl.handle.net/10397/654
ISSN: 0305-0548
EISSN: 1873-765X
DOI: 10.1016/j.cor.2003.09.001
Rights: Computers & Operations Research © 2003 Elsevier Ltd. The journal web site is located at http://www.sciencedirect.com.
Appears in Collections:Journal/Magazine Article

Files in This Item:
File Description SizeFormat 
p-batch-identical.pdfPre-published version125.1 kBAdobe PDFView/Open
Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

21
Last Week
0
Last month
0
Citations as of Jun 26, 2017

WEB OF SCIENCETM
Citations

17
Last Week
0
Last month
0
Citations as of Jun 21, 2017

Page view(s)

544
Last Week
2
Last month
Checked on Jun 25, 2017

Download(s)

577
Checked on Jun 25, 2017

Google ScholarTM

Check

Altmetric



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