Performance of the LPT algorithm in multiprocessor scheduling

DOI10.1016/0305-0548(90)90015-YMaRDI QIDQ583889zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

heuristicsNP-completeLPT algorithmworst-case analysisprobabilistic analysisstochastic modelmultiprocessor schedulingdeterministic modelsmakespans

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• A note on LPT scheduling
• Parametric bounds for LPT scheduling on uniform processors
• A note on LPT scheduling
• The rate of convergence to optimality of the LPT rule
• The Asymptotic Optimality of the LPT Rule

Cites work

• scientific article; zbMATH DE number 3890754 (Why is no real title available?)
• scientific article; zbMATH DE number 3757695 (Why is no real title available?)
• scientific article; zbMATH DE number 3550182 (Why is no real title available?)
• scientific article; zbMATH DE number 3354425 (Why is no real title available?)
• A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors
• A Review of Production Scheduling
• A probabilistic analysis of multiprocessor list scheduling: the erlang case
• An Application of Bin-Packing to Multiprocessor Scheduling
• Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics
• Bounds for nonpreemptive scheduling of jobs with similar processing times on multiprocessor systems using the LPT-algorithm
• Bounds on Multiprocessing Timing Anomalies
• Evaluation of a MULTIFIT-based scheduling algorithm
• Fast algorithms for bin packing
• Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors
• Multiprocessor scheduling: Combining LPT and MULTIFIT
• On the Expected Relative Performance of List Scheduling
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Performance Guarantees for Scheduling Algorithms
• Probabilistic Bounds on the Performance of List Scheduling
• Tight Bounds and Probabilistic Analysis of Two Heuristics for Parallel Processor Scheduling
• Tighter Bounds for the Multifit Processor Scheduling Algorithm
• Worst-Case Analysis of Heuristic Algorithms

Cited in

(18)

• Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions
• The Asymptotic Optimality of the LPT Rule
• A note on LPT scheduling
• Comparing the minimum completion times of two longest-first scheduling-heuristics
• The longest processing time rule for identical parallel machines revisited
• scientific article; zbMATH DE number 5964914 (Why is no real title available?)
• Generalized worst-case bounds for an homogeneous multiprocessor model with independent memories—Completion time performance criterion
• A note on LPT scheduling
• The general algorithm \(\text{LPT}(k)\) for scheduling identical parallel machines
• The exact LPT-bound for maximizing the minimum completion time
• The rate of convergence to optimality of the LPT rule
• Algorithms for handling skew in parallel task scheduling
• An LPT-bound for a parallel multiprocessor scheduling problem
• Update on the asymptotic optimality of LPT
• 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
• Performance of critical path type algorithms for scheduling on parallel processors
• Tight approximation bounds for the LPT rule applied to identical parallel machines with small jobs

This page was built for publication: Performance of the LPT algorithm in multiprocessor scheduling

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