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 |
Issue Date: | Apr-2005 | Source: | Computers and operations research, Apr. 2005, v. 32, no. 4, p. 849-859 | 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. | Keywords: | Scheduling Batch processing Precedence constraints Release dates Identical processing times Algorithms |
Publisher: | Pergamon Press | Journal: | Computers and operations research | 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 | Size | Format | |
|---|---|---|---|---|
| p-batch-identical.pdf | Pre-published version | 125.1 kB | Adobe PDF | View/Open |
Access
View full-text via PolyU eLinks 
Page views
120
Last Week
1
1
Last month
Citations as of Nov 22, 2023
Downloads
180
Citations as of Nov 22, 2023
SCOPUSTM
Citations
25
Last Week
0
0
Last month
0
0
Citations as of Nov 23, 2023
WEB OF SCIENCETM
Citations
22
Last Week
0
0
Last month
0
0
Citations as of Nov 30, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.