Competitive ratio of list scheduling on uniform machines and randomized heuristics

DOI10.1007/S10951-010-0177-XMaRDI QIDQ633543zbMATH OpenOpenAlexFDO

Authors Antoine Musitelli, Jean-Marc Nicoletti

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

analysis of algorithmscompetitive ratioonline algorithmsrandomized scheduling

Mathematics Subject Classification ID

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

Recommendations

• Randomized on-line scheduling on two uniform machines
• scientific article; zbMATH DE number 1305421
• On the optimality of list scheduling for online uniform machines scheduling
• Randomized algorithms for that ancient scheduling problem
• New algorithms for an ancient scheduling problem.

Cites work

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

Cited in

(6)

• A survey on makespan minimization in semi-online environments
• Online scheduling on uniform machines with two hierarchies
• A lower bound on deterministic online algorithms for scheduling on related machines without preemption
• Lower bounds for online makespan minimization on a small number of related machines
• List Scheduling in Order of α-Points on a Single Machine
• Semi-online scheduling on two uniform parallel machines with initial lookahead

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q633543)