Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/20228
Title: Parallel machine scheduling with batch delivery costs
Authors: Wang, G
Cheng, TCE 
Issue Date: 2000
Publisher: Elsevier
Source: International journal of production economics, 2000, v. 68, no. 2, p. 177-183 How to cite?
Journal: International journal of production economics 
Abstract: We consider a scheduling problem in which n independent and simultaneously available jobs are to be processed on m parallel machines. The jobs are delivered in batches and the delivery date of a batch is equal to the completion time of the last job in the batch. The delivery cost depends on the number of deliveries. The objective is to minimize the sum of the total flow time and delivery cost. We first show that the problem is NP-complete in the ordinary sense even when m = 2, and NP-complete in the strong sense when m is arbitrary. Then we develop a dynamic programming algorithm to solve the problem. The algorithm is pseudopolynomial when m is constant and the number of batches has a fixed upper bound. Finally, we identify two polynomially solvable cases by introducing their corresponding solution methods.
URI: http://hdl.handle.net/10397/20228
ISSN: 0925-5273
DOI: 10.1016/S0925-5273(99)00105-X
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

61
Last Week
1
Last month
1
Citations as of Sep 24, 2017

WEB OF SCIENCETM
Citations

46
Last Week
0
Last month
0
Citations as of Sep 22, 2017

Page view(s)

42
Last Week
2
Last month
Checked on Sep 25, 2017

Google ScholarTM

Check

Altmetric



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