A New Approximation Algorithm for the Nonpreemptive Scheduling of Independent Jobs on Identical Parallel Processors

DOI10.1137/050634657zbMath1138.68015OpenAlexW2054837336MaRDI QIDQ3503217

Paolamaria Pietramala, Giuseppe Paletta

Publication date: 22 May 2008

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/050634657

zbMATH Keywords

optimizationschedulingapproximation algorithmworst-case performance ratio

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Related Items (5)

Partial solutions and multifit algorithm for multiprocessor scheduling ⋮ A note on posterior tight worst-case bounds for longest processing time schedules ⋮ Minimizing the makespan in nonpreemptive parallel machine scheduling problem ⋮ A new heuristic for workload balancing on identical parallel machines and a statistical perspective on the workload balancing criteria ⋮ A composite algorithm for multiprocessor scheduling

This page was built for publication: A New Approximation Algorithm for the Nonpreemptive Scheduling of Independent Jobs on Identical Parallel Processors