IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v217y2012i1p149-161.html
   My bibliography  Save this article

Analysis of job assignment with batch arrivals among heterogeneous servers

Author

Listed:
  • Zhang, Zhongju
  • Daigle, John

Abstract

We revisit the problem of job assignment to multiple heterogeneous servers in parallel. The system under consideration, however, has a few unique features. Specifically, repair jobs arrive to the queueing system in batches according to a Poisson process. In addition, servers are heterogeneous and the service time distributions of the individual servers are general. The objective is to optimally assign each job within a batch arrival to minimize the long-run average number of jobs in the entire system. We focus on the class of static assignment policies where jobs are routed to servers upon arrival according to pre-determined probabilities. We solve the model analytically and derive the structural properties of the optimal static assignment. We show that when the traffic is below a certain threshold, it is better to not assign any jobs to slower servers. As traffic increases (either due to an increase in job arrival rate or batch size), more slower servers will be utilized. We give an explicit formula for computing the threshold. Finally we compare and evaluate the performance of the static assignment policy to two dynamic policies, specifically the shortest expected completion policy and the shortest queue policy.

Suggested Citation

  • Zhang, Zhongju & Daigle, John, 2012. "Analysis of job assignment with batch arrivals among heterogeneous servers," European Journal of Operational Research, Elsevier, vol. 217(1), pages 149-161.
  • Handle: RePEc:eee:ejores:v:217:y:2012:i:1:p:149-161
    DOI: 10.1016/j.ejor.2011.09.001
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221711008046
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2011.09.001?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Susan H. Xu & Rhonda Righter & J. George Shanthikumar, 1992. "Optimal Dynamic Assignment of Customers to Heterogeneous Servers in Parallel," Operations Research, INFORMS, vol. 40(6), pages 1126-1138, December.
    2. Ernest Koenigsberg, 1966. "On Jockeying in Queues," Management Science, INFORMS, vol. 12(5), pages 412-436, January.
    3. Colin E. Bell & Shaler Stidham, Jr., 1983. "Individual versus Social Optimization in the Allocation of Customers to Alternative Servers," Management Science, INFORMS, vol. 29(7), pages 831-839, July.
    4. B. M. Rao & M. J. M. Posner, 1987. "Algorithmic and approximation analyses of the shorter queue model," Naval Research Logistics (NRL), John Wiley & Sons, vol. 34(3), pages 381-398, June.
    5. Ward Whitt, 1986. "Deciding Which Queue to Join: Some Counterexamples," Operations Research, INFORMS, vol. 34(1), pages 55-62, February.
    6. Grassmann, WK, 1980. "Transient and steady state results for two parallel queues," Omega, Elsevier, vol. 8(1), pages 105-112.
    7. Zhang, Zhongju & Fan, Weiguo, 2008. "Web server load balancing: A queueing analysis," European Journal of Operational Research, Elsevier, vol. 186(2), pages 681-693, April.
    8. Vijendra P. Singh, 1970. "Two-Server Markovian Queues with Balking: Heterogeneous vs. Homogeneous Servers," Operations Research, INFORMS, vol. 18(1), pages 145-159, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Zhen, Lu & Wang, Kai & Wang, Shuaian & Qu, Xiaobo, 2018. "Tug scheduling for hinterland barge transport: A branch-and-price approach," European Journal of Operational Research, Elsevier, vol. 265(1), pages 119-132.
    2. Chou, Yon-Chun & Lin, Yue-Lan & Chun, King-Fai, 2014. "A construction of knowledge rules for reactive planning of job-mix assignment to homogeneous serial batch machines," International Journal of Production Economics, Elsevier, vol. 151(C), pages 56-66.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Plinio S. Dester & Christine Fricker & Danielle Tibi, 2017. "Stationary analysis of the shortest queue problem," Queueing Systems: Theory and Applications, Springer, vol. 87(3), pages 211-243, December.
    2. Parlakturk, Ali & Kumar, Sunil, 2004. "Self-Interested Routing in Queueing Networks," Research Papers 1782r, Stanford University, Graduate School of Business.
    3. M. Saxena & I. Dimitriou & S. Kapodistria, 2020. "Analysis of the shortest relay queue policy in a cooperative random access network with collisions," Queueing Systems: Theory and Applications, Springer, vol. 94(1), pages 39-75, February.
    4. Boronico, Jess S. & Siegel, Philip H., 1998. "Capacity planning for toll roadways incorporating consumer wait time costs," Transportation Research Part A: Policy and Practice, Elsevier, vol. 32(4), pages 297-310, May.
    5. Olga Bountali & Antonis Economou, 2019. "Strategic customer behavior in a two-stage batch processing system," Queueing Systems: Theory and Applications, Springer, vol. 93(1), pages 3-29, October.
    6. Danielle Tibi, 2019. "Martingales and buffer overflow for the symmetric shortest queue model," Queueing Systems: Theory and Applications, Springer, vol. 93(1), pages 153-190, October.
    7. Ali K. Parlaktürk & Sunil Kumar, 2004. "Self-Interested Routing in Queueing Networks," Management Science, INFORMS, vol. 50(7), pages 949-966, July.
    8. Rob Shone & Vincent A. Knight & Paul R. Harper, 2020. "A conservative index heuristic for routing problems with multiple heterogeneous service facilities," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 92(3), pages 511-543, December.
    9. Nur Sunar & Yichen Tu & Serhan Ziya, 2021. "Pooled vs. Dedicated Queues when Customers Are Delay-Sensitive," Management Science, INFORMS, vol. 67(6), pages 3785-3802, June.
    10. A. Wang & I. Ziedins, 2018. "Probabilistic selfish routing in parallel batch and single-server queues," Queueing Systems: Theory and Applications, Springer, vol. 88(3), pages 389-407, April.
    11. Jeganathan, K. & Abdul Reiyas, M. & Prasanna Lakshmi, K. & Saravanan, S., 2019. "Two server Markovian inventory systems with server interruptions: Heterogeneous vs. homogeneous servers," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 155(C), pages 177-200.
    12. Josh Reed & Yair Shaki, 2015. "A Fair Policy for the G / GI / N Queue with Multiple Server Pools," Mathematics of Operations Research, INFORMS, vol. 40(3), pages 558-595, March.
    13. J. P. C. Blanc, 1992. "The Power-Series Algorithm Applied to the Shortest-Queue Model," Operations Research, INFORMS, vol. 40(1), pages 157-167, February.
    14. Keumseok Kang & J. George Shanthikumar & Kemal Altinkemer, 2016. "Postponable Acceptance and Assignment: A Stochastic Dynamic Programming Approach," Manufacturing & Service Operations Management, INFORMS, vol. 18(4), pages 493-508, October.
    15. Athanasia Manou & Antonis Economou & Fikri Karaesmen, 2014. "Strategic Customers in a Transportation Station: When Is It Optimal to Wait?," Operations Research, INFORMS, vol. 62(4), pages 910-925, August.
    16. V.D. Dinopoulou & C. Melolidakis, 2001. "Asymptotically optimal component assembly plans in repairable systems and server allocation in parallel multiserver queues," Naval Research Logistics (NRL), John Wiley & Sons, vol. 48(8), pages 732-746, December.
    17. Niño-Mora, José, 2012. "Towards minimum loss job routing to parallel heterogeneous multiserver queues via index policies," European Journal of Operational Research, Elsevier, vol. 220(3), pages 705-715.
    18. Corine M. Laan & Judith Timmer & Richard J. Boucherie, 2021. "Non-cooperative queueing games on a network of single server queues," Queueing Systems: Theory and Applications, Springer, vol. 97(3), pages 279-301, April.
    19. D. P. Song & Y. X. Sun & W. Xing, 1998. "Optimal Control of a Stochastic Assembly Production Line," Journal of Optimization Theory and Applications, Springer, vol. 98(3), pages 681-700, September.
    20. Zhang, Zhongju & Fan, Weiguo, 2008. "Web server load balancing: A queueing analysis," European Journal of Operational Research, Elsevier, vol. 186(2), pages 681-693, April.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:217:y:2012:i:1:p:149-161. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.