A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem

DOI10.1007/S10951-015-0453-XMaRDI QIDQ282256zbMATH OpenOpenAlexFDO

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

Publication date 12 May 2016

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

Full work available at URL https://doi.org/10.1007/s10951-015-0453-x

zbMATH Keywords

heuristicschedulingLPT scheduletwo uniform parallel machines

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• A modified LPT algorithm for the two uniform parallel machine makespan minimization problem
• A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines
• A heuristic for maximizing the number of on-time jobs on two uniform parallel machines
• A note on posterior tight worst-case bounds for longest processing time schedules
• An LPT-bound for a parallel multiprocessor scheduling problem

Cites work

• 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?)
• A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines
• A modified LPT algorithm for the two uniform parallel machine makespan minimization problem
• A note on LPT scheduling
• A note on MULTIFIT scheduling for uniform machines
• A note on the Coffman-Sethi bound for LPT scheduling
• An Application of Bin-Packing to Multiprocessor Scheduling
• Bounds for Certain Multiprocessing Anomalies
• Bounds for LPT Schedules on Uniform Processors
• Bounds for Multifit Scheduling on Uniform Processors
• Bounds on Multiprocessing Timing Anomalies
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Parametric bounds for LPT scheduling on uniform processors
• Scheduling Independent Tasks on Uniform Processors
• Tighter Bounds for LPT Scheduling on Uniform Processors
• Tighter bound for MULTIFIT scheduling on uniform processors

Cited in

(6)

• An approximation algorithm for multi-agent scheduling on two uniform parallel machines
• A modified LPT algorithm for the two uniform parallel machine makespan minimization problem
• A heuristic for maximizing the number of on-time jobs on two uniform parallel machines
• The LPT heuristic for minimizing total load on a proportionate openshop
• Makespan minimization on uniform parallel machines with release times
• A note on posterior tight worst-case bounds for longest processing time schedules

This page was built for publication: A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem

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