Bounding the Power of Preemption in Randomized Scheduling

DOI10.1137/S0097539795283292MaRDI QIDQ4210081zbMATH OpenOpenAlexFDO

Authors Ran Canetti, Sandy Irani

Publication date 20 September 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539795283292

zbMATH Keywords

lower boundspreemptionrandomized algorithmsscheduling

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Communication networks in operations research (90B18)

Recommendations

• scientific article; zbMATH DE number 1263237
• The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders
• The power of preemption on unrelated machines and applications to scheduling orders
• A tight 2-approximation for preemptive stochastic scheduling
• On PreemptiveResource Constrained Scheduling: Polynomial-Time Approximation Schemes
• scientific article; zbMATH DE number 2086932
• An Approximation Algorithm for Preemptive Scheduling on Parallel-Task Systems
• Real-time \(k\)-bounded preemptive scheduling
• Preemption-light multiprocessor scheduling of sporadic tasks with high utilisation bound
• Preemptive Scheduling to Minimize Maximum Completion Time on Uniform Processors with Memory Constraints

Cited in

(25)

• Online interval scheduling: Randomized and multiprocessor cases
• Preemptive scheduling in overloaded systems.
• Online interval scheduling with a bounded number of failures
• Competitive algorithms for multistage online scheduling
• Improved randomized online scheduling of intervals and jobs
• Multistage interval scheduling games
• Online interval scheduling to maximize total satisfaction
• Online scheduling of bounded length jobs to maximize throughput
• Online scheduling of jobs with fixed start times on related machines
• Online interval scheduling on a single machine with finite lookahead
• Improved Randomized Results for That Interval Selection Problem
• On the Value of Preemption in Scheduling
• Improved Randomized Online Scheduling of Unit Length Intervals and Jobs
• Online selection of intervals and t-intervals
• scientific article; zbMATH DE number 1263237 (Why is no real title available?)
• On-line scheduling of equal-length intervals on parallel machines
• scientific article; zbMATH DE number 2086629 (Why is no real title available?)
• Interval scheduling on related machines
• Optimally Handling Commitment Issues in Online Throughput Maximization
• The power of preemption on unrelated machines and applications to scheduling orders
• A general framework for handling commitment in online throughput maximization
• Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams.
• O(1/) is the answer in online weighted throughput maximization
• Fixed interval scheduling: models, applications, computational complexity and algorithms
• Improved randomized results for the interval selection problem

Describes a project that uses

Uses Software

• MOCA

This page was built for publication: Bounding the Power of Preemption in Randomized Scheduling

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