Performance of the LPT algorithm in multiprocessor scheduling
DOI10.1016/0305-0548(90)90015-YzbMath0692.68033OpenAlexW2034939669MaRDI QIDQ583889
Tien Y. Kao, Elsayed A. Elsayed
Publication date: 1990
Published in: Computers \& Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0305-0548(90)90015-y
heuristicsmultiprocessor schedulingprobabilistic analysisNP-completeworst-case analysisstochastic modelLPT algorithmdeterministic modelsmakespans
Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bounds for nonpreemptive scheduling of jobs with similar processing times on multiprocessor systems using the LPT-algorithm
- Multiprocessor scheduling: Combining LPT and MULTIFIT
- Fast algorithms for bin packing
- A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors
- Tighter Bounds for the Multifit Processor Scheduling Algorithm
- Tight Bounds and Probabilistic Analysis of Two Heuristics for Parallel Processor Scheduling
- On the Expected Relative Performance of List Scheduling
- Evaluation of a MULTIFIT-based scheduling algorithm
- Probabilistic Bounds on the Performance of List Scheduling
- A probabilistic analysis of multiprocessor list scheduling: the erlang case
- Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics
- Worst-Case Analysis of Heuristic Algorithms
- A Review of Production Scheduling
- Performance Guarantees for Scheduling Algorithms
- An Application of Bin-Packing to Multiprocessor Scheduling
- Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Bounds on Multiprocessing Timing Anomalies
This page was built for publication: Performance of the LPT algorithm in multiprocessor scheduling
