On randomized online scheduling

DOI10.1145/509907.509930MaRDI QIDQ3579202zbMATH OpenOpenAlexFDO

Authors Susanne Albers

Publication date 5 August 2010

Published in Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Parallel algorithms in computer science (68W10) Deterministic scheduling theory in operations research (90B35)

Cited in

(25)

• Extension of algorithm list scheduling for a semi-online scheduling problem
• Preemptive online scheduling: Optimal algorithms for all speeds
• A survey on makespan minimization in semi-online environments
• Improved lower bounds for online scheduling to minimize total stretch
• Multiprofessor scheduling
• Pseudo lower bounds for online parallel machine scheduling
• Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing
• Improved randomized online scheduling of intervals and jobs
• Semi-online scheduling jobs with tightly-grouped processing times on three identical machines
• A survey on combinatorial optimization in dynamic environments
• Robust polynomial-time approximation schemes for parallel machine scheduling with job arrivals and departures
• Fair scheduling via iterative quasi-uniform sampling
• Improved Randomized Online Scheduling of Unit Length Intervals and Jobs
• New upper and lower bounds for online scheduling with machine cost
• Semi-online scheduling revisited
• Online algorithms with advice for bin packing and scheduling problems
• On robust online scheduling algorithms
• Online two-dimensional load balancing
• Lower bounds for online scheduling on four processors
• Randomized algorithms for fully online multiprocessor scheduling with testing
• Efficient job scheduling algorithms with multi-type contentions
• Scheduling with testing on multiple identical parallel machines
• Online parallel machines scheduling with two hierarchies
• Online scheduling with reassignment
• Randomized priority algorithms

This page was built for publication: On randomized online scheduling

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