Probabilistic Bounds on the Performance of List Scheduling

DOI10.1137/0215028MaRDI QIDQ3727378zbMATH OpenOpenAlexFDO

Authors Peter Downey, John Bruno

Publication date 1986

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

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

zbMATH Keywords

approximation algorithmKolmogorov-Smirnov statisticsmakespan schedulingparallel machinesprobabilistic analysis of list scheduling heuristics

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the Expected Relative Performance of List Scheduling
• A probabilistic analysis of multiprocessor list scheduling: the erlang case
• scientific article; zbMATH DE number 947476
• On the Asymptotic Optimality of Multiprocessor Scheduling Heuristics for the Makespan Minimization Problem
• Tight Bounds and Probabilistic Analysis of Two Heuristics for Parallel Processor Scheduling

Cited in

(18)

• Some recent results in the analysis of greedy algorithms for assignment problems
• Sensitivity analysis of list scheduling heuristics
• Case study on statistically estimating minimum makespan for flow line scheduling problems.
• List scheduling revisited
• Estimating the probability of meeting a deadline in schedules and plans
• Performance evaluation of schedulers in a probabilistic setting
• A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors
• Tight Bounds and Probabilistic Analysis of Two Heuristics for Parallel Processor Scheduling
• Decentralized list scheduling
• On the Expected Relative Performance of List Scheduling
• A probabilistic analysis of multiprocessor list scheduling: the erlang case
• Minimizing expected makespans on uniform processor systems
• scientific article; zbMATH DE number 1462947 (Why is no real title available?)
• On the Asymptotic Optimality of Multiprocessor Scheduling Heuristics for the Makespan Minimization Problem
• Performance of the LPT algorithm in multiprocessor scheduling
• Distribution-free bounds on the expectation of the maximum with scheduling applications
• Probabilistic single processor scheduling
• Scheduling independent jobs with stochastic processing times and a common due date on parallel and identical machines

This page was built for publication: Probabilistic Bounds on the Performance of List Scheduling

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