Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/33206
Title: Algorithms better than LPT for semi-online scheduling with decreasing processing times
Authors: Cheng, TCE 
Kellerer, H
Kotov, V
Keywords: Competitive ratio
Multiprocessor scheduling
Online algorithms
Semi-online algorithms
Issue Date: 2012
Publisher: North-Holland
Source: Operations research letters, 2012, v. 40, no. 5, p. 349-352 How to cite?
Journal: Operations research letters 
Abstract: We consider the semi-online multiprocessor scheduling problem with m identical, parallel machines to minimize the makespan, where the jobs arrive in decreasing order of processing times. The famous Longest Processing Time (LPT) algorithm by Graham (1966) [4] for the classical offline multiprocessor scheduling problem schedules the jobs in decreasing order of processing times and has a worst-case bound of 43-1(3m). So far, no algorithm with a better competitive ratio than the LPT algorithm has been given for the semi-online scheduling problem with decreasing processing times. In this note, we present a 54-competitive algorithm for m<3 and an algorithm that is the best possible for m=3, i.e. an algorithm with competitive ratio (1+37)6.
URI: http://hdl.handle.net/10397/33206
ISSN: 0167-6377
EISSN: 1872-7468
DOI: 10.1016/j.orl.2012.05.009
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

1
Last Week
0
Last month
0
Citations as of Aug 21, 2017

WEB OF SCIENCETM
Citations

2
Last Week
0
Last month
0
Citations as of Aug 12, 2017

Page view(s)

80
Last Week
3
Last month
Checked on Aug 20, 2017

Google ScholarTM

Check

Altmetric



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