Analysis of a discrete-time queue with general independent arrivals, general service demands and fixed service capacity
Tóm tắt
This paper analyzes a single-server discrete-time queueing model with general independent arrivals, where the service process of the server is characterized in two steps. Specifically, the model assumes that (1) each customer represents a random, arbitrarily distributed, amount of work for the server, the service demand, and (2) the server disposes of a fixed number of work units that can be executed per slot, the service capacity. For this non-classical queueing model, we obtain explicit closed-form results for the probability generating functions (pgf’s) of the unfinished work in the system (expressed in work units) and the queueing delay of an arbitrary customer (expressed in time slots). Deriving the pgf of the number of customers in the system turns out to be hard, in general. Nevertheless, we derive this pgf explicitly in a number of special cases, i.e., either for geometrically distributed service demands, and/or for Bernoulli arrivals or geometric arrivals. The obtained results show that the tail distributions of the unfinished work, the customer delay and the system content all exhibit a geometric decay, with semi-analytic formulas for the decay rates available. Another interesting conclusion is that, for a given system load, the mean customer delay converges to constant limiting values when the service capacity per slot goes to infinity, and either the mean arrival rate or the mean service demand increases proportionally. Accurate approximative analytical expressions are available for these limiting values.
Tài liệu tham khảo
Bruneel H (1983) Buffers with stochastic output interruptions. Electron Lett 19(18):735–737
Bruneel H (1984) A general model for the behaviour of infinite buffers with periodic service opportunities. Eur J Oper Res 16(1):98–106
Bruneel H (1986) Message delay in TDMA channels with contiguous output. IEEE Trans Commun 34(7):681–684
Bruneel H (1993) Performance of discrete-time queueing systems. Comput Oper Res 20(3):303–320
Bruneel H, Kim BG (1993) Discrete-time models for communication systems including ATM. Kluwer Academic, Boston
Bruneel H, Walraevens J, Claeys D, Wittevrongel S (2012) Analysis of a discrete-time queue with geometrically distributed service capacities. In: Proceedings of 19th international conference on analytical and stochastic modeling techniques and applications. ASMTA 2012, Grenoble, France, pp 121–135
Chaudhry M, Singh G, Gupta U (2013) A simple and complete computational analysis of MAP/R/1 queue using roots. Methodol Comput Appl Probab 15(3):563–582
Claeys D, Laevens K, Walraevens J, Bruneel H (2010) Complete characterisation of the customer delay in a queueing system with batch arrivals and batch service. Math Methods Oper Res 72(1):1–23
Claeys D, Steyaert B, Walraevens J, Laevens K, Bruneel H (2013) Tail probabilities of the delay in a batch-service queueing model with batch-size dependent service times and a timer mechanism. Comput Oper Res 40(5):1497–1505
Creemers S, Belien J, Lambrecht M (2012) The optimal allocation of server time slots over different classes of patients. Eur J Oper Res 219(3):508–521
Dong M, Hou F (2012) Modelling and implementation of manufacturing direct labour allocation: a case study in semiconductor production operations. Int J Prod Res 50(4):1029–1044
Fiems D, Bruneel H (2002) A note on the discretization of Little’s result. Oper Res Lett 30(1):17–18
Gao P, Wittevrongel S, Bruneel H (2004) Discrete-time multiserver queues with geometric service times. Comput Oper Res 31:81–99
Georganas ND (1976) Buffer behavior with poisson arrivals and bulk geometric service. IEEE Trans Commun 24(8):938–940
Gonzáles MO (1992) Classical complex analysis. Marcel Dekker, New York
Haughton M, Isotupa KPS (2013) Flow control in capacity-constrained queueing systems with non-stationary arrivals. J Oper Res Soc 64(2):283–292
Heines TS (1979) Buffer behavior in computer communication systems. IEEE Trans Comput 28(8):573–576
Hsu J (1974) Buffer behavior with poisson arrival and geometric output process. IEEE Trans Commun 22(12):1940–1941
Janssen A, van Leeuwaarden J (2005) A discrete queue, Fourier sampling on Szego curves and Spitzer formulas. Int J Wavelets Multiresolut Inf Process 3(3):361–387
Kleinrock L (1975) Queueing systems, part I. Wiley, New York
Kravanja P, Van Barel M, Ragos O, Vrahatis M, Zafiropoulos F (2000) ZEAL: a mathematical software package for computing zeros of analytic functions. Comput Phys Commun 124(2–3):212–232
Laevens K, Bruneel H (1995) Delay analysis for discrete-time queueing systems with multiple randomly interrupted servers. Eur J Oper Res 85(1):161–177
Ling X, Hu M, Long J, Ding J, Shi Q (2013) Traffic resource allocation for complex networks. Chin Phys B 22(1). doi:10.1088/1674-1056/22/1/018904
Liu Z, Chua D, Yeoh K (2011) Aggregate production planning for shipbuilding with variation-inventory trade-offs. Int J Prod Res 49(20):6249–6272
Maertens T, Walraevens J, Bruneel H (2007) A modified HOL priority scheduling discipline: performance analysis. Eur J Oper Res 180(3):1168–1185
Mitrani I (1987) Modelling of computer and communication systems. Cambridge University Press, Cambridge
Papoulis A, Pillai SU (2002) Probability, random variables, and stochastic processes, 4th edn. Mc Graw-Hill, New York
Rogiest W, Fiems D, Laevens K, Bruneel H (2009) Modeling the performance of FDL buffers with wavelength conversion. IEEE Trans Commun 57(12):3703–3711
Shahnazari-Shahrezaei P, Tavakkoli-Moghaddam R, Azarkish M, Sadeghnejad-Barkousaraie A (2012) A differential evolution algorithm developed for a nurse scheduling problem. S Afr J Ind Eng 23(3):68–90
Takagi H (1993) Queueing analysis, a foundation of performance evaluation, discrete-time systems, vol 3. North-Holland, Amsterdam