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: Elsevier Ltd.
Source: Computers & operations research, Apr. 2005, v. 32, no. 4, p. 849-859 How to cite?
Journal: Computers & 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
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 May 1, 2016

WEB OF SCIENCETM
Citations

16
Last Week
0
Last month
0
Citations as of Apr 30, 2016

Page view(s)

506
Last Week
0
Last month
Checked on May 1, 2016

Download(s)

549
Checked on May 1, 2016

Google ScholarTM

Check

Altmetric



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