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

Allocation of jobs and identical resources with two pooling centers

  • Published:
Queueing Systems Aims and scope Submit manuscript

Abstract

We examine the resource allocation problem of partitioning identical servers into two parallel pooling centers, and simultaneously assigning job types to pooling centers. Each job type has a distinct Poisson arrival rate and a distinct holding cost per unit time. Each pooling center becomes a queueing system with an exponential service time distribution. The goal is to minimize the total holding cost. The problem is shown to be polynomial if a job type can be divided between the pooling centers, and NP-hard if dividing job types is not possible. When there are two servers and jobs cannot be divided, we demonstrate that the two pooling center configuration is rarely optimal. A heuristic which checks the single pooling center has an upper bound on the relative error of 4/3. The heuristic is extended for the multiple server problem, where relative error is bounded above by the number of servers.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bain LJ, Engelhardt M. Introduction to probability and mathematical statistics. Boston: PWS-KENT Publishing Company; 1992.

    Google Scholar 

  2. Bell CE, Stidham S. Individual versus social optimization in the allocation of customers to alternative servers. Manag Sci 1983;29:831–9.

    Google Scholar 

  3. Calabrese JM. Optimal workload allocation in open networks of multiserver queues. Manag Sci 1992;38:1792–802.

    Google Scholar 

  4. Dallery Y, Stecke KE. On the optimal allocation of servers and workloads in closed queueing networks. Oper Res 1990;38:694–703.

    Google Scholar 

  5. Dyer ME, Proll LG. On the validity of marginal analysis for allocating servers in M/M/c queues (in notes). Manag Sci 1977;23:1019–22.

    Google Scholar 

  6. Frenk H, Labbe M, van Vliet M, Zhang S. Improved algorithms for machine allocation in manufacturing systems. Oper Res 1994;42:523–30.

    Google Scholar 

  7. Garey MR, Johnson DS. Computers and intractability: a guide to the theory of NP-completeness. San Francisco: Freeman; 1979.

    Google Scholar 

  8. Gilbert SM, Weng ZK. Incentive effects favor nonconsolidating queues in a service system: the principal-agent perspective. Manag Sci 1998;44:1662–9.

    Google Scholar 

  9. Green LV. A queueing system with general-use and limited-use servers. Oper Res 1985;33:168–82.

    Google Scholar 

  10. Green LV, Guha D. On the efficiency of imbalance in multi-facility multi-server service systems. Manag Sci 1995;41:179–87.

    Google Scholar 

  11. Hillier FS, Lieberman GJ. Introduction to operations research. New York: MacGraw–Hill; 2001.

    Google Scholar 

  12. Hillier FS, So KC. Toward characterizing the optimal allocation of storage space in production line systems with variable processing times (in notes). Manag Sci 1993;39:126–33.

    Google Scholar 

  13. Hillier FS, So KC. On the simultaneous optimization of server and work allocations in production line systems with variable processing times. Oper Res 1996;44:435–43.

    Google Scholar 

  14. Kimemia J, Gershwin SB. Flow optimization in flexible manufacturing systems. Int J Prod Res 1985;23(1):81–96.

    Google Scholar 

  15. Lee HL, Cohen MA. Multi-agent customer allocation in a stochastic service system. Manag Sci 1985;31:752–63.

    Article  Google Scholar 

  16. Rolfe AJ. A note on marginal allocation in multiple-server service systems. Manag Sci 1971;17:656–8.

    Google Scholar 

  17. Roque DR. A note on “Queuing models with lane selection”. Oper Res 1980;28:419–20.

    Google Scholar 

  18. Rothkopf MH, Rech P. Perspectives on queues: combining queues is not always beneficial. Oper Res 1987;35:906–9.

    Google Scholar 

  19. Schwartz BL. Queuing models with lane selection: a new class of problems. Oper Res 1974;22:331–9.

    Google Scholar 

  20. Schwartz BL. Errata: queuing models with lane selection: a new class of problems. Oper Res 1976;24:386.

    Google Scholar 

  21. Shanthikumar JG, Yao DD. Optimal server allocation in a system of multi-server station. Manag Sci 1987;33:1173–80.

    Google Scholar 

  22. Shanthikumar JG, Yao DD. On server allocation in multiple center manufacturing systems. Oper Res 1988;36:333–42.

    Google Scholar 

  23. Smith DR, Whitt W. Resource sharing for efficiency in traffic systems. Bell Syst Tech J 1981;60:39–55.

    Google Scholar 

  24. Stecke KE, Solberg JJ. The optimality of unbalancing both workloads and machine group sizes in closed queueing networks of multiserver queues. Oper Res 1985;33:882–910.

    Google Scholar 

  25. Stidham S. On the optimality of single-server queuing system. Oper Res 1970;18:708–32.

    Google Scholar 

  26. Whitt W. Partitioning customers into service groups. Manag Sci 1999;45:1579–92.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. The Ohio State University, Industrial Engineering, 1971 Neil Avenue, Columbus, OH, 43210, USA

    Hui-Chih Hung & Marc E. Posner

Authors
  1. Hui-Chih Hung
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marc E. Posner
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Marc E. Posner.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hung, HC., Posner, M.E. Allocation of jobs and identical resources with two pooling centers. Queueing Syst 55, 179–194 (2007). https://doi.org/10.1007/s11134-007-9015-z

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11134-007-9015-z

Keywords

Mathematics Subject Classification (2000)

Search

Navigation