Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Competitive ratio of List Scheduling on uniform machines and randomized heuristics
 
conference paper

Competitive ratio of List Scheduling on uniform machines and randomized heuristics

Musitelli, Antoine
•
Nicoletti, Jean-Marc
2011
Journal Of Scheduling
Workshop on New Challenges in Scheduling Theory

We study online scheduling on m uniform machines, where m - 1 of them have a reference speed 1 and the last one a speed s with 0 <= s <= 1. The competitive ratio of the well-known List Scheduling (LS) algorithm is determined. For some values of s and m = 3, LS is proven to be the best deterministic algorithm. We describe a randomized heuristic for m machines. Finally, for the case m = 3, we develop and analyze the competitive ratio of a randomized algorithm which outperforms LS for any s.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

10951_2010_Article_177.pdf

Type

Publisher's Version

Version

http://purl.org/coar/version/c_970fb48d4fbd8a85

Access type

openaccess

Size

464.01 KB

Format

Adobe PDF

Checksum (MD5)

a3b3c424d0668eacdaedabe0b6ba0f8f

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés