Stability of Parallel Server Systems

Pascal Moyal () and Ohad Perry ()
Additional contact information
Pascal Moyal: Institut Elie Cartan de Lorraine, Universite de Lorraine, 54 000 Nancy, France
Ohad Perry: Department of Industrial Engineering and Management Science, Northwestern University, Evanston, Illinois 60208

Operations Research, 2022, vol. 70, issue 4, 2456-2476

Abstract: The fundamental problem in the study of parallel-server systems is that of finding and analyzing routing policies of arriving jobs to the servers that efficiently balance the load on the servers. The most well-studied policies are (in decreasing order of efficiency) join the shortest workload (JSW), which assigns arrivals to the server with the least workload; join the shortest queue (JSQ), which assigns arrivals to the smallest queue; the power-of- d (PW( d )), which assigns arrivals to the shortest among d ≥ 1 queues that are sampled from the total of s queues uniformly at random; and uniform routing, under which arrivals are routed to one of the s queues uniformly at random. In this paper we study the stability problem of parallel-server systems, assuming that routing errors may occur, so that arrivals may be routed to the wrong queue (not the smallest among the relevant queues) with a positive probability. We treat this routing mechanism as a probabilistic routing policy, named a p -allocation policy, that generalizes the PW( d ) policy, and thus also the JSQ and uniform routing, where p is an s -dimensional vector whose components are the routing probabilities. Our goal is to study the (in)stability problem of the system under this routing mechanism, and under its “nonidling” version, which assigns new arrivals to an idle server, if such a server is available, and otherwise routes according to the p -allocation rule. We characterize a sufficient condition for stability, and prove that the stability region, as a function of the system’s primitives and p , is in general smaller than the set { ρ < 1 } . Our analyses build on representing the queue process as a continuous-time Markov chain in an ordered space of s -dimensional real-valued vectors, and using a generalized form of the Schur-convex order.

Keywords: Stochastic Models; parallel servers; instability of subcritical systems (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2125 (application/pdf)

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:inm:oropre:v:70:y:2022:i:4:p:2456-2476

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().