The exact LPT-bound for maximizing the minimum completion time

DOI10.1016/0167-6377(92)90004-MzbMath0767.90034OpenAlexW2048624116MaRDI QIDQ1196214

Hans Kellerer, Gerhard J. Woeginger, János A. Csirik

Publication date: 17 December 1992

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(92)90004-m

zbMATH Keywords

suboptimal algorithmsidentical processorsworst case ratio

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (36)

\(\kappa\)-partitioning problems for maximizing the minimum load ⋮ Comparing the minimum completion times of two longest-first scheduling-heuristics ⋮ SEMI-ONLINE MACHINE COVERING ⋮ Optimal preemptive online algorithms for scheduling with known largest size on two uniform machines ⋮ A polynomial-time approximation scheme for maximizing the minimum machine completion time ⋮ SEMI-ON-LINE SCHEDULING PROBLEM FOR MAXIMIZING THE MINIMUM MACHINE COMPLETION TIME ON THREE SPECIAL UNIFORM MACHINES ⋮ Semi on-line scheduling problem for maximizing the minimum machine completion time on two uniform machines ⋮ Improved approaches to the exact solution of the machine covering problem ⋮ Optimal semi-online algorithms for machine covering ⋮ Ordinal Maximin Share Approximation for Goods ⋮ Reducing price of anarchy of selfish task allocation with more selfishness ⋮ Mixed coordination mechanisms for scheduling games on hierarchical machines ⋮ Polynomial-time combinatorial algorithm for general max-min fair allocation ⋮ General max-min fair allocation ⋮ A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation ⋮ Parallel machine covering with limited number of preemptions ⋮ On-line machine covering on two machines with local migration ⋮ Lower bounds and modified LPT algorithm for \(k\)-partitioning problems with partition matroid constraint ⋮ Symmetry exploitation for online machine covering with bounded migration ⋮ Semi-on-line scheduling problems for maximizing the minimum machine completion time ⋮ Tight bounds for bandwidth allocation on two links ⋮ Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data ⋮ Optimal semi-online preemptive algorithms for machine covering on two uniform machines ⋮ Approximation schemes for scheduling and covering on unrelated machines ⋮ MapReduce machine covering problem on a small number of machines ⋮ Parallel machine scheduling problems with proportionally deteriorating jobs ⋮ Maximizing the Minimum Load for Selfish Agents ⋮ \(k\)-partitioning problems with partition matroid constraint ⋮ Parallel machine scheduling to maximize the minimum load with nonsimultaneous machine available times ⋮ Maximizing the minimum completion time on parallel machines ⋮ The optimal on-line parallel machine scheduling ⋮ Semi-online machine covering for two uniform machines ⋮ Maximizing the minimum load for selfish agents ⋮ Simultaneous approximation ratios for parallel machine scheduling problems ⋮ Preemptive machine covering on parallel machines ⋮ A new approach for bicriteria partitioning problem

Cites Work

• A performance guarantee for the greedy set-partitioning algorithm
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• Analysis of Greedy Solutions for a Replacement Part Sequencing Problem

This page was built for publication: The exact LPT-bound for maximizing the minimum completion time