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.
Original language | English |
---|---|
Pages (from-to) | 349-352 |
Number of pages | 4 |
Journal | Operations Research Letters |
Volume | 40 |
Issue number | 5 |
DOIs | |
Publication status | Published - 1 Sept 2012 |
Keywords
- Competitive ratio
- Multiprocessor scheduling
- Online algorithms
- Semi-online algorithms
ASJC Scopus subject areas
- Software
- Management Science and Operations Research
- Industrial and Manufacturing Engineering
- Applied Mathematics