A service system with packing constraints: greedy randomized algorithm achieving sublinear in scale optimality gap

DOI10.1287/STSY.2019.0067MaRDI QIDQ5084484zbMATH OpenOpenAlexFDO

Authors Alexander L. Stolyar, Yuan Zhong

Publication date 24 June 2022

Published in Stochastic Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1511.03241

zbMATH Keywords

cloud computingqueueing networksstochastic bin packinggreedy random (GRAND) algorithmpacking constraintssublinear optimality gap

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30) Stochastic network models in operations research (90B15)

Abstract: A service system with multiple types of arriving customers is considered. There is an infinite number of homogeneous servers. Multiple customers can be placed for simultaneous service into one server, subject to general packing constraints. Each new arriving customer is placed for service immediately, either into an occupied server, as long as packing constraints are not violated, or into an empty server. After service completion, each customer leaves its server and the system. The basic objective is to minimize the number of occupied servers in steady state. We study a Greedy-Random (GRAND) placement (packing) algorithm, introduced in [23]. This is a simple online algorithm, which places each arriving customer uniformly at random into either one of the already occupied servers that can still fit the customer, or one of the so-called zero-servers, which are empty servers designated to be available to new arrivals. In [23], a version of the algorithm, labeled GRAND($aZ$), was considered, where the number of zero servers is $aZ$, with $Z$ being the current total number of customers in the system, and $a>0$ being an algorithm parameter. GRAND($aZ$) was shown in [23] to be asymptotically optimal in the following sense: (a) the steady-state optimality gap grows linearly in the system scale $r$ (the mean total number of customers in service), i.e. as $c(a)r$ for some $c(a)>0$; and (b) $c(a)o0$ as $ao0$. In this paper, we consider the GRAND($Z^p$) algorithm, in which the number of zero-servers is $Z^p$, where $pin(1-1/(8kappa),1)$ is an algorithm parameter, and $(kappa-1)$ is the maximum possible number of customers that a server can fit. We prove the asymptotic optimality of GRAND($Z^p$) in the sense that the steady-state optimality gap is $o(r)$, sublinear in the system scale. This is a stronger form of asymptotic optimality than that of GRAND($aZ$).

Recommendations

• Asymptotic optimality of a greedy randomized algorithm in a large-scale service system with general packing constraints
• Large-scale heterogeneous service systems with general packing constraints
• An infinite server system with general packing constraints
• Asymptotic properties of stochastic greedy bin-packing
• Bandwidth packing

Cites work

• A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
• An infinite server system with general packing constraints
• Asymptotic optimality of a greedy randomized algorithm in a large-scale service system with general packing constraints
• Bandwidth packing
• Dynamic Bin Packing
• Large-scale heterogeneous service systems with general packing constraints
• Martingale proofs of many-server heavy-traffic limits for Markovian queues
• On Multidimensional Packing Problems
• On the Sum-of-Squares algorithm for bin packing
• Probability and Computing
• Stochastic bandwidth packing process: stability conditions via Lyapunov function technique

Cited in

(3)

• An infinite server system with general packing constraints
• Asymptotic optimality of a greedy randomized algorithm in a large-scale service system with general packing constraints
• Large-scale heterogeneous service systems with general packing constraints

This page was built for publication: A service system with packing constraints: greedy randomized algorithm achieving sublinear in scale optimality gap

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5084484)