Algorithms better than LPT for semi-online scheduling with decreasing processing times

Edwin Tai Chiu Cheng, Hans Kellerer, Vladimir Kotov

Research output: Journal article publicationJournal articleAcademic researchpeer-review

5 Citations (Scopus)

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 languageEnglish
Pages (from-to)349-352
Number of pages4
JournalOperations Research Letters
Volume40
Issue number5
DOIs
Publication statusPublished - 1 Sep 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

Cite this