Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/29680
Title: An improved on-line algorithm for single parallel-batch machine scheduling with delivery times
Authors: Tian, J
Cheng, TCE 
Ng, CT 
Yuan, J
Keywords: Competitive ratio
Delivery times
On-line scheduling
Parallel-batch machine
Issue Date: 2012
Source: Discrete applied mathematics, 2012, v. 160, no. 7-8, p. 1191-1210 How to cite?
Journal: Discrete Applied Mathematics 
Abstract: We study an on-line single parallel-batch machine scheduling problem where each job has a processing time and a delivery time. Jobs arrive over time and the batch capacity is unbounded. Jobs can be processed in a common batch, and each job is delivered independently and immediately at its completion time on the machine. The objective is to minimize the time by which all the jobs are delivered. We provide an on-line algorithm with a competitive ratio 22-1≈1.828, which improves on a 2-competitive on-line algorithm for this problem in the literature.
URI: http://hdl.handle.net/10397/29680
ISSN: 0166-218X
DOI: 10.1016/j.dam.2011.12.002
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

4
Last Week
0
Last month
0
Citations as of Feb 24, 2017

WEB OF SCIENCETM
Citations

3
Last Week
0
Last month
Citations as of Feb 17, 2017

Page view(s)

30
Last Week
0
Last month
Checked on Feb 26, 2017

Google ScholarTM

Check

Altmetric



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