Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-23T17:25:14.304Z Has data issue: false hasContentIssue false
  • English
  • Français

OPTIMAL SWITCHING ON AND OFF THE ENTIRE SERVICE CAPACITY OF A PARALLEL QUEUE

Published online by Cambridge University Press:  09 October 2015

Eugene A. Feinberg  and
Xiaoxuan Zhang
Eugene A. Feinberg
Affiliation:
Department of Applied Mathematics and Statistics, Stony Brook University, Stony Brook, NY 11794, USA E-mail: [email protected]
Xiaoxuan Zhang
Affiliation:
IBM T.J. Watson Research Center, Yorktown Heights, NY 10598, USA E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper studies optimal switching on and off of the entire service capacity of an M/M/∞ queue with holding, running and switching costs. The running costs depend only on whether the system is on or off, and the holding costs are linear. The goal is to minimize average costs per unit time. The main result is that an average-cost optimal policy either always runs the system or is an (M, N)-policy defined by two thresholds M and N, such that the system is switched on upon an arrival epoch when the system size accumulates to N and is switched off upon a departure epoch when the system size decreases to M. It is shown that this optimization problem can be reduced to a problem with a finite number of states and actions, and an average-cost optimal policy can be computed via linear programming. An example, in which the optimal (M, N)-policy outperforms the best (0, N)-policy, is provided. Thus, unlike the case of single-server queues studied in the literature, (0, N)-policies may not be average-cost optimal.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 29 , Issue 4 , October 2015 , pp. 483 - 506
Copyright
Copyright © Cambridge University Press 2015 

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. Altman, E. and Nain, P. (1993). Optimal control of the M/G/1 queue with repeated vacations of the server. IEEE Transactions on Automatic Control 38(12): 1766–1775.Google Scholar
2. Bell, C.E. (1975). Turning off a server with customers present: is this any way to run an M/M/c queue with removable servers? Operations Research 23(3): 571–574.Google Scholar
3. Bell, C.E. (1980). Optimal operation of an M/M/2 queue with removable servers. Operations Research 28(5): 1189–1204.Google Scholar
4. Browne, S. and Kella, O. (1995). Parallel service with vacations. Operations Research 43(5): 870–878.Google Scholar
5. Chao, X. and Zhao, Y.Q. (1998). Analysis of multi-server queues with station and server vacations. European Journal of Operational Research 110(2): 392–406.Google Scholar
6. Denardo, E. (1970). On linear programming in a Markov decision problem. Management Science 16(5): 281–288.Google Scholar
7. Denardo, E., Feinberg, E., and Kella, O. (1997). Stochastic monotonicity for stationary recurrence times of first passage heights}. The Annals of Applied Probability 7(2): 326–339.Google Scholar
8. Federgruen, A. and So, K. (1991). Optimality of threshold policies in single-server queueing systems with server vacations. Advances in Applied Probability 23(2): 388–405.Google Scholar
9. Feinberg, E. (1994). A generalization of ‘expectation equals reciprocal of intensity’ to nonstationary distributions. Journal of Applied Probability 31(1): 262–267.Google Scholar
10. Feinberg, E. (2012). Reduction of discounted continuous-time MDPs with unbounded jump and reward rates to discrete-time total-reward MDPs. In Optimization, Control, and Applications of Stochastic Systems, Hernaández-Hernaández, D. and Minjárez-Sosa, J.A. (Eds.) New York: Birkhäuser/Springer, pp. 77–97.Google Scholar
11. Feinberg, E. and Kella, O. (2002). Optimality of D-policies for an M/G/1 queue with a removable server. Queueing Systems 42(4): 355–376.Google Scholar
12. Fuhrmann, S. and Cooper, R.B. (1985). Stochastic decompositions in the M/G/1 queue with generalized vacations. Operations Research 33(5): 1117–1129.Google Scholar
13. Greenberg, A., Hamilton, J., Maltz, D., and Patel, P. (2008). The cost of a cloud: research problems in data center networks. ACM SIGCOMM Computer Communication Review 39(1): 68–73.Google Scholar
14. Guo, X. and Hernández-Lerma, O. (2005). Continuous-time Markov Decision Processes. Berlin: Springer-Verlag.Google Scholar
15. Guo, X., Hernández-Lerma, O., and Prieto-Rumeau, T. (2006). A survey of recent results on continuous-time Markov decision processes. Top 14(2): 177–246.Google Scholar
16. Heyman, D. (1968). Optimal operating policies for M/G/1 queuing systems. Operations Research 16(2): 362–382.Google Scholar
17. Hofri, M. (1986). Queueing systems with a procrastinating server. ACM SIGMETRICS Performance Evaluation Review 14(1): 245–253.Google Scholar
18. Huang, C., Brumelle, S., Sawaki, K., and Vertinsky, I. (1977). Optimal control for multi-servers queueing systems under periodic review. Naval Research Logistics Quarterly 24(1): 127–135.Google Scholar
19. Igaki, N. (1992). Exponential two server queue with n-policy and general vacations. Queueing Systems 10(4): 279–294.Google Scholar
20. Kao, E.P. and Narayanan, K.S. (1991). Analyses of an M/M/N queue with server's vacations. European Journal of Operational Research 54(2): 256–266.Google Scholar
21. Kella, O. (1989). The threshold policy in the M/G/1 queue with server vacations. Naval Research Logistics 36(1): 111–123.Google Scholar
22. Kella, O. and Whitt, W. (1991). Queues with server vacations and lévy processes with secondary jump input. The Annals of Applied Probability 1(1): 104–117.Google Scholar
23. Khazaei, H., Misic, J., and Misic, V. (2012). Performance analysis of cloud computing centers using M/G/m/m+ r queuing systems. IEEE Transactions on Parallel and Distributed Systems 23(5): 936–943.Google Scholar
24. Kitaev, M. and Rykov, V. (1995). Controlled queueing systems. Boca Raton: CRC Press.Google Scholar
25. Korevaar, J. (2004). Tauberian Theory: a Century of Developments. New York: Springer.Google Scholar
26. Kulkarni, V., Kumar, S., Mookerjee, V., and Sethi, S. (2009). Optimal allocation of effort to software maintenance: A queuing theory approach. Production and Operations Management 18(5): 506–515.Google Scholar
27. Lee, H. and Srinivasan, M. (1989). Control policies for the M X /G/1 queueing system. Management Science 35(6): 708–721.Google Scholar
28. Levy, Y. and Yechiali, U. (1976). An M/M/s queue with servers' vacations. Information Systems and Operational Research 14(2): 153–163.Google Scholar
29. Li, W. and Alfa, A.S. (2000). Optimal policies for M/M/m queue with two different kinds of (n, t)-policies. Naval Research Logistics 47(3): 240–258.Google Scholar
30. Mazzucco, M., Dyachuk, D., and Deters, R. (2010). Maximizing cloud providers' revenues via energy aware allocation policies. 2010 IEEE 3rd International Conference on Cloud Computing, pp. 131–138.Google Scholar
31. Mine, H. and Osaki, S. (1970). Markovian Decision Processes. vol. 25. New York: Elsevier Publishing Company.Google Scholar
32. Piunovskiy, A. and Zhang, Y. (2012). The transformation method for continuous-time Markov decision processes. Journal of Optimization Theory and Applications 154(2): 691–712.Google Scholar
33. Puterman, M. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. New York: John Wiley and Sons, Inc.Google Scholar
34. Rhee, H.-K. and Sivazlian, B. (1990). Distribution of the busy period in a controllable M/M/2 queue operating under the triadic (0, k, n, m) policy. Journal of Applied Probability 27(2): 425–432.Google Scholar
35. Ross, S. (1996). Stochastic Processes. New York: John Wiley and Sons, Inc.Google Scholar
36. Shanthikumar, J. (1988). On stochastic decomposition in M/G/1 type queues with generalized server vacations. Operations Research 36(4): 566–569.Google Scholar
37. Sobel, M. (1969). Optimal average-cost policy for a queue with start-up and shut-down costs. Operations Research 17(1): 145–162.Google Scholar
38. Yadin, M. and Naor, P. (1963). Queueing systems with a removable service station. Operations Research 14(4): 393–405.Google Scholar