An infinite server system with packing constraints and ranked servers

Alexander L. Stolyar ()
Additional contact information
Alexander L. Stolyar: University of Illinois at Urbana-Champaign

Queueing Systems: Theory and Applications, 2025, vol. 109, issue 3, No 1, 24 pages

Abstract: Abstract A service system with multiple types of customers, arriving as Poisson processes, is considered. The system has infinite number of servers, ranked by $$1,2,3, \ldots $$ 1 , 2 , 3 , … ; a server rank is its “location." Each customer has an independent exponentially distributed service time, with the mean determined by its type. Multiple customers (possibly of different types) can be placed for service into one server, subject to “packing” constraints. Service times of different customers are independent, even if served simultaneously by the same server. The large-scale asymptotic regime is considered, such that the mean number of customers r goes to infinity. We seek algorithms with the underlying objective of minimizing the location (rank) U of the right-most (highest ranked) occupied (non-empty) server. Therefore, this objective seeks to minimize the total number Q of occupied servers and keep the set of occupied servers as far at the “left” as possible, i.e., keep U close to Q. In previous work, versions of Greedy Random (GRAND) algorithm have been shown to asymptotically minimize Q/r as $$r\rightarrow \infty $$ r → ∞ . In this paper, we show that when these algorithms are combined with the First-Fit rule for “taking” empty servers, they asymptotically minimize U/r as well.

Keywords: Queueing networks; Stochastic bin packing; Packing constraints; Ranked servers; Greedy random (GRAND); First-Fit; Local fluid limit; Cloud computing; 90B15; 60K25 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11134-025-09945-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:queues:v:109:y:2025:i:3:d:10.1007_s11134-025-09945-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11134/

DOI: 10.1007/s11134-025-09945-2

Access Statistics for this article

Queueing Systems: Theory and Applications is currently edited by Sergey Foss

More articles in Queueing Systems: Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().