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

DOI10.1145/322234.322242MaRDI QIDQ3902467zbMATH OpenOpenAlexFDO

Authors Peter Downey, Greg N. Frederickson, John Bruno

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

(20)

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

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)