Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

A simple load balancing problem with decentralized information

  • Published:
Mathematical Methods of Operations Research Aims and scope Submit manuscript

Abstract

The following load balancing problem is investigated in discrete time: A service system consists of two service stations and two controllers, one in front of each station. The service stations provide the same service with identical service time distributions and identical waiting costs. Customers requiring service arrive at a controller's site and are routed to one of the two stations by the controller. The processes describing the two arrival streams are identical. Each controller has perfect knowledge of the workload in its own station and receives information about the other station's workload with one unit of delay. The controllers' routing strategies that minimize the customers' total flowtime are determined for a certain range of the parameters that describe the arrival process and the service distribution. Specifically, we prove that optimal routing strategies are characterized by thresholds that are either precisely specified or take one of two possible values.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bell CW, Stidham S (1983) Individual versus social optimization in the allocation of customers to alternative servers. Management Sci 29:831–839

    Google Scholar 

  2. Beutler F, Teneketzis D (1989) Routing in queueing networks under imperfect information: Stochastic dominance and thresholds. Stoch Stoch Rep 26:81–100

    Google Scholar 

  3. Boel RK, van Schuppen JH (1989) Distributed routing for load balancing. Proc IEEE, Special Issue on Dynamics of Discrete Events Systems 210–221

  4. Chang C-S (1992) A new ordering for stochastic majorization: Theory and applications. Adv Appl Prob 24:604–634

    Google Scholar 

  5. Davis E (1977) Optimal control of arrivals to a two-server queueing system with separate queues. PhD dissertation, Program in Operations Research, North Carolina State University, Raleigh, NC

    Google Scholar 

  6. Ephremides A, Varaiya P, Walrand J (1980) A simple dynamic routing problem. IEEE Trans Automat Control 25:690–693

    Google Scholar 

  7. Hajek B (1984) Optimal control of two interacting service stations. IEEE Trans Automat Control 29:491–499

    Google Scholar 

  8. Hajek B (1990) Performance of global load balancing by local adjustment. IEEE Trans Inform Theory 36:1398–1414

    Google Scholar 

  9. Hordijk A, Koole G (1990) On the optimality of the generalized shortest queue policy. Prob Eng Inf Sci 4:477–489

    Google Scholar 

  10. Lin W, Kumar PR (1984) Optimal control of a queueing system with two heterogeneous servers. IEEE Trans Automat Control 29:696–703

    Google Scholar 

  11. Pandelis DG, Teneketzis D (1993) A simple load balancing problem with decentralized information. Control Group Report No CGR-93-13, Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, MI

    Google Scholar 

  12. Ross S (1983) Stochastic processes. Wiley, New York

    Google Scholar 

  13. Stamoulis GD, Tsitsiklis JN (1991) Optimal distributed policies for choosing among multiple servers. Proc 30th CDC, Brighton, UK 815–820

  14. Stidham S (1985) Optimal control of admission to a queueing system. IEEE Trans Automat Control 30:705–713

    Google Scholar 

  15. [15]Varaiya P, Walrand J (1978) On delayed sharing patterns. IEEE Trans Automat Control 23:443–445

    Google Scholar 

  16. Varaiya P, Walrand J (1978) On delayed sharing patterns. IEEE Trans Automat Control 23:443–445

    Google Scholar 

  17. Walrand J (1984) A note on “Optimal control of a queueing system with two heterogeneous servers”. System Control Lett 4:131–134

    Google Scholar 

  18. Weber RR (1978) On the optimal assignment of customers to parallel servers. J Appl Prob 15:406–413

    Google Scholar 

  19. Winston W (1977) Optimality of the shortest line discipline. J Appl Prob 14:181–189

    Google Scholar 

  20. Witsenhausen HS (1971) Separation of estimation and control for discrete time systems. Proc IEEE 59:1559–1566

    Google Scholar 

  21. Whitt W (1986) Deciding which queue to join: Some counterexamples. Oper Res 34:55–62

    Google Scholar 

  22. Xu SH (1992) Socially and individually optimal routing of stochastic jobs in parallel processor systems. Oper Res 40:367–375

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Environmental Research Institute of Michigan, 3300 Plymouth Rd., 48105, Ann Arbor, MI, USA

    Dimitrios G. Pandelis

  2. Department of Electrical Engineering and Computer Science, University of Michigan, 48109-2122, Ann Arbor, MI, USA

    Demosthenis Teneketzis

Authors
  1. Dimitrios G. Pandelis
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Demosthenis Teneketzis
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Pandelis, D.G., Teneketzis, D. A simple load balancing problem with decentralized information. Mathematical Methods of Operations Research 44, 97–113 (1996). https://doi.org/10.1007/BF01246331

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01246331

Keywords

Search

Navigation