A fully polynomial approximation scheme for a scheduling problem with intree-type precedence delays

A fully polynomial approximation scheme for a scheduling problem with intree-type precedence delays

0.00 Avg rating0 Votes
Article ID: iaor20011324
Country: Netherlands
Volume: 23
Issue: 1/2
Start Page Number: 9
End Page Number: 11
Publication Date: Aug 1998
Journal: Operations Research Letters
Authors:
Keywords: networks, computational analysis
Abstract:

We investigate a single-machine scheduling problem with precedence delays that have a simple structure: the corresponding tree has k leaves and only k + 2 nodes. The objective is to minimize the makespan. We present a pseudo-polynomial algorithm for this problem, and we also give a fully polynomial approximation scheme.

Reviews

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