Performance of the LPT algorithm in multiprocessor scheduling

DOI10.1016/0305-0548(90)90015-YzbMATH Open0692.68033OpenAlexW2034939669MaRDI QIDQ583889FDOQ583889

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Bounds on Multiprocessing Timing Anomalies
• An Application of Bin-Packing to Multiprocessor Scheduling
• Fast algorithms for bin packing
• Title not available (Why is that?)
• Multiprocessor scheduling: Combining LPT and MULTIFIT
• Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors
• Tighter Bounds for the Multifit Processor Scheduling Algorithm
• A Review of Production Scheduling
• On the Expected Relative Performance of List Scheduling
• A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors
• Evaluation of a MULTIFIT-based scheduling algorithm
• Tight Bounds and Probabilistic Analysis of Two Heuristics for Parallel Processor Scheduling
• 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
• Performance Guarantees for Scheduling Algorithms
• Bounds for nonpreemptive scheduling of jobs with similar processing times on multiprocessor systems using the LPT-algorithm

Cited In (18)

• The Asymptotic Optimality of the LPT Rule
• Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions
• A note on LPT scheduling
• The longest processing time rule for identical parallel machines revisited
• Comparing the minimum completion times of two longest-first scheduling-heuristics
• Title not available (Why is that?)
• 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
• Update on the asymptotic optimality of LPT
• An LPT-bound for a parallel multiprocessor scheduling problem
• 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)