### Abstract

We consider the problem of scheduling jobs on a single machine with preemption, when the server is allowed to reject jobs at some penalty. We consider minimizing two objectives: total flow time and total job-idle time (the idle time of a job is the flow time minus the processing time). We give 2-competitive online algorithms for the two objectives and extend some of our results to the case of weighted flow time and machines with varying speeds. We also give a resource augmentation result for the case of arbitrary penalties achieving a competitive ratio of O(1/epsilon(log W + log C)(2)) using a (1+epsilon) speed processor. Finally, we present a number of lower bounds for both the case of uniform and arbitrary penalties.

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

Title of host publication | Algorithms - ESA 2003 (11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003. Proceedings) |

Editors | G. Di Battista, U. Zwick |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 43-54 |

ISBN (Print) | 3-540-20064-9 |

DOIs | |

Publication status | Published - 2003 |

### Publication series

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

Volume | 2832 |

ISSN (Print) | 0302-9743 |

## Fingerprint Dive into the research topics of 'Scheduling for flow-time with admission control'. Together they form a unique fingerprint.

## Cite this

Bansal, N., Blum, A., Chawla, S., & Dhamdhere, K. (2003). Scheduling for flow-time with admission control. In G. Di Battista, & U. Zwick (Eds.),

*Algorithms - ESA 2003 (11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003. Proceedings)*(pp. 43-54). (Lecture Notes in Computer Science; Vol. 2832). Springer. https://doi.org/10.1007/978-3-540-39658-1_7