Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines

DOI10.1145/380752.380782zbMath1323.68048OpenAlexW2060640049MaRDI QIDQ5175957

Luca Becchetti, Stefano Leonardi

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/380752.380782

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25) Randomized algorithms (68W20) Theory of operating systems (68N25) Online algorithms; streaming algorithms (68W27)

Related Items (4)

Semi-clairvoyant scheduling ⋮ Minimizing the mean slowdown in a single-server queue ⋮ Minimizing the mean slowdown in the M/G/1 queue ⋮ Greed Works—Online Algorithms for Unrelated Machine Stochastic Scheduling

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)

This page was built for publication: Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines