On the Expected Relative Performance of List Scheduling

DOI10.1287/OPRE.33.3.548MaRDI QIDQ3686419zbMATH OpenOpenAlexFDO

Authors E. N. Gilbert, E. G. jun. Coffman

Publication date 1985

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/opre.33.3.548

zbMATH Keywords

expected relative performancelist schedulemakespan

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Recommendations

• A probabilistic analysis of multiprocessor list scheduling: the erlang case
• Probabilistic Bounds on the Performance of List Scheduling
• A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors
• Stochastic limit laws for schedule makespans
• On the Asymptotic Optimality of Multiprocessor Scheduling Heuristics for the Makespan Minimization Problem

Cited in

(22)

• The ratio of the extreme to the sum in a random sequence
• Analysis of the list scheduling algorithm for precedence constrained parallel tasks
• A new on-line scheduling heuristic
• List scheduling revisited
• The equivalence of two classical list scheduling algorithms for dependent typed tasks with release dates, due dates and precedence delays
• An average-case analysis of online non-clairvoyant scheduling of independent parallel tasks
• Performance guarantees for flowshop heuristics to minimize makespan
• Scheduling independent tasks to minimize the makespan on identical machines
• A tighter analysis of work stealing
• A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors
• scientific article; zbMATH DE number 5762701 (Why is no real title available?)
• Decentralized list scheduling
• Probabilistic Bounds on the Performance of List Scheduling
• A probabilistic analysis of multiprocessor list scheduling: the erlang case
• Minimizing expected makespans on uniform processor systems
• The expected asymptotical ratio for preemptive stochastic online problem
• Stochastic convexity of sums of i.i.d. non-negative random variables with applications
• scientific article; zbMATH DE number 1462947 (Why is no real title available?)
• Performance of the LPT algorithm in multiprocessor scheduling
• Distribution-free bounds on the expectation of the maximum with scheduling applications
• Scheduling independent jobs with stochastic processing times and a common due date on parallel and identical machines
• A state-of-the-art review of parallel-machine scheduling research

This page was built for publication: On the Expected Relative Performance of List Scheduling

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