[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Cost sharing of cooperating queues in a Jackson network

  • Published:
Queueing Systems Aims and scope Submit manuscript

Abstract

We consider networks of queues in which the independent operators of individual queues may cooperate to reduce the amount of waiting. More specifically, we focus on Jackson networks in which the total capacity of the servers can be redistributed over all queues in any desired way. If we associate a cost to waiting that is linear in the queue lengths, it is known from the literature how the operators should share the available service capacity to minimize the long run total cost. This paper deals with the question whether or not (the operators of) the individual queues will indeed cooperate in this way, and if so, how they could share the cost in the new situation such that each operator never pays more than his own cost without cooperation. For the particular case of a tandem network with two or three nodes it is known from previous work that cooperation is indeed beneficial, but for larger tandem networks and for general Jackson networks this question was still open. The main result of this paper gives for any Jackson network an explicit cost allocation that is beneficial for all operators. The approach we use also works for other cost functions, such as the server utilization.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

We’re sorry, something doesn't seem to be working properly.

Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Similar content being viewed by others

Notes

  1. Where this is convenient, we will denote the permutation in the superscript without parentheses and commas; e.g., in Sect. 3.2 we write \(m^{123}(c)\) instead of \(m^{(1,2,3)}(c),\) etc.

  2. We may assume this without loss of generality by relabeling the nodes. If two or three queues have equal r value, either of these can be chosen as “the” queue with middle r value.

References

  1. Altman, E., Boulogne, T., El-Azouzi, R., Jiménez, T., Wynter, L.: A survey on networking games in telecommunications. Comput. Oper. Res. 33(2), 286–311 (2006)

    Article  Google Scholar 

  2. Andradóttir, S., Ayhan, H.: Throughput maximization for tandem lines with two stations and flexible servers. Oper. Res. 53, 516–531 (2005)

    Article  Google Scholar 

  3. Anily, S., Haviv, M.: Cooperation in service systems. Oper. Res. 58(3), 660–673 (2010)

    Article  Google Scholar 

  4. García-Sanz, M.D., Fernández, F.R., Fiestras-Janeiro, M.G., García-Jurado, I., Puerto, J.: Cooperation in Markovian queueing models. Eur. J. Oper. Res. 188(2), 485–495 (2008)

    Article  Google Scholar 

  5. Gibbens, R., Key, P.: Coalition games and resource allocation in ad-hoc networks. In: Liò, P., Yoneki, E., Crowcroft, J., Verma, D. (eds.) Bio-Inspired Computing and Communication, Volume 5151 of Lecture Notes in Computer Science, pp. 387–398. Springer, Berlin (2008)

    Google Scholar 

  6. Gibbens, R.J., Kelly, F.P., Cope, G.A., Whitehead, M.J.: Coalitions in the international network. In: Jensen A., Iversen V.B. (eds.) 13th International Teletraffic Congress (ITC), 1991, pp. 93–91 (1991)

  7. González, P., Herrero, C.: Optimal sharing of surgical costs in the presence of queues. Math. Methods Oper. Res. 59(3), 435–446 (2004)

    Google Scholar 

  8. Kleinrock, L.: Communication Nets: Stochastic Message Flow and Delay. McGraw-Hill, New York (1964)

    Google Scholar 

  9. Mandelbaum, A., Reiman, M.J.: On pooling in queueing networks. Manag. Sci. 44, 971–981 (1998)

    Article  Google Scholar 

  10. Peters, H.: Game Theory. Springer, Berlin (2008)

    Book  Google Scholar 

  11. Shapley, L.S., Shubik, M.: On market games. J. Econ. Theory 1(1), 9–25 (1969)

    Article  Google Scholar 

  12. Timmer, J., Scheinhardt, W.: How to share the cost of cooperating queues in a tandem network? In: 22nd International Teletraffic Congress (ITC), 2010, pp. 1–7 (2010)

  13. Walrand, J.: An Introduction to Queueing Networks. Prentice-Hall, New Jersey (1988)

    Google Scholar 

  14. Weber, R.J.: Probabilistic values for games. In: Roth, A.E. (ed.) The Shapley Value, Essays in Honor of Lloyd S. Shapley, pp. 101–119. Cambridge University Press, Cambridge (1988)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Applied Mathematics, University of Twente, P.O. Box 217, 7500 AE,  Enschede, The Netherlands

    Judith Timmer & Werner Scheinhardt

Authors
  1. Judith Timmer
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Werner Scheinhardt
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Werner Scheinhardt.

Additional information

In the Netherlands, the three universities of technology have formed the 3TU.Federation. This article is the result of joint research in the 3TU.Centre of Competence NIRICT (Netherlands Institute for Research on ICT).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Timmer, J., Scheinhardt, W. Cost sharing of cooperating queues in a Jackson network. Queueing Syst 75, 1–17 (2013). https://doi.org/10.1007/s11134-012-9336-4

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11134-012-9336-4

Keywords

Mathematics Subject Classification (2000)

Search

Navigation