Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-08T08:38:47.520Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimality of threshold policies in single-server queueing systems with server vacations

Published online by Cambridge University Press:  01 July 2016

Awi Federgruen  and
Kut C. So
Awi Federgruen*
Affiliation:
Columbia University
Kut C. So*
Affiliation:
University of California, Irvine
*
∗Postal address: Graduate School of Business, Columbia University, New York, NY 10027, USA.
∗∗Postal address: Graduate School of Management, University of California, Irvine, CA 92717, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we consider a class of single-server queueing systems with compound Poisson arrivals, in which, at service completion epochs, the server has the option of taking off for one or several vacations of random length. The cost structure consists of a holding cost rate specified by a general non-decreasing function of the queue size, fixed costs for initiating and terminating service, and a variable operating cost incurred for each unit of time that the system is in operation. We show under some weak conditions with respect to the holding cost rate function and the service time, vacation time and arrival batch size distributions that it is either optimal among all feasible (stationary and non-stationary) policies never to take a vacation, or it is optimal to take a vacation when the system empties out and to resume work when, upon completion of a vacation, the queue size is equal to or in excess of a critical threshold. These optimality results are generalized for several variants of this model.

Keywords

VACATION MODELSREMOVABLE SERVERMONOTONE POLICIESSEMI-MARKOV DECISION PROCESS
Type
Research Article
Information
Advances in Applied Probability , Volume 23 , Issue 2 , June 1991 , pp. 388 - 405
Copyright
Copyright © Applied Probability Trust 1991 

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

Baba, Y. (1986) On the MX/G/1 queue with vacation time. Operat. Res. Lett. 5, 93–98.Google Scholar
Balachandran, K. R. (1973) Control policies for a single server system. Management Sci. 19, 1013–1018.Google Scholar
Balachandran, K. R. and Tijms, H. C. (1975) On the D-policy for the M/G/1 queue. Management Sci. 21, 1073–1076.Google Scholar
Bell, C. E. (1971) Characterization and computation of optimal policies for operating an M/G/1 queueing system with removable server. Operat. Res. 19, 208–218.Google Scholar
Boxma, O. J. (1976) Note on a control problem of Balachandran and Tijms. Management Sci. 22, 916–917.Google Scholar
Chaudhry, M. and Templeton, J. (1983) A First Course in Bulk Queues. Wiley Interscience, New York.Google Scholar
Cooper, R. B. (1970) Queues served in cyclic order waiting times. Bell Syst. Tech. J. 49, 399–413.Google Scholar
Cooper, R. B. (1981) Introduction to Queueing Theory , 2nd edn. Elsevier North-Holland, New York.Google Scholar
Doshi, B. T. (1986) Queueing systems with vacations—a survey. Queueing Systems 1, 29–66.Google Scholar
Federgruen, A. and So, K. C. (1989) Optimal time to repair a broken server. Adv. Appl. Prob. 21, 376–397.CrossRefGoogle Scholar
Federgruen, A. and So, K. C. (1990) Optimal maintenance policies for single-server queueing systems subject to breakdowns. Operat. Res. 38, 330–343.Google Scholar
Heyman, D. P. (1968) Optimal operating policies for M/G/1 queueing systems. Operat. Res. 16, 362–382.Google Scholar
Heyman, D. P. (1977) The T-Policy for the M/G/1 queue. Management Sci. 23, 775–778.Google Scholar
Heyman, D. P. and Sobel, M. J. (1982) Stochastic Models in Operations Research : Volume I. McGraw-Hill, New York.Google Scholar
Hofri, M. (1986) Queueing systems with a procrastinating server. Proc. Joint Conf. Computer Performance Modeling, Measurement, and Evaluation, Raleigh , NC, 245–253.Google Scholar
Hordijk, A. and Van Der Duyn Schouten, F. A. (1984) Discretization and weak convergence in Markov decision drift processes: conditions for optimality obtained by discretization. Math. Operat. Res. 9, 112–141.Google Scholar
Hordijk, A. and Van Der Duyn Schouten, F. A. (1985) Markov decision drift processes: conditions for optimality obtained by discretization. Math. Operat. Res. 10, 160–173.Google Scholar
Kella, O. (1989) The threshold policy in the M/G/1 queue with server vacations. Naval Res. Logist. 36, 111–123.3.0.CO;2-3>CrossRefGoogle Scholar
Lee, H. S. and Srinivasan, M. M. (1989) Control policies for the MX/G/1 queueing system. Management Sci. 35, 708–721.Google Scholar
Levy, Y. and Yechiali, U. (1975) Utilization of idle time in an M/G/1 queueing system. Management Sci. 22, 202–211.Google Scholar
Nahmias, S. (1981) Managing repairable item inventory systems: a review. Chapter 6 in TIMS Studies in Management Science 16, ed. Schwarz, L..Google Scholar
Ross, S. M. (1970) Applied Probability Models with Optimization Applications. Holden-Day, San Francisco.Google Scholar
Ross, S. M. (1985) Introduction to Probability Models , 3rd edn. Academic Press, New York.Google Scholar
Schweitzer, P. J. (1971) Iterative solution of the functional equations for undiscounted Markov renewal programming. J. Math. Anal. Appl. 34, 495–501.Google Scholar
Sennott, L. I. (1989) Average cost optimal stationary policies in infinite state Markov decision processes with unbounded costs. Operat. Res. 37, 626–633.CrossRefGoogle Scholar
Skinner, C. E. (1967) A priority queueing system with server-walking time. Operat. Res. 15, 278–285.Google Scholar
So, K. C. (1985) Optimal maintenance policies for single-server queueing systems subject to breakdowns. Doctoral dissertation, Stanford University, California.Google Scholar
Sobel, M. J. (1969) Optimal average-cost policy for a queue with start-up and shut-down costs. Operat. Res. 17, 145–162.Google Scholar
Svonoros, A. P. (1986) A general framework for multi-echelon inventory and production control problems. Doctoral dissertation, Columbia University, New York.Google Scholar
Svonoros, A. P. and Zipkin, P. (1986) Evaluation of one-for-one replenishment policies for multi-echelon inventory systems. Working Paper No. 86–9, Graduate School of Business, Columbia University, New York.Google Scholar
Takagi, H. (1987) Queueing analysis of vacation models, Part I. M/G/1. Part II: M/G/1 with Vacations . Technical Report TR87-0032, IBM Tokyo Research Laboratory, Tokyo, Japan.Google Scholar
Teghem, J. Jr. (1986a) Control of the service process in a queueing system. European J. Operat. Res. 23, 141–158.Google Scholar
Teghem, J. Jr. (1986b) The (TN, TN–1, …, T1) policy for the M/G/1 queue. Technical Report, Faculté Polytechnique de Mons, 7000 Mons, Belgium.Google Scholar
Weber, R. R. and Stidham, S. Jr. (1987) Optimal control of service rates in networks of queues. Adv. Appl. Prob. 19, 202–218.Google Scholar
Wolff, R. W. (1989) Stochastic Modeling and the Theory of Queues. Prentice Hall, Englewood Cliffs, NJ.Google Scholar
Yadin, M. and Naor, P. (1963) Queueing systems with a removable service station. Operat. Res. Quart. 14, 393–405.Google Scholar