Probabilistic Bounds on the Performance of List Scheduling

DOI10.1137/0215028zbMath0595.68037OpenAlexW2018351242MaRDI QIDQ3727378

Peter J. Downey, John L. 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

parallel machinesapproximation algorithmKolmogorov-Smirnov statisticsmakespan schedulingprobabilistic analysis of list scheduling heuristics

Mathematics Subject Classification ID

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

Related Items

Unnamed Item, Scheduling independent jobs with stochastic processing times and a common due date on parallel and identical machines, Performance of the LPT algorithm in multiprocessor scheduling, Distribution-free bounds on the expectation of the maximum with scheduling applications, Some recent results in the analysis of greedy algorithms for assignment problems