Abstract
One of the most fundamental properties that single-server multi-class service systems may possess is the property of work conservation. Under certain restrictions, the work conservation property gives rise to a conservation law for mean waiting times, i.e., a linear relation between the mean waiting times of the various classes of customers. This paper is devoted to single-server multi-class service systems in which work conservation is violated in the sense that the server's activities may be interrupted although work is still present. For a large class of such systems with interruptions, a decomposition of the amount of work into two independent components is obtained; one of these components is the amount of work in the corresponding systemwithout interruptions. The work decomposition gives rise to a (pseudo)conservation law for mean waiting times, just as work conservation did for the system without interruptions.
Similar content being viewed by others
References
J.E. Baker and I. Rubin, Polling with a general-service order table, IEEE Trans. Commun., COM-35 (1987) 283–288.
D.P. Bertsekas and R.G. Gallager,Data Networks (Prentice-Hall, Inc., Englewood Cliffs, 1987).
O.J. Boxma and W.P. Groenendijk, Pseudo-conservation laws in cyclic-service systems, J. Appl. Prob.24 (1987) 949–964.
O.J. Boxma and W.P. Groenendijk, Waiting times in discrete-time cyclic-service systems, IEEE Trans. Commun. COM-36 (1988) 164–170.
O.J. Boxma and W.P. Groenendijk, Two queues with alternating service and switching times, In:Queueing Theory and its Applications — Liber Amicorum for J. W. Cohen, eds. O.J. Boxma and R. Syski (North-Holland, Amsterdam, 1988) 261–282.
O.J. Boxma, W.P. Groenendijk and J.A. Weststrate, A pseudoconservation law for service systems with a polling table, Report Centre for Mathematics and Computer Science, Amsterdam, 1988; to appear in IEEE Trans. Commun.
O.J. Boxma and B. Meister, Waiting-time approximations for cyclic-service systems with switch-over times, Performance Evaluation Review14 (1986) 254–262.
O.J. Boxma and J.A. Weststrate, Waiting times in polling systems with Markovian server routing, Report Centre for Mathematics and Computer Science, Amsterdam, 1989; to appear in:Messung, Modellierung und Bewertung von Rechensystemen und Netzen, eds. G. Stiege and J.S. Lie (Springer, Berlin, 1989).
S. Browne and U. Yechiali, Dynamic priority rules for cyclic-type queues, Adv. Appl. Prob.21 (1989) 432–450.
S.L. Brumelle, On the relation between customer and time averages in queues, J. Appl. Prob.8 (1971) 508–520.
B.T. Doshi, Queueing systems with vacations-a survey, Queueing Systems1 (1986) 29–66.
B.T. Doshi, Generalizations of the stochastic decomposition results for single server queues with vacations, Report AT&T Bell Labs, Holmdel (NJ), 1988.
D.E. Everitt, Simple approximations for token rings, IEEE Trans. Commun. COM-34 (1986) 719–721.
D.E. Everitt, A conservation-type law for the token ring with limited service, Br. Telecom Technol.J. 4 (1986) 51–61.
D.E. Everitt, A note on the pseudoconservation laws for cyclic service systems with limited service disciplines, IEEE Trans. Commun. COM-37 (1989) 781–783.
A. Federgruen and H. Groenevelt, M/G/c queueing systems with multiple customer classes: characterization and control of achievable performance under nonpreemptive priority rules, Management Sci.34 (1988) 1121–1138.
M.J. Ferguson and Y.J. Aminetzah, Exact results for nonsymmetric token ring systems, IEEE Trans. Commun. COM-33 (1985) 223–231.
S.G. Foss, Queues with customers of several types, In:Advances in Probability Theory: Limit Theorems & Related Problems, ed. A.A. Borovkov (Optimization Software Inc., New York, 1984).
S.W. Fuhrmann, Inequalities for cyclic service systems with limited service, In:Proc. GLOBECOM '87.
S.W. Fuhrmann and R.B. Cooper, Stochastic decompositions in the M/G/1 queue with generalized vacations, Oper. Res.33 (1985) 1117–1129.
S.W. Fuhrmann and Y.T. Wang, Mean waiting time approximations of cyclic service systems with limited service, In:Performance '87, eds. P.-J. Courtois and G. Latouche (North-Holland Publ. Cy., Amsterdam, 1988) 253–265.
E. Gelenbe and I. Mitrani,Analysis and Synthesis of Computer Systems (Academic Press, New York, 1980).
N.P. Giannakouros and A. Laloux, A general conservation law for a priority polling system, Report Telecommunications Laboratory, Leuven University, 1988.
W.P. Groenendijk, Waiting-time approximations for cyclic-service systems with mixed service strategies, In:Proc. 12th ITC (North-Holland Publ. Co., Amsterdam, 1989).
W.P. Groenendijk, A conservation-law based approximation algorithm for waiting times in polling systems, Report Centre for Mathematics and Computer Science, Amsterdam, 1988.
S. Halfin, Batch delays versus customer delays, Bell System Tech. J.62 (1983) 2011–2015.
D.P. Heyman and M.J. Sobel,Stochastic Models in Operations Research, Vol. I. (McGraw-Hill Book Company, New York, 1982).
T. Katayama, A cyclic service tandem queueing model with semi-exhaustive service, Report NTT Communication Switching Laboratories, Tokyo, 1987; to appear in theProc. Int. Seminar on Performance of Distributed and Parallel Systems, Kyoto, Japan.
J. Keilson and L.D. Servi, Oscillating random walk models for GI/G/1 vacation systems with Bernoulli schedules, J. Appl. Prob.23 (1986) 790–802.
L. Kleinrock,Communication Nets-Stochastic Message Flow and Delay (Dover, New York, 1964).
L. Kleinrock, A conservation law for a wide class of queueing disciplines, Naval Res. Logist. Quart.12 (1965) 181–192.
L. Kleinrock,Queueing Systems, Vol. II (Wiley, New York, 1976).
L. Kleinrock and H. Levy, The analysis of random polling systems, Oper. Res.36 (1988), 716–732.
G.P. Klimov, Time-sharing service systems, I, Theory of Prob. and its Appl.19 (1974) 532–551.
H. Levy, Optimization of polling systems via binomial service, Report Department of Computer Science, Tel-Aviv University, 1988.
H. Levy and M. Sidi, Correlated arrivals in polling systems, Report Department of Computer Science, Tel-Aviv University, 1988.
H. Levy, M. Sidi and O.J. Boxma, Dominance relations in polling systems, Report Department of Computer Science, Tel-Aviv University, 1988; to appear in Queueing Systems.
S.S. Nair, A single server tandem queue, J. Appl. Prob.8 (1971) 95–109.
T.J. Ott, On the M/G/1 queue with additional inputs, J. Appl. Prob.21 (1984) 129–142.
J.W.M. Pang and R.W. Donaldson, Approximate delay analysis and results for asymmetric token-passing and polling networks, IEEE J. Sel. Areas in Commun. SAC-4 (1986) 783–793.
L. Schrage, An alternative proof of a conservation law for the queue G/G/1, Oper. Res. 18 (1970) 185–187.
M. Sidi and H. Levy, A queueing network with a single cyclically roving server, Report Electrical Engineering Department, Technion, 1988.
M.M. Srinivasan, An approximation for mean waiting times in cyclic server systems with nonexhaustive service, Performance Evaluation9 (1988) 17–33.
H. Takagi,Analysis of Polling Systems (The MIT Press, Cambridge, Massachusetts, 1986).
H. Takagi, Queuing analysis of polling models, ACM Comp. Surveys20 (1988) 5–28.
M. Taube-Netto, Two queues in tandem attended by a single server, Oper. Res.25 (1977) 140–147.
Tedijanto, Exact results for the cyclic-service queue with a Bernoulli schedule, Report Electrical Engineering Department and Systems Research Center, University of Maryland, 1988.
K.S. Watson, Performance evaluation of cyclic service strategies-a survey, In:Performance'84, ed. E. Gelenbe (North-Holland Publ. Cy., Amsterdam, 1988) 521–533.
R.W. Wolff, Work-conserving priorities, J. Appl. Prob7 (1969) 327–337.
R.W. Wolff, Poisson arrivals see time averages, Oper. Res.30 (1982) 223–231.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Boxma, O.J. Workloads and waiting times in single-server systems with multiple customer classes. Queueing Syst 5, 185–214 (1989). https://doi.org/10.1007/BF01149192
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01149192