Abstract: Abstract The workload of a generalized n-site asymmetric simple inclusion process (ASIP) is investigated. Three models are analyzed. The first model is a serial network for which the steady-state Laplace–Stieltjes transform (LST) of the total workload in the first k sites ( \(k\le n\) ) just after gate openings and at arbitrary epochs is derived. In a special case, the former (just after gate openings) turns out to be an LST of the sum of k independent random variables. The second model is a 2-site ASIP with leakage from the first queue. Gate openings occur at exponentially distributed intervals, and the external input processes to the stations are two independent subordinator Lévy processes. The steady-state joint workload distribution right after gate openings, right before gate openings and at arbitrary epochs is derived. The third model is a shot-noise counterpart of the second model where the workload at the first queue behaves like a shot-noise process. The steady-state total amount of work just before a gate opening turns out to be a sum of two independent random variables. PubDate: 2021-01-02
Abstract: Abstract Understanding the impact of the queue length information on the behavior of customers is nowadays a hot topic for strategic queueing problems. Particularly, it is important to understand how this information impacts the equilibrium behavior and therefore global performance metrics in order to give some recommendations to service providers for optimizing their objective. Recent works are focused on information policies in order to optimize the provider’s profit. In this work, the aim is to maximize the expected social welfare. It is intuitive that the expected social welfare is higher when more information is available to new customers. In some circumstances, and particularly when the queue is overloaded, providing the information up to a particular level of occupancy yields a better expected social welfare compared to always providing queue length information to new customers. This counterintuitive result comes mainly from the strategic behavior of customers at equilibrium when queue length information is not available. After proving that there exists such an optimal information disclosure policy (IDP) for arbitrary arrival and service rates, we go further and study the expected social welfare for the overloaded context in which the arrival rate equals the service rate. Finally, numerical illustrations corroborate our contributions, and moreover, they show that an admission control policy can be also proposed, combined with an IDP, in order to optimize the expected social welfare of the system. PubDate: 2020-12-07
Abstract: Abstract Queues can be seen as a service facility where quality of service (QoS) is an important measure for the performance of the system. In many cases, the queue implements the optimal admission control (either discounted or average) policy in the presence of holding/congestion cost and revenue collected from admitted customers. In this paper, users offer an arrival rate at stationarity that depends on the QoS they experience. We study the interaction between arriving customers and such a queue under two different QoS measures—the asymptotic rate of the customers lost and the fraction of customers lost in the long run. In particular, we investigate the behaviour of equilibrium points and equilibrium sets associated with this interaction and their interpretations in terms of business cycles. We provide sufficient conditions for existence of equilibrium sets for M/M/1 queue. These conditions further help us to identify the relationship among system parameters for which equilibrium sets exist. Next, we consider \(\textit{GI}/M/1\) queues and provide a sufficient condition for existence of multiple optimal revenue policies. We then specialize these results to study the equilibrium sets of (i) a D/M/1 queue and (ii) a queue where the arrival rate is locally continuous. The equilibrium behaviour in the latter case is more interesting as there may be multiple equilibrium points or sets. Motivated by such queues, we introduce a weaker version of monotonicity and investigate the existence of generalized equilibrium sets. PubDate: 2020-12-05
Abstract: Abstract We consider an infinite sequence consisting of agents of several types and goods of several types, with a bipartite compatibility graph between agent and good types. Goods are matched with agents that appear earlier in the sequence using FCFS matching, if such are available, and are lost otherwise. This model may be used for two-sided queueing applications such as ride sharing, Web purchases, organ transplants, and for parallel redundant service queues. For this model, we calculate matching rates and delays. These can be used to obtain waiting times and help with design questions for related service systems. We explore some relations of this model to other FCFS stochastic matching models. PubDate: 2020-12-01
Abstract: Abstract In standard queues, when there are waiting customers, service completions are followed by service commencements. In retrial queues, this is not the case. In such systems, customers try to receive service at a time of their choosing, or the server seeks the next customer for a non-negligible time. In this note, we consider a hybrid model with both a finite standard queue and an orbit. While in the orbit, customers try to join the standard queue in their own time. We assume that the retrial rate is a decision variable, and study both the Nash equilibrium and the socially optimal retrial rates, under a cost model that considers both waiting costs and retrial costs. PubDate: 2020-11-16
Abstract: Abstract This paper studies tight upper bounds for the mean and higher moments of the steady-state waiting time in the GI/GI/1 queue given the first two moments of the interarrival-time and service-time distributions. We apply the theory of Tchebycheff systems to obtain sufficient conditions for classical two-point distributions to yield the extreme values. These distributions are determined by having one mass at 0 or at the upper limit of support. PubDate: 2020-11-09
Abstract: Abstract We consider a discrete-time d-dimensional process \(\{{\varvec{X}}_n\}=\{(X_{1,n},X_{2,n},\ldots ,X_{d,n})\}\) on \({\mathbb {Z}}^d\) with a background process \(\{J_n\}\) on a countable set \(S_0\) , where individual processes \(\{X_{i,n}\},i\in \{1,2,\ldots ,d\},\) are skip free. We assume that the joint process \(\{{\varvec{Y}}_n\}=\{({\varvec{X}}_n,J_n)\}\) is Markovian and that the transition probabilities of the d-dimensional process \(\{{\varvec{X}}_n\}\) vary according to the state of the background process \(\{J_n\}\) . This modulation is assumed to be space homogeneous. We refer to this process as a d-dimensional skip-free Markov-modulated random walk. For \({\varvec{y}}, {\varvec{y}}'\in {\mathbb {Z}}_+^d\times S_0\) , consider the process \(\{{\varvec{Y}}_n\}_{n\ge 0}\) starting from the state \({\varvec{y}}\) and let \({\tilde{q}}_{{\varvec{y}},{\varvec{y}}'}\) be the expected number of visits to the state \({\varvec{y}}'\) before the process leaves the nonnegative area \({\mathbb {Z}}_+^d\times S_0\) for the first time. For \({\varvec{y}}=({\varvec{x}},j)\in {\mathbb {Z}}_+^d\times S_0\) , the measure \(({\tilde{q}}_{{\varvec{y}},{\varvec{y}}'}; {\varvec{y}}'=({\varvec{x}}',j')\in {\mathbb {Z}}_+^d\times S_0)\) is called an occupation measure. Our primary aim is to obtain the asymptotic decay rate of the occupation measure as \({\varvec{x}}'\) goes to infinity in a given direction. We also obtain the convergence domain of the matrix moment generating function of the occupation measure. PubDate: 2020-11-03
Abstract: Abstract We consider an \(M/M/1/{\overline{N}}\) observable non-customer-intensive service queueing system with unknown service rates consisting of strategic impatient customers who make balking decisions and non-strategic patient customers who do not make any decision. In the queueing game amongst the impatient customers, we show that there exists at least one pure threshold strategy equilibrium in the presence of patient customers. As multiple pure threshold strategy equilibria exist in certain cases, we consider the minimal pure threshold strategy equilibrium in our sensitivity analysis. We find that the likelihood ratio of a fast server to a slow server in an empty queue is monotonically decreasing in the proportion of impatient customers and monotonically increasing in the waiting area capacity. Further, we find that the minimal pure threshold strategy equilibrium is non-increasing in the proportion of impatient customers and non-decreasing in the waiting area capacity. We also show that at least one pure threshold strategy equilibrium exists when the waiting area capacity is infinite. PubDate: 2020-10-14
Abstract: Abstract In recent years, a number of models involving different compatibilities between jobs and servers in queueing systems, or between agents and resources in matching systems, have been studied, and, under Markov assumptions and appropriate stability conditions, the stationary distributions have been shown to have product forms. We survey these results and show how, under an appropriate detailed description of the state, many existing product-form results are corollaries of similar results for the Order Independent queue. We also discuss how to use the product-form results to determine distributions for steady-state response times. PubDate: 2020-10-14
Abstract: Abstract Service systems often feature multiple classes of customers with different service needs and multiple pools of servers with different skillsets. How to efficiently match customers of different classes with servers of different skillsets is of great importance to the management of these systems. In this survey, we review works on skill-based routing in queues. We first summarize key insights on routing/scheduling policies developed in the literature. We then discuss complications brought by modern service operations management problems, particularly healthcare systems. These complications stimulate a growing body of literature on new modeling and analysis tools. Lastly, we provide additional numerical experiments to highlight the complex nature of a routing problem motivated from hospital patient-flow management, and provide some useful intuition to develop good skill-based routing policies in practice. Our goal is to provide a brief overview of the skill-based routing research landscape and to help generate interesting research ideas. PubDate: 2020-10-04
Abstract: Abstract Stochastic networks with complex structures are key modelling tools for many important applications. In this paper, we consider a specific type of network: retrial queueing systems with priority. This type of queueing system is important in various applications, including telecommunication and computer management networks with big data. The system considered here receives two types of customers, of which Type-1 customers (in a queue) have non-pre-emptive priority to receive service over Type-2 customers (in an orbit). For this type of system, we propose an exhaustive version of the stochastic decomposition approach, which is one of the main contributions made in this paper, for the purpose of studying asymptotic behaviour of the tail probability of the number of customers in the steady state for this retrial queue with two types of customers. Under the assumption that the service times of Type-1 customers have a regularly varying tail and the service times of Type-2 customers have a tail lighter than Type-1 customers, we obtain tail asymptotic properties for the numbers of customers in the queue and in the orbit, respectively, conditioning on the server’s status, in terms of the exhaustive stochastic decomposition results. These tail asymptotic results are new, which is another main contribution made in this paper. Tail asymptotic properties are very important, not only on their own merits but also often as key tools for approximating performance metrics and constructing numerical algorithms. PubDate: 2020-09-29
Abstract: Abstract This paper studies an extension of Naor’s model in which there is parameter uncertainty. In particular, the arrival rate is known, to customers and system managers, only through its distribution. For the observable case, the relationship between the optimal individual threshold and the thresholds for a social optimizer or revenue maximizer does not change from the classical model with a known arrival rate. However, in the unobservable case, it is shown that the decisions of the social optimizer and revenue maximizer no longer coincide. Furthermore, in the unobservable case with arrival rate uncertainty, the social optimizer induces a lower expected arrival rate than the revenue maximizer. This stands in contrast to the observable case, in which the social optimizer prefers a more congested system. PubDate: 2020-09-24
Abstract: Abstract This paper considers an unobservable two-site tandem queueing system attended by an alternating server. We study the strategic customer behaviour under two threshold-based operating policies, applied by a profit-maximizing server, while customers’ strategic behaviour and server’s switching costs are taken into account. Under the Exact-N policy, in each cycle the server first completes service of N customers in the first stage ( \(Q_1\) ), then switches to the second stage ( \(Q_2\) ) and then serves those N customers before switching back to \(Q_1\) to start a new cycle. This policy leads to a mixture of Follow-the-Crowd and Avoid-the-Crowd customer behaviour. In contrast, under the N-Limited policy, the server switches from \(Q_1\) to \(Q_2\) also when the first queue is emptied, making this regime work-conserving and leading only to Avoid-the-Crowd behaviour. Performance measures are obtained using matrix geometric methods for both policies and any threshold N, while for sequential service ( \(N=1\) ) explicit expressions are derived. It is shown that the system’s stability condition is independent of N, and of the switching policy. Optimal performances in equilibrium, under each of these switching policies, are analysed and compared through a numerical study. PubDate: 2020-09-09
Abstract: Abstract We study a system of taxis and customers with Poisson arrivals and exponential patience times. We model a delayed matching process between taxis and customers using a matching rate \(\theta \) as follows: if there are i taxis and j customers in the system, the next pairing will occur after an exponential amount of time with rate \(\theta i^{\delta _1}j^{\delta _2}\) ( \(\delta _1, \delta _2 \in (0,+\infty \) )). We formulate the system as a CTMC and study the fluid and diffusion approximations for this system, which involve the solutions to a system of differential equations. We consider two approximation methods: Kurtz’s method (KA) derived from Kurtz’s results (Kurtz in J Appl Probab 7(1):49–58, 1970; Kurtz in J Appl Probab 8(2):344–356, 1971) and Gaussian approximation (GA) that works for the case \(\delta _1 = \delta _2 = 1\) (we call this the bilinear case) based on the infinitesimal analysis of the CTMC. We compare their performance numerically with simulations and conclude that GA performs better than KA in the bilinear case. We next formulate an optimal control problem to maximize the total net revenue over a fixed time horizon T by controlling the arrival rate of taxis. We solve the optimal control problem numerically and compare its performance to the real system. We also use Markov decision processes to compute the optimal policy that maximizes the long-run revenue rate. We finally propose a heuristic control policy (HPKA) and show that its expected regret is a bounded function of T. We also propose a version of this policy (HPMDP) that can actually be implemented in the real queueing system and study its performance numerically. PubDate: 2020-08-10
Abstract: Abstract In this note, we prove that the speed of convergence of the workload of a Lévy-driven queue to the quasi-stationary distribution is of order 1/t. We identify also the Laplace transform of the measure giving this speed and provide some examples. PubDate: 2020-08-10
Abstract: Abstract We analyze a discrete-time two-class queueing system with a single server which is alternately available for only one customer class. The server is each time allocated to a customer class for a geometrically distributed amount of time. Service times of the customers are deterministically equal to 1 time slot each. During each time slot, both classes can have at most one arrival. The bivariate process of the number of customers of both classes can be considered as a two-dimensional nearest-neighbor random walk. The generating function of this random walk has to be obtained from a functional equation. This type of functional equation is known to be difficult to solve. In this paper, we obtain closed-form expressions for the joint probability distribution for the number of customers of both classes, in steady state. PubDate: 2020-08-01
Abstract: Abstract Many service systems use technology to notify customers about their expected waiting times or queue lengths via delay announcements. However, in many cases, either the information might be delayed or customers might require time to travel to the queue of their choice, thus causing a lag in information. In this paper, we construct a neutral delay differential equation model for the queue length process and explore the use of velocity information in our delay announcement. Our results illustrate that using velocity information can have either a beneficial or detrimental impact on the system. Thus, it is important to understand how much velocity information a manager should use. In some parameter settings, we show that velocity information can eliminate oscillations created by delays in information. We derive a fixed point equation for determining the optimal amount of velocity information that should be used and find closed-form upper and lower bounds on its value. When the oscillations cannot be eliminated altogether, we identify the amount of velocity information that minimizes the amplitude of the oscillations. However, we also find that using too much velocity information can create oscillations in the queue lengths that would otherwise be stable. PubDate: 2020-06-16
Abstract: Abstract Bulk-service multi-server queues with heterogeneous server capacity and thresholds are commonly seen in several situations such as passenger transport or package delivery services. In this paper, we develop a novel decomposition-based solution approach for such queues using arguments from renewal theory. We then obtain the distribution of the waiting time measure for multi-type server systems. We also obtain other useful performance measures such as utilization, expected throughput time, and expected queue lengths. PubDate: 2020-06-11
Hybrid journal (It can contain Open Access articles)
