Worst-case analysis of LPT scheduling on a small number of non-identical processors

DOI10.1016/j.ipl.2023.106424zbMath1529.68058arXiv2203.02724OpenAlexW4380894115MaRDI QIDQ6072208

Reiji Suda, Takuto Mitsunobu, Vorapong Suppakitpaisarn

Publication date: 12 October 2023

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2203.02724

zbMATH Keywords

approximation algorithmsscheduling algorithmLPT algorithm

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

• Tighter approximation bounds for LPT scheduling in two special cases
• Parametric bounds for LPT scheduling on uniform processors
• A tight approximation ratio of a list scheduling algorithm for a single-machine scheduling problem with a non-renewable resource
• New approximation bounds for LPT scheduling
• Performance Guarantees of Local Search for Multiprocessor Scheduling
• Scheduling Independent Tasks on Uniform Processors
• Approximation Algorithms for Scheduling Parallel Jobs: Breaking the Approximation Ratio of 2
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• Tighter Bounds for LPT Scheduling on Uniform Processors
• Algorithms for Scheduling Independent Tasks
• Bounds for LPT Schedules on Uniform Processors
• An Application of Bin-Packing to Multiprocessor Scheduling
• `` Strong NP-Completeness Results
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies

This page was built for publication: Worst-case analysis of LPT scheduling on a small number of non-identical processors