A note on posterior tight worst-case bounds for longest processing time schedules

DOI10.1007/S10288-018-0381-7MaRDI QIDQ2423296zbMATH OpenOpenAlexFDO

Authors Johnny C. Ho, Giuseppe Paletta, Alex J. Ruiz-Torres, Ivar Massabò

Publication date 21 June 2019

Published in 4OR (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10288-018-0381-7

zbMATH Keywords

LPT algorithmmultiprocessor schedulingparallel machinesworst-case analysis

Mathematics Subject Classification ID

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

Recommendations

• A note on LPT scheduling
• New approximation bounds for LPT scheduling
• scientific article; zbMATH DE number 8821
• A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem
• A note on LPT scheduling

Cites work

• A New Approximation Algorithm for the Nonpreemptive Scheduling of Independent Jobs on Identical Parallel Processors
• A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem
• A note on LPT scheduling
• A note on the Coffman-Sethi bound for LPT scheduling
• A short note on an advance in estimating the worst-case performance ratio of the MPS algorithm
• A state-of-the-art review of parallel-machine scheduling research
• An Application of Bin-Packing to Multiprocessor Scheduling
• Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors
• scientific article; zbMATH DE number 8821 (Why is no real title available?)
• scientific article; zbMATH DE number 3521517 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1302193 (Why is no real title available?)
• scientific article; zbMATH DE number 1783886 (Why is no real title available?)
• Multiprocessor scheduling: Combining LPT and MULTIFIT
• Optimal Scheduling of Tasks on Identical Parallel Processors
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• The Asymptotic Optimality of the LPT Rule
• The rate of convergence to optimality of the LPT rule

Cited in

(2)

• A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem
• scientific article; zbMATH DE number 8821 (Why is no real title available?)

This page was built for publication: A note on posterior tight worst-case bounds for longest processing time schedules

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