Two-choice regulation in heterogeneous closed networks

详细信息    查看全文

• 作者：Christine Fricker ; Nicolas Servel
• 关键词：Bike ; sharing systems ; Stochastic networks ; Two ; choice ; Clusters ; Mean ; field ; Heterogeneous systems ; 60K25
• 刊名：Queueing Systems
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：82
• 期：1-2
• 页码：173-197
• 全文大小：732 KB
• 参考文献：1.Anselmi, J., D’Auria, B., Walton, N.: Closed queueing networks under congestion: non-bottleneck independence and bottleneck convergence. Math. Oper. Res. 38(3), 469–491 (2013)CrossRef
  2.Antunes, N., Fricker, C., Robert, P., Tibi, D.: Stochastic networks with multiple stable points. Ann. Probab. 36(1), 255–278 (2008)CrossRef
  3.Baskett, F., Chandy, K.M., Muntz, R.R., Palacios, F.G.: Open, closed, and mixed networks of queues with different classes of customers. J. Assoc. Comput. Mach. 22, 248–260 (1975)CrossRef
  4.Benaim, M.: On gradient like properties of population games, learning models and self reinforced processes. In: Bourguignon, J.-P., Jeltsch, R., Pinto, A.A., Viana, M. (eds.) Dynamics, Games and Science, vol. 1 of CIM Series in Mathematical Sciences, pp. 117–152. Springer International Publishing (2015)
  5.Budhiraja, A., Dupuis, P., Fischer, M., Ramanan, K.: Local stability of Kolmogorov forward equations for finite state nonlinear Markov processes. Electron. J. Probab. 20(81), 1–30 (2015)
  6.Chemla, D., Meunier, F., Calvo, R.W.: Bike sharing systems: solving the static rebalancing problem. Discret. Optim. (2012)
  7.Fayolle, G., Lasgouttes, J.-M.: Asymptotics and scalings for large product-form networks via the central limit theorem. Markov Process. Relat. Fields 2(2), 317–348 (1996)
  8.Fricker, C., Gast, N., Mohamed, A.: Mean field analysis for inhomogeneous bike sharing systems. In: AofA 2012, International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (2012)
  9.Fricker, C., Gast, N.: Incentives and redistribution in bike-sharing systems with stations of finite capacity. EURO J. Transp. Logist. 1–31 (2014)
  10.Ganesh, A., Lilienthal, S., Manjunath, D., Proutiere, A., Simatos, F.: Load balancing via random local search in closed and open systems. Queueing Syst. 71(3), 321–345 (2012)CrossRef
  11.George, D.K., Xia, C.H.: Asymptotic analysis of closed queueing networks and its implications to achievable service levels. SIGMETRICS Perform. Eval. Rev. 38(2), 3–5 (2010)CrossRef
  12.Kelly, F.P.: Reversibility and Stochastic Networks. Wiley Series in Probability and Mathematical Statistics. Wiley, Chichester (1979)
  13.Kogan, Y.: Another approach to asymptotic expansions for large closed queueing networks. Oper. Res. Lett. 11(5), 317–321 (1992)CrossRef
  14.Malyshev, V.A., Yakovlev, A.V.: Condensation in large closed Jackson networks. Ann. Appl. Probab. 6(1), 92–115 (1996)CrossRef
  15.Mitzenmacher, M.D.: The power of two choices in randomized load balancing. ProQuest LLC, Ann Arbor, MI. Thesis (Ph.D.)–University of California, Berkeley (1996)
  16.Mukhopadhyay, A., Mazumdar, R.R., Guillemin, F.: The power of randomized routing in heterogeneous loss systems. In: 27th International Teletraffic Congress Proceedings. Ghent (2015)
  17.Nair, R., Miller-Hooks, E., Hampshire, R.C., Bušić, A.: Large-scale vehicle sharing systems: analysis of vélib’. Int. J. Sustain. Transp. 7(1), 85–106 (2013)CrossRef
  18.Nicolas, G., Bruno, G.: A mean field model of work stealing in large-scale systems. SIGMETRICS ’10. In: Proceedings of the ACM SIGMETRICS international conference on Measurement and modeling of computer systems, pp. 13–24 (2010)
  19.Raviv, T., Tzur, M., Forma, I.: Static repositioning in a bike-sharing system: models and solution approaches. Eur. J. Transp. Logist. 2(3), 187–229 (2013)CrossRef
  20.Raviv, T., Kolka, O.: Optimal inventory management of a bike-sharing station. IIE Trans. 45(10), 1077 (2013)CrossRef
  21.Tibi, D.: Metastability in communication networks. Technical report. arXiv:​1002.​0796 (2010)
  22.Vvedenskaya, N.D., Dobrushin, R.L., Karpelevich, F.I.: A queueing system with a choice of the shorter of two queues: an asymptotic approach. Probl. Peredachi Inf. 32(1), 20–34 (1996)
  23.Waserhole, A., Jost, V., Brauner, N.: Pricing techniques for self regulation in vehicle sharing systems. Electron. Notes Discret. Math. 41, 149–156 (2013)CrossRef
  24.Xie, Q., Dong, X., Lu, Y., Srikant, R.: Power of d choices for large-scale bin packing: a loss model. In: ACM SIGMETRICS, pp. 321–334. Portland (2015). Accessed 15–19 June 2015
  
• 作者单位：Christine Fricker (1)
  Nicolas Servel (1)
  
  1. INRIA Paris-Rocquencourt, Domaine de Voluceau, 78153, Le Chesnay, France
  
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Operation Research and Decision Theory
  Computer Communication Networks
  Probability Theory and Stochastic Processes
  Production and Logistics
  Systems Theory and Control
  
• 出版者：Springer Netherlands
• ISSN：1572-9443

文摘

A heterogeneous closed network with N one-server queues with finite capacity and one infinite-server queue is studied. A target application is bike-sharing systems. Heterogeneity is taken into account through clusters queues of which have the same parameters. Incentives to the customer to go to the least-loaded one-server queue between two chosen within a cluster are investigated. By mean-field arguments, the limiting queue length stationary distribution as N gets large is analytically tractable. Moreover, when all customers follow incentives, the probability that a queue is empty or full is approximated. Sizing the system to improve performance is achievable under this policy. Keywords Bike-sharing systems Stochastic networks Two-choice Clusters Mean-field Heterogeneous systems