Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-27T08:09:54.605Z Has data issue: false hasContentIssue false
  • English
  • Français

SCHEDULING IN A SINGLE-SERVER QUEUE WITH STATE-DEPENDENT SERVICE RATES

Published online by Cambridge University Press:  21 May 2019

Urtzi Ayesta ,
Balakrishna Prabhu  and
Rhonda Righter
Urtzi Ayesta
Affiliation:
CNRS, IRIT, 2 rue C. Camichel, 31071Toulouse, FranceLAAS-CNRS, Université de Toulouse, CNRS, INP, Toulouse, FranceIKERBASQUE - Basque Foundation for Science, 48011Bilbao, SpainUPV/EHU, Univ. of the Basque Country, 20018, Donostia, Spain E-mail: [email protected]
Balakrishna Prabhu
Affiliation:
LAAS-CNRS, Université de Toulouse, CNRS, INP, Toulouse, France
Rhonda Righter
Affiliation:
University of California, Berkeley, CA94720, United States
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider single-server scheduling to minimize holding costs where the capacity, or rate of service, depends on the number of jobs in the system, and job sizes become known upon arrival. In general, this is a hard problem, and counter-intuitive behavior can occur. For example, even with linear holding costs the optimal policy may be something other than SRPT or LRPT, it may idle, and it may depend on the arrival rate. We first establish an equivalence between our problem of deciding which jobs to serve when completed jobs immediately leave, and a problem in which we have the option to hold on to completed jobs and can choose when to release them, and in which we always serve jobs according to SRPT. We thus reduce the problem to determining the release times of completed jobs. For the clearing, or transient system, where all jobs are present at time 0, we give a complete characterization of the optimal policy and show that it is fully determined by the cost-to-capacity ratio. With arrivals, the problem is much more complicated, and we can obtain only partial results.

Keywords

operations researchqueueing theory
Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 34 , Issue 4 , October 2020 , pp. 507 - 521
Copyright
Copyright © Cambridge University Press 2019

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Aalto, S. & Ayesta, U. (2009). SRPT applied to bandwidth-sharing networks. Annals of Operations Research 170: 3–19.CrossRefGoogle Scholar
2.Bansal, N., Kimbrel, T., & Pruhs, K. (2004). Dynamic speed scaling to manage energy and temperature. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 520–529.CrossRefGoogle Scholar
3.Bansal, N., Kimbrel, T., & Pruhs, K. (2007). Speed scaling to manage energy and temperature. Journal of the ACM 54: 1–39.CrossRefGoogle Scholar
4.Bekker, R., Borst, S.C., Boxma, O.J., & Kella, O. (2004). Queues with workload-dependent arrival and service rates. Queueing Systems 46: 537–556.CrossRefGoogle Scholar
5.Berg, B., Dorsman, J.-P., & Harchol-Balter, M. (2018). Towards Optimality in Parallel Job Scheduling. In Proceedings of ACM SIGMETRICS 2018, Los Angeles, CA, June 2018.CrossRefGoogle Scholar
6.Buyukkoc, C., Varaya, P., & Walrand, J. (1985). The cμ rule revisited. Advances in Applied Probability 17: 237–238.CrossRefGoogle Scholar
7.Elahi, M. & Williamson, C. (2018). On saturation effects in coupled speed scaling. In Quantitative Evaluation of Systems (McIver, A. & Horvath, A. Eds. ), Cham, Switzerland: Springer International Publishing, pp. 407–422.CrossRefGoogle Scholar
8.Gupta, V. & Harchol-Balter, M. (2009). Self-adaptive Admission Control Policies for Resource-sharing Systems. In Proceedings of ACM SIGMETRICS, pp. 311–322.CrossRefGoogle Scholar
9.Marin, A., Mitrani, I., Elahi, M., & Williamson, C. (2018). Control and optimization of the SRPT service policy by frequency scaling. In Quantitative Evaluation of Systems (McIver, A. & Horvath, A., Eds.), Cham, Switzerland: Springer International Publishing, pp. 257–272.CrossRefGoogle Scholar
10.Righter, R. (1994). Scheduling. In Chapter in Stochastic Orders (Shaked, J.G. & Shanthikumar, M. Eds.), New York: Academic Press, pp. 381–432.Google Scholar
11.Righter, R. & Shanthikumar, J.G. (1989). Scheduling multiclass single server queueing systems to Stochastically maximize the number of successful departures. Probability in the Engineering and the Informational Sciences 3: 323–333.CrossRefGoogle Scholar
12.Righter, R. & Shanthikumar, J.G. (1992). Extremal properties of the FIFO discipline in queueing networks. Journal of Applied Probability 29: 967–978.CrossRefGoogle Scholar
13.Sadiq, B. & de Veciana, G. (2010). Balancing SRPT prioritization vs. opportunistic gain in wireless systems with flow dynamics, ITC 22.Google Scholar
14.Schrage, L. (1968). Letter to the Editor – A proof of the optimality of the shortest remaining processing time discipline. Operations Research 16(3): 687–690.CrossRefGoogle Scholar
15.Shaked, M. & Shanthikumar, J.G. (2007). Stochastic orders. New York: Springer.CrossRefGoogle Scholar
16.Timmermans, V. & Vredeveld, T. (2015). Scheduling with state-dependent machine speed, WAOA Workshop?. In Approximation and Online Algorithms (Sanità, L. & Skutella, M. Eds.), Cham, Switzerland: Springer, pp. 196–208.CrossRefGoogle Scholar
17.Weiss, G. (1995). A tutorial in stochastic scheduling. In Scheduling Theory and Its Applications (Lenstra, P., Chretienne, E.G., Coffman, Z. & Liu, J.K., Eds.), Wiley.Google Scholar
18.Wierman, A., Andrew, L.L.H., & Tang, A. (2009). Power-aware speed scaling in processor sharing systems. In IEEE INFOCOM, 2007–2015.CrossRefGoogle Scholar