Sojourn distributions for particular customers in networks of queues

Abstract

In this paper a study of the transient behavior of sojourn distributions of particular customers traversing serial networks of single-server queues is presented. It is motivated by the need to project completion times of critical customers in loaded, capacitated queueing systems. In particular, serial networks with First-Come-First-Served queueing discipline which do not allow overtaking are considered. An analytic model based on a Markovian state space is shown to be computationally prohibitive even for relatively small scenarios. Given the limitation of the exact solution, heuristic schemes, based on a characterization of the behavior of the exact solution and the Central Limit Theorem, are developed as an alternative to digital Monte-Carlo simulation. A hybrid technique combining the estimated mean from one of the heuristics and the estimated variance from another proves to be accurate and efficient in approximating the mean and variance of the sojourn distribution in a variety of application scenarios.

Keywords

• Serial queueing networks
• Sojourn times
• Phase-type distributions

References

1. Boxma, O., Donk, P., 1982. On response time and cycle time distributions in a two-stage cyclic queue. Performance Eval 2, pp. 181–194.
2. Boxma, O., Kelly, F., Konheim, A., 1984. The product form for the sojourn time distribution in cyclic exponential queues. JACM 31, pp. 128–133.
3. Burke, P., 1972. Output processes and tandem queues. Proc. Symp. Comp.-Comm. Networks and Teletrac, pp. 419–428.
4. Chow, W., 1980. The cycle time distribution of exponential cyclic queues. JACM 27, pp. 281–286.
5. Daduna, H., 1982. Passage times for overtake-free paths in Gordon-Newell networks. Adv Appl Prob 14, pp. 672–686.
6. Daduna, H., 1984. Burke’s theorem on passage time in Gordon-Newell networks. Adv Appl Prob 16, pp. 867–886.
7. Gordon, W., Newell, G., 1967. Closed queueing systems with exponential servers. Operations Research 15, pp. 254–265.
8. Grassmann, W., 1977a. Transient solutions in Markovian queueing systems. Computers and OR 4, pp. 47–56.

9. Grassmann, W., 1977b. Transient solutions in Markovian queues. European Journal of OR 1, pp. 392–402.
10. Harrison, P., 1980. Distributions of time delays in queueing networks. Unpublished manuscript.
11. Harrison, P., 1984. A note on cycle times in tree-like queueing networks. Adv. Appl. Prob 16, pp. 216–219.
12. Kelly, F., Pollett, P., 1983. Sojourn times in closed queueing networks. Adv Appl Prob 15, pp. 638–656.
13. Lemoine, A., 1977. Networks of queues – a survey of equilibrium analysis. Management Science 24, pp. 464–481.
14. Melamed, B., 1982. Sojourn times in queueing networks. Math of OR 7, pp. 223–244.
15. Melamed, B., Yadin, M., 1984a. Numerical computation of sojourn-time distributions in queueing networks. JACM 31, pp. 839–854.
16. Melamed, B., Yadin, M., 1984b. Randomization procedures in the computation of cumulative-time distributions over discrete state. Markov processes. Operations Research 32, pp. 926–944.
17. Mitrani, I., 1979. A critical note on a result by Lemoine. Management Science 25, pp. 1026–1027.
18. Reich, E., 1957. Waiting times when queues are in tandem. Ann Math Stat 28, pp. 768–773.
19. Reich, E., 1963. Note on queueing in tandem. Ann Math Stat 34, pp. 338–341.
20. Schassburger, R., Daduna, H., 1983. The time for a round exponential queues. JACM 30, pp. 146–150.
21. Simon, B., Foley, R., 1979. Some results on sojourn times in acyclicJackson networks. Mana gement Science 25, pp. 1027–1034.
22. Takacs, L., 1962. Stochastic Processes. John Wiley and Sons, Inc. Walrand, J., Varaiya, P., 1980. Sojourn times and the overtaking condition in Jacksonian networks. Advances in Applied Probability 12, pp. 1000–1018.