| 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: | Schuurman P. |
| Keywords: | networks, computational analysis |
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.