A new algorithm for online uniform-machine scheduling to minimize the makespan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

11 Citations (Scopus)

Abstract

We consider the online scheduling problem with m - 1, m {greater than or slanted equal to} 2, uniform machines each with a processing speed of 1, and one machine with a speed of s, 1 {less-than or slanted equal to} s {less-than or slanted equal to} 2, to minimize the makespan. The well-known list scheduling (LS) algorithm has a worst-case bound of frac(( 3 m - 1 ), ( m + 1 )) [Y. Cho, S. Sahni, Bounds for list schedules on uniform processors, SIAM J. Comput. 9 (1980) 91-103]. An algorithm with a better competitive ratio was proposed in [R. Li, L. Shi, An on-line algorithm for some uniform processor scheduling, SIAM J. Comput. 27 (1998) 414-422]. It has a worst-case bound of 2.8795 for a big m and s = 2. In this note we present a 2.45-competitive algorithm for m {greater than or slanted equal to} 4 and any s, 1 {less-than or slanted equal to} s {less-than or slanted equal to} 2.
Original languageEnglish
Pages (from-to)102-105
Number of pages4
JournalInformation Processing Letters
Volume99
Issue number3
DOIs
Publication statusPublished - 16 Aug 2006

Keywords

  • Competitive ratio
  • Multi-machine scheduling
  • Online algorithms
  • Uniform machines

ASJC Scopus subject areas

  • Computational Theory and Mathematics

Cite this