Tight approximation bounds for the LPT rule applied to identical parallel machines with small jobs

DOI10.1007/s10951-022-00742-wzbMath1501.90028OpenAlexW4283640313WikidataQ114225423 ScholiaQ114225423MaRDI QIDQ2093193

Myungho Lee, Kangbok Lee, Michael L. Pinedo

Publication date: 4 November 2022

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-022-00742-w

zbMATH Keywords

makespan minimizationapproximation algorithmsidentical parallel machine schedulingLPT ruleprocessing time restriction

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Cites Work

• Multiprocessor scheduling: Combining LPT and MULTIFIT
• Approximation schemes for scheduling on parallel machines
• The longest processing time rule for identical parallel machines revisited
• A note on the Coffman-Sethi bound for LPT scheduling
• A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem
• The Design of Approximation Algorithms
• The Asymptotic Optimality of the LPT Rule
• An Application of Bin-Packing to Multiprocessor Scheduling
• `` Strong NP-Completeness Results
• Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• On the Minimization of the Makespan Subject to Flowtime Optimality
• An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables
• Bounds on Multiprocessing Timing Anomalies
• A note on LPT scheduling

This page was built for publication: Tight approximation bounds for the LPT rule applied to identical parallel machines with small jobs