Space-efficient scheduling of stochastically generated tasks

2010/04/24 by Tomáš Brázdil, Tomá vs Brázdil, Javier Esparza +6
Computer Science · #Distributed and Parallel Computing Systems #FOS: Computer and information sciences #Interconnection Networks and Systems #Parallel Computing and Optimization Techniques #Performance (cs.PF) #cs.PF

paper · pdf · doi:10.48550/arxiv.1004.4286

technical report accompanying an ICALP'10 paper

openalex publication_date 2010/04/24 · arxiv created 2010/04/27 · arxiv updated 2010/04/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the problem of scheduling tasks for execution by a processor when the tasks can stochastically generate new tasks. Tasks can be of different types, and each type has a fixed, known probability of generating other tasks. We present results on the random variable S^sigma modeling the maximal space needed by the processor to store the currently active tasks when acting under the scheduler sigma. We obtain tail bounds for the distribution of S^sigma for both offline and online schedulers, and investigate the expected value of S^sigma.

Related

• Probabilistic Models for the Execution Time in Stochastic Scheduling
• Sequencing Stochastic Jobs with a Single Sample
• New Old Algorithms for Stochastic Scheduling
• Optimal Factory Scheduling using Stochastic Dominance A*
• Models and Algorithms for Stochastic Online Scheduling