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
PIRA download icon_1.1View/Download Contents

SCOPUSTM   
Citations

23
Last Week
2
Last month
0
Citations as of Aug 13, 2018

WEB OF SCIENCETM
Citations

20
Last Week
1
Last month
0
Citations as of Aug 21, 2018

Page view(s)

577
Last Week
0
Last month
Citations as of Aug 14, 2018

Download(s)

600
Citations as of Aug 14, 2018

Google ScholarTM

Check

Altmetric


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