Leo Liberti, James Ostrowski
Journal of Global Optimization
We study on-line scheduling in overloaded systems. Requests for jobs arrive one by one as time proceeds; the serving agents have limited capacity and not all requests can be served. Still, we want to serve the "best" set of requests according to some criterion. In this situation, the ability to preempt (i.e., abort) jobs in service in order to make room for better jobs that would otherwise be rejected has proven to be of great help in some scenarios. We show that, surprisingly, in many other scenarios this is not the case. In a simple, generic model, we prove a polylogarithmic lower bound on the competitiveness of randomized and preemptive on-line scheduling algorithms. Our bound applies to several recently studied problems. In fact, in certain scenarios our bound is quite close to the competitiveness achieved by known deterministic, nonpreemptive algorithms. © 1998 Society for Industrial and Applied Mathematics.
Leo Liberti, James Ostrowski
Journal of Global Optimization
Michael Ray, Yves C. Martin
Proceedings of SPIE - The International Society for Optical Engineering
N.K. Ratha, A.K. Jain, et al.
Workshop CAMP 2000
Israel Cidon, Leonidas Georgiadis, et al.
IEEE/ACM Transactions on Networking