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

deterministic modelsheuristicsLPT algorithmmakespansmultiprocessor schedulingNP-completeprobabilistic analysisstochastic modelworst-case analysis

Mathematics Subject Classification ID

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

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

• A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors
• A probabilistic analysis of multiprocessor list scheduling: the erlang case
• A Review of Production Scheduling
• 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
• 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?)
• 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

(24)

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

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)