Sequencing Tasks with Exponential Service Times to Minimize the Expected Flow Time or Makespan

DOI10.1145/322234.322242zbMATH Open0454.68016OpenAlexW2085298577MaRDI QIDQ3902467FDOQ3902467

John Bruno, Greg N. Frederickson, Peter Downey

Publication date: 1981

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

stochastic schedulingmean completion timeidentical parallel processorsmaximum completion time

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cited In (21)

• Simple Strategies in Multi-Objective MDPs
• Scheduling Stochastic Jobs with a Two-Point Distribution on Two Parallel Machines
• Preemptive stochastic online scheduling on two uniform machines
• Robust scheduling of parallel machines with sequence-dependent set-up costs
• Analysis of Smith's rule in stochastic machine scheduling
• Scheduling tasks with exponential duration on unrelated parallel machines
• A uniformization-based algorithm for continuous-time stochastic games model checking
• Scheduling Two-Point Stochastic Jobs to Minimize the Makespan on Two Parallel Machines
• Analysis of computer job control under uncertainty
• Markov automata with multiple objectives
• Efficient computation of time-bounded reachability probabilities in uniform continuous-time Markov decision processes
• Approximation results in parallel machines stochastic scheduling
• PAC Statistical Model Checking of Mean Payoff in Discrete- and Continuous-Time MDP
• Optimal sequences in stochastic single machine shops
• Minimizing expected makespans of multi-priority classes of jobs on uniform processors
• Time complexity of single machine scheduling with stochastic precedence constraints
• A case for on-machine load balancing
• On index policies for stochastic minsum scheduling
• Cost vs. time in stochastic games and Markov automata
• A Tight 2-Approximation for Preemptive Stochastic Scheduling
• Greed Works—Online Algorithms for Unrelated Machine Stochastic Scheduling

This page was built for publication: Sequencing Tasks with Exponential Service Times to Minimize the Expected Flow Time or Makespan

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