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
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
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 Jun 22, 2017

WEB OF SCIENCETM
Citations

2
Last Week
0
Last month
0
Citations as of May 13, 2017

Page view(s)

72
Last Week
2
Last month
Checked on Jun 25, 2017

Google ScholarTM

Check

Altmetric



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