## Abstract

This work presents approximation algorithms for scheduling the tasks of a parallel application that are subject to precedence constraints. The considered tasks are malleable which means that they may be executed on a varying number of processors in parallel. The considered objective criterion is the makespan, i.e., the largest task completion time.

We demonstrate a close relationship between this scheduling problem and one of its subproblems, the allotment problem. By exploiting this relationship, we design a polynomial time approximation algorithm with performance guarantee arbitrarily close to (3+√5)/2≈2.61803 for the special case of series parallel precedence constraints and for the special case of precedence constraints of bounded width. These special cases cover the important situation of tree structured precedence constraints. For the general case with arbitrary precedence constraints, we give a polynomial time approximation algorithm with performance guarantee 3+√5≈5.23606.

We demonstrate a close relationship between this scheduling problem and one of its subproblems, the allotment problem. By exploiting this relationship, we design a polynomial time approximation algorithm with performance guarantee arbitrarily close to (3+√5)/2≈2.61803 for the special case of series parallel precedence constraints and for the special case of precedence constraints of bounded width. These special cases cover the important situation of tree structured precedence constraints. For the general case with arbitrary precedence constraints, we give a polynomial time approximation algorithm with performance guarantee 3+√5≈5.23606.

Original language | English |
---|---|

Title of host publication | Algorithms — ESA 2001 |

Subtitle of host publication | 9th Annual European Symposium Århus, Denmark, August 28–31, 2001 Proceedings |

Editors | Friedhelm Meyer auf der Heide |

Publisher | Springer |

Pages | 146-157 |

ISBN (Electronic) | 978-3-540-44676-7 |

ISBN (Print) | 978-3-540-42493-2 |

DOIs | |

Publication status | Published - 2001 |

Event | 9th Annual European Symposium on Algorithms, ESA 2001 - Aarhus, Denmark Duration: 28 Aug 2001 → 31 Aug 2001 Conference number: 9 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 2161 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 9th Annual European Symposium on Algorithms, ESA 2001 |
---|---|

Abbreviated title | ESA |

Country/Territory | Denmark |

City | Aarhus |

Period | 28/08/01 → 31/08/01 |

## Keywords

- Approximation algorithm
- Time slot
- Allotment problem
- Critical path
- Precedence constraints