Competitive ratio of list scheduling on uniform machines and randomized heuristics

DOI10.1007/s10951-010-0177-xzbMath1208.90084OpenAlexW1996873799MaRDI QIDQ633543

Jean-Marc Nicoletti, Antoine Musitelli

Publication date: 1 April 2011

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://infoscience.epfl.ch/record/171559/files/10951_2010_Article_177.pdf

zbMATH Keywords

online algorithmsanalysis of algorithmscompetitive ratiorandomized scheduling

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Stochastic scheduling theory in operations research (90B36) Online algorithms; streaming algorithms (68W27)

Related Items (4)

A survey on makespan minimization in semi-online environments ⋮ Online scheduling on uniform machines with two hierarchies ⋮ Lower bounds for online makespan minimization on a small number of related machines ⋮ A lower bound on deterministic online algorithms for scheduling on related machines without preemption

Cites Work

• A new algorithm for online uniform-machine scheduling to minimize the makespan
• New algorithms for an ancient scheduling problem.
• Dynamic scheduling on parallel machines
• Online randomized multiprocessor scheduling
• Competitive paging with locality of reference
• Bounds for List Schedules on Uniform Processors
• An On-Line Algorithm for Some Uniform Processor Scheduling
• Randomized on-line scheduling on two uniform machines
• Unnamed Item

This page was built for publication: Competitive ratio of list scheduling on uniform machines and randomized heuristics