A comment on scheduling on uniform machines under chain-type precedence constraints

A comment on scheduling on uniform machines under chain-type precedence constraints

0.00 Avg rating0 Votes
Article ID: iaor20052155
Country: Netherlands
Volume: 26
Issue: 3
Start Page Number: 107
End Page Number: 109
Publication Date: Mar 2000
Journal: Operations Research Letters
Authors:
Keywords: heuristics
Abstract:

In a recent paper, Chekuri and Bender derive (among other results) a polynomial-time 6-approximation algorithm for makespan minimization on uniform parallel machines subject to chain-type precedence constraints. In this short note, we combine some straightforward observations and thereby derive an extremely simple 2-approximation algorithm for this problem.

Reviews

Required fields are marked *. Your email address will not be published.