Abstract
This paper investigates a discrete-time priority queue with multi-class customers. Applying a delay-cycle analysis, we explicitly derive the probability generating function of the waiting time for an individual class in a geometric batch input queue under preemptive-resume and head-of-the-line priority rules. The conservation law and waiting time characterization for a general class of discrete-time queues are also presented. The results in this paper cover several previous results as special cases.
Similar content being viewed by others
References
B. Bartsch and G. Bolch, A conservation law forG/G/m queueing systems, Acta Inf. 10 (1978) 105–109.
P.E. Boudreau, J.S. Griffin, Jr., and M. Kac, A discrete queueing problem with variable service rates, IBM J. Res. Dev. 6 (1962) 407–418.
O.J. Boxma and W.P. Groenendijk, Waiting times in discrete-time cyclic service systems, IEEE Trans. Commun. COM-36 (1988) 164–170.
H. Bruneel, Analysis at service completion times of buffers with output interruptions, Zeit. Oper. Res. 29 (1984) 301–313.
P.J. Burke, Delays in single-server queues with batch input, Oper. Res. 23 (1975) 830–833.
R.W. Conway, W.L. Maxwell and L.W. Miller,Theory of Scheduling (Addison-Wesley, Reading, 1967).
S.C. Dafermos and M.F. Neuts, A single server queue in discrete time, Cahiers du Centre d'Etudes de Recherche Operationelle 13 (1971) 23–40.
J.N. Daigle and C.H. Houstis, Analysis of a task oriented multipriority system, IEEE Trans. Commun. COM-29 (1981) 1669–1677.
S. Halfin, Batch delays versus customer delays, BSTJ 62 (1983) 2011–2015.
O. Hashida, Discrete-timeGeom [X]/G/1 queue with preemptive priority,The 1989 Fall Natl. Conf. ORSJ, 1-B-7 (October 1989).
N.K. Jaiswal,Priority Queues (Academic Press, New York, 1968).
O. Kella and U. Yechiali, Priorities inM/G/1 queue with server vacations, Naval Res. Logist. 35 (1988) 23–34.
B.G. Kim, A single-server discrete-time queueing system: With and without priorities,Proc. GLOBECOM'88, 16.5.1–16.5.5.
T. Meisling, Discrete-time queueing theory, Oper. Res. 6 (1958) 96–105.
B. Meister, Waiting time in a preemptive resume system with compound Poisson input, Computing 25 (1980) 17–28.
B.A. Powell and B. Avi-Itzhak, Queueing system with enforced idle time, Oper. Res. 15 (1967) 1145–1156.
I. Rubin and Z. Tsai, Message delay analysis of multiclass priority TDMA, FDMA, and discrete-time queueing systems, IEEE Trans. Inf. Theory IT-35 (1989) 637–647.
L. Schrage, An alternative proof of a conservation law for the queueG/G/1, Oper. Res. 18 (1970) 185–187.
M. Sidi and A. Segall, Two interfering queues in packet-radio networks, IEEE Trans. Commun. COM-31 (1983) 123–129.
M. Sidi and A. Segall, Structured priority queueing systems with applications to packet-radio networks, Performance Evaluation 3 (1983) 265–275.
M. Sidi, Two competing discrete-time queues with priority, Queueing Systems 3 (1988) 347–362.
B. Simon, Priority queues with feedback, JACM 31 (1984) 134–149.
B.W. Stuck and E. Arthurs,A Computer and Communications Network Performance Analysis Primer (Prentice-Hall, New Jersey, 1985).
Y. Takahashi, On the relationship between work load and waiting time in single server queues with batch inputs, Oper. Res. Lett. 7 (1988) 51–56.
D. Towsley, The analysis of a statistical multiplexer with nonindependent arrivals and errors, IEEE Trans. Commun. COM-28 (1980) 65–72.
R.W. Wolff, Work-conserving priorities, J. Appl. Prob. 7 (1970) 327–337.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Takahashi, Y., Hashida, O. Delay analysis of discrete-time priority queue with structured inputs. Queueing Syst 8, 149–163 (1991). https://doi.org/10.1007/BF02412247
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02412247