__Search Results__

*S. Aalto, A. Penttinen, P. Lassila and P. Osti*, **On the optimal trade-off between SRPT and opportunistic scheduling**, in Proceedings of ACM SIGMETRICS, 2011, San Jose, California, USA (bib)**Abstract:** We consider service systems where new jobs not only increase the load but also improve the service ability of such a system, cf. opportunistic scheduling gain in wireless systems. We study the optimal trade-off between the SRPT (Shortest Remaining Processing Time) discipline and opportunistic scheduling in the systems characterized by compact and symmetric capacity regions. The objective is to minimize the mean delay in a transient setting where all jobs are available at time 0 and no new jobs arrive thereafter. Our main result gives conditions under which the optimal rate vector does not depend on the sizes of the jobs as long as their order (in size) remains the same. In addition, it shows that in this case the optimal policy applies the SRPT principle serving the shortest job with the highest rate of the optimal rate vector, the second shortest with the second highest rate etc. We also give a recursive algorithm to determine both the optimal rate vector and the minimum mean delay. In some special cases, the rate vector, as well as the minimum mean delay, have even explicit expressions as demonstrated in the paper. For the general case, we derive both an upper bound and a lower bound of the minimum mean delay.