@inproceedings{f8ae223db34e465bb7aa0649c0435dd7,

title = "Scheduling for flow-time with admission control",

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.",

author = "N. Bansal and A. Blum and S. Chawla and K. Dhamdhere",

year = "2003",

doi = "10.1007/978-3-540-39658-1_7",

language = "English",

isbn = "3-540-20064-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "43--54",

editor = "{Di Battista}, G. and U. Zwick",

booktitle = "Algorithms - ESA 2003 (11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003. Proceedings)",

address = "Germany",

}