An improved delayed-start LPT algorithm for a partition problem on two identical parallel machines

DOI10.1016/J.EJOR.2007.04.013MaRDI QIDQ2463519zbMATH OpenOpenAlexWikidataFDO

Authors C. Koulamas, George J. Kyparisis

Publication date 12 December 2007

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2007.04.013

zbMATH Keywords

approximation algorithmsLPTparallel machinesscheduling

Mathematics Subject Classification ID

Stochastic scheduling theory in operations research (90B36)

Recommendations

• A modified LPT algorithm for the two uniform parallel machine makespan minimization problem
• scientific article; zbMATH DE number 2162223
• scientific article; zbMATH DE number 1094170
• Bounds on delay start LPT algorithm for scheduling on two identical machines in the \(l_p\) norm
• Parallel machines scheduling with nonsimultaneous machine available time

Cites work

• Bounds on Multiprocessing Timing Anomalies
• scientific article; zbMATH DE number 1559404 (Why is no real title available?)
• scientific article; zbMATH DE number 6472625 (Why is no real title available?)
• Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data
• Tighter bounds on a heuristic for a partition problem
• Worst-Case Analysis of a Placement Algorithm Related to Storage Allocation

Cited in

(8)

• Bounds on delay start LPT algorithm for scheduling on two identical machines in the \(l_p\) norm
• A note on minimizing the sum of squares of machine completion times on two identical parallel machines
• A modified LPT algorithm for the two uniform parallel machine makespan minimization problem
• A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem
• The minimization scheduling problem of sum of squares of the machine completion times on two identical parallel machines
• A fast and effective subset sum based improvement procedure for workload balancing on identical parallel machines
• The LPT heuristic for minimizing total load on a proportionate openshop
• Online scheduling of malleable parallel jobs with setup times on two identical machines

This page was built for publication: An improved delayed-start LPT algorithm for a partition problem on two identical parallel machines

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