### Abstract

We study the problem of assigning n tasks to m identical parallel machines in the real-time scheduling setting, where each task recurrently releases jobs that must be completed by their deadlines. The goal is to find a partition of the task set over the machines such that each job that is released by a task can meet its deadline. Since this problem is co-NP-hard, the focus is on finding a-approximation algorithms in the resource augmentation setting, i.e., finding a feasible partition on machines running at speed a¿=¿1, if some feasible partition exists on unit-speed machines.
Recently, Chen and Chakraborty gave a polynomial-time approximation scheme if the ratio of the largest to the smallest relative deadline of the tasks, ¿, is bounded by a constant. However, their algorithm has a super-exponential dependence on ¿ and hence does not extend to larger values of ¿. Our main contribution is to design an approximation scheme with a substantially improved running-time dependence on ¿. In particular, our algorithm depends exponentially on log¿ and hence has quasi-polynomial running time even if ¿ is polynomially bounded. This improvement is based on exploiting various structural properties of approximate demand bound functions in different ways, which might be of independent interest.

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

Title of host publication | LATIN 2014: Theoretical Informatics (11th Latin American Symposium, Montevideo, Uruguay, March 31-April 4, 2014. Proceedings) |

Editors | A. Pardo, A. Viola |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 550-561 |

ISBN (Print) | 978-3-642-54422-4 |

DOIs | |

Publication status | Published - 2014 |

Event | 11th Latin American Theoretical INformatics Symposium (LATIN 2014) - Montevideo, Uruguay Duration: 31 Mar 2014 → 4 Apr 2014 Conference number: 11 |

### Publication series

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

Volume | 8392 |

ISSN (Print) | 0302-9743 |

### Conference

Conference | 11th Latin American Theoretical INformatics Symposium (LATIN 2014) |
---|---|

Abbreviated title | LATIN 2014 |

Country | Uruguay |

City | Montevideo |

Period | 31/03/14 → 4/04/14 |

## Fingerprint Dive into the research topics of 'Approximating real-time scheduling on identical machines'. Together they form a unique fingerprint.

## Cite this

Bansal, N., Rutten, C., Ster, van der, S., Vredeveld, T., & Zwaan, van der, G. R. J. (2014). Approximating real-time scheduling on identical machines. In A. Pardo, & A. Viola (Eds.),

*LATIN 2014: Theoretical Informatics (11th Latin American Symposium, Montevideo, Uruguay, March 31-April 4, 2014. Proceedings)*(pp. 550-561). (Lecture Notes in Computer Science; Vol. 8392). Springer. https://doi.org/10.1007/978-3-642-54423-1_48