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

Deterministic scheduling theory in operations research (90B35) 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)

Cited in

(22)

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