An official website of the United States government
Motivated by a service platform, we study a two-sided network where heterogeneous demand (customers) and heterogeneous supply (workers) arrive randomly over time to get matched. Customers and workers arrive with a randomly sampled patience time (also known as reneging time in the literature) and are lost if forced to wait longer than that time to be matched. The system dynamics depend on the matching policy, which determines when to match a particular customer class with a particular worker class. Matches between classes use the head-of-line customer and worker from each class. Since customer and worker arrival processes can be very general counting processes, and the reneging times can be sampled from any finite mean distribution that is absolutely continuous, the state descriptor must track the age-in-system for every customer and worker waiting in order to be Markovian, as well as the time elapsed since the last arrival for every class. We develop a measure-valued fluid model that approximates the evolution of the discrete-event stochastic matching model and prove its solution is unique under a fixed matching policy. For a sequence of matching models, we establish a tightness result for the associated sequence of fluid-scaled state descriptors and show that any distributional limit point is a fluid model solution almost surely. When arrival rates are constant, we characterize the invariant states of the fluid model solution and show convergence to these invariant states as time becomes large. Finally, again when arrival rates are constant, we establish another tightness result for the sequence of fluid-scaled state descriptors distributed according to a stationary distribution and show that any subsequence converges to an invariant state. As a consequence, the fluid and time limits can be interchanged, which justifies regarding invariant states as first order approximations to stationary distributions.
more »
« less
Large Deviations for the Single-Server Queue and the Reneging Paradox
For the M/M/1+M model at the law-of-large-numbers scale, the long-run reneging count per unit time does not depend on the individual (i.e., per customer) reneging rate. This paradoxical statement has a simple proof. Less obvious is a large deviations analogue of this fact, stated as follows: the decay rate of the probability that the long-run reneging count per unit time is atypically large or atypically small does not depend on the individual reneging rate. In this paper, the sample path large deviations principle for the model is proved and the rate function is computed. Next, large time asymptotics for the reneging rate are studied for the case when the arrival rate exceeds the service rate. The key ingredient is a calculus of variations analysis of the variational problem associated with atypical reneging. A characterization of the aforementioned decay rate, given explicitly in terms of the arrival and service rate parameters of the model, is provided yielding a precise mathematical description of this paradoxical behavior.
more »
« less
- PAR ID:
- 10341417
- Date Published:
- Journal Name:
- Mathematics of Operations Research
- Volume:
- 47
- Issue:
- 1
- ISSN:
- 0364-765X
- Page Range / eLocation ID:
- 232 to 258
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
A source submits status update jobs to a service fa- cility for processing and delivery to a monitor. The status updates belong to service classes with different service requirements. We model the service requirements using a hyperexponential service time model. To avoid class-specific bias in the service process, the system implements an M/G/1/1 blocking queue; new arrivals are discarded if the server is busy. Using an age-of-information (AoI) metric to characterize timeliness of the updates, a stochastic hybrid system (SHS) approach is employed to derive the overall average AoI and the average AoI for each service class. We observe that both the overall AoI and class-specific AoI share a common penalty that is a function of the second moment of the average service time and they differ chiefly because of their different arrival rates. We show that each high-probability service class has an associated age-optimal update arrival rate while low- probability service classes incur an average age that is always decreasing in the update arrival rate.more » « less
-
We consider a long-term average profit–maximizing admission control problem in an M/M/1 queuing system with unknown service and arrival rates. With a fixed reward collected upon service completion and a cost per unit of time enforced on customers waiting in the queue, a dispatcher decides upon arrivals whether to admit the arriving customer or not based on the full history of observations of the queue length of the system. Naor [Naor P (1969) The regulation of queue size by levying tolls. Econometrica 37(1):15–24] shows that, if all the parameters of the model are known, then it is optimal to use a static threshold policy: admit if the queue length is less than a predetermined threshold and otherwise not. We propose a learning-based dispatching algorithm and characterize its regret with respect to optimal dispatch policies for the full-information model of Naor [Naor P (1969) The regulation of queue size by levying tolls. Econometrica 37(1):15–24]. We show that the algorithm achieves an O(1) regret when all optimal thresholds with full information are nonzero and achieves an [Formula: see text] regret for any specified [Formula: see text] in the case that an optimal threshold with full information is 0 (i.e., an optimal policy is to reject all arrivals), where N is the number of arrivals.more » « less
-
The present research examines a pattern-based measure of communications based on Closed Loop Communications (CLC) and non-content verbal metrics to predict Loss of Separation (LOS) in the National Airspace System (NAS). This study analyzes the transcripts from six retired Air Traffic Controllers (ATC) who participated in three simulated trials of various workloads in a TRACON arrival radar simulation. Results indicated a statistically significant model for predicting LOS based on CLC deviations (CLCD), word count in transmission, words per second, and traffic density. However, more research is required to evaluate the significance of each communication variable to predict LOS.more » « less
-
ABSTRACT In this work, we establish and test methods for implementing dynamical friction (DF) for massive black hole pairs that form in large volume cosmological hydrodynamical simulations that include galaxy formation and black hole growth. We verify our models and parameters both for individual black hole dynamics and for the black hole population in cosmological volumes. Using our model of DF from collisionless particles, black holes can effectively sink close to the galaxy centre, provided that the black hole’s dynamical mass is at least twice that of the lowest mass resolution particles in the simulation. Gas drag also plays a role in assisting the black holes’ orbital decay, but it is typically less effective than that from collisionless particles, especially after the first billion years of the black hole’s evolution. DF from gas becomes less than $$1{{\ \rm per\ cent}}$$ of DF from collisionless particles for BH masses >107 M⊙. Using our best DF model, we calculate the merger rate down to z = 1.1 using an Lbox = 35 Mpc h−1 simulation box. We predict ∼2 mergers per year for z > 1.1 peaking at z ∼ 2. These merger rates are within the range obtained in previous work using similar resolution hydrodynamical simulations. We show that the rate is enhanced by factor of ∼2 when DF is taken into account in the simulations compared to the no-DF run. This is due to $${\gt}40{{\ \rm per\ cent}}$$ more black holes reaching the centre of their host halo when DF is added.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1287/moor.2021.1127
