- This event has passed.
Israeli – Dutch Workshop on Applied Probability and Queues
Oct 2, 2017 - Oct 4, 2017
Summary
Israeli-Dutch Workshop on Applied Probability and Queues –
on the occasion of David Perry’s 70th birthday and retirement from the University of Haifa.
Both Israel and The Netherlands have very strong research communities in queueing theory and related topics like performance analysis, inventory theory and insurance risk. This is reflected in, a.o., positions in editorial boards, prizes, awards and research grants. The two above-mentioned research communities are similar in nature: several groups, spread out over a number of universities and research institutes, have considerable interaction, and there is a national queueing seminar.
This two and a half day Israeli-Dutch workshop on Applied Probability and Queues – on the occasion of David Perry’s 70th birthday and retirement from the University of Haifa brings the two communities together, and takes the opportunity to honour David Perry. Without a doubt, David has been one of the main driving forces in establishing and maintaining ties between the two communities. In the past twenty years, he has visited The Netherlands at least once each year, he has hosted numerous Dutch researchers, and he has been involved in a large number of joint research projects.
Organizers
| Ivo Adan | TU Eindhoven |
| Onno Boxma | TU Eindhoven |
| Esther Frostig | University of Haifa |
| Offer Kella | Hebrew University of Jerusalem |
Invited Speakers
| Ivo Adan | TU Eindhoven, Abstract | |
| René Bekker | VU Amsterdam, Abstract | |
| Richard Boucherie | Twente University, Abstract | |
| Esther Frostig | University of Haifa, Abstract | |
| Moshe Haviv | Hebrew University of Jerusalem, Abstract | |
| Royi Jacobovic | Hebrew University of Jerusalem, Abstract | |
| Stella Kapodistria | TU Eindhoven, Abstract | |
| Haya Kaspi | Technion, Abstract | |
| Offer Kella | Hebrew University of Jerusalem, Abstract | |
| Yoav Kerner | Ben-Gurion University of the Negev, Abstract | |
| Igor Kleiner | University of Haifa, Abstract | |
| Ton de Kok | TU Eindhoven, Abstract | |
| Johan v. Leeuwaarden | TU Eindhoven, Abstract | |
| Andreas Löpker | HTW Dresden, Abstract | |
| Michel Mandjes | University of Amsterdam, Abstract | |
| Binyamin Oz | University of Auckland, Abstract | |
| David Perry | University of Haifa and Western Galilee College, Abstract | |
| Ohad Perry | Northwestern University, Abstract | |
| Rachel Ravid | Braude College, Abstract | |
| Liron Ravner | Tel-Aviv University/University of Amsterdam, Abstract | |
| Ad Ridder | VU Amsterdam, Abstract | |
| Nahum Shimkin | Technion, Abstract | |
| Gideon Weiss | University of Haifa, Abstract | |
| Uri Yechiali | Tel-Aviv University, Abstract | |
| Bert Zwart | CWI/TU Eindhoven, Abstract |
Programme
Monday October 2, 2017
|
Tuesday October 3, 2017
|
Wednesday October 4, 2017
|
Abstracts
Ivo Adan
Call center model with heterogeneous reneging customers
We consider a queueing model of a call center with reneging. There are two types of customer: patient and impatient. The patient customers renege at a slower rate than the impatient customers. We study the queueing time process in such a system and derive various performance measures in steady state. (joint work with Vidyadhar Kulkarni (vkulkarn@email.unc.edu) and Brett Hathaway (bretthathaway50@hotmail.con), University of North Carolina, Chapel Hill, NC 27599)
René Bekker
Waiting-time distributions in blended multi-server queues with impatient customers
In many service systems, the service level (SL) is defined in terms of the tail probability of the waiting time. Different customer classes typically have different SL constraints. We first study a call blending system with an urgent (inbound) and best effort (outbound, email, call back) class, where the former has a severely more stringent SL whereas such customers may become impatient. For threshold control, we derive the waiting time distribution using the waiting time process of the first customer in line; in case of infinite patience, this distribution is a mixture of exponentials. Second, if time permits, we identify how to optimally assign servers to customers; we derive the value function for an isolated customer class and then apply one-step policy improvement.
(joint work with Petra Vis, Ger Koole, and Bartlomiej Zaber)
Richard Boucherie
Transient product-form distributions
For (networks of) infinite server queues with Poisson arrival process the transient distribution is a multidimensional Poisson or product-form distribution since all customers independently follow their own trajectory. Surprisingly, the network of infinite server queues is the only Kelly-Whittle network that has Poisson transient distribution. A reaction network is a generalisation of networks of infinite server queues. In a reaction network multiple particles of different types may jointly make a transition with transition rate proportional to the total number of particles of those types present in the system. We explore the boundary of the set of reaction networks that have an exact transient (truncated) multidimensional Poisson distribution for the number of particles of different types. Motivated by the birth-death process, we introduce the notions of transient detailed balance and delay functions, and use these notions to obtain a transient product-form distribution for a coagulation-fragmentation process of polymers with a tree-like structure from that of the pure coagulation process.
(joint work with A.V. den Boer and P.G. Taylor)
Esther Frostig
Dividends in the dual model
We consider the dual risk model with special dividend or tax payments: If an arriving gain finds the surplus above a barrier b or if it would bring the surplus above that level, a certain part of the gain is paid as dividends or taxes.
We obtain expressions for the joint Laplace transform of the time to ruin and the amount of dividends paid until ruin and the expected discounted dividend paid until ruin. We consider the case where the dividend paid from each gain is a general function of the gain. More explicit results are obtained when the dividend is a given percentage of the gain amount.
(joint work with Onno Boxma)
Moshe Haviv
Externalities, optimization and regulation in queues
The academic research on queues deals mostly with waiting. Yet, the externality, namely the added waiting time an arrival inflicts on others, is of no less importance. The talk will deal mostly with how the analysis of the externalities leads to the socially optimal behavior, while solving queueing dilemmas such as whether or not to join a queue, when to arrive to a queue, or from which server to seek service. Customers, being selfish, do not mind the externalities they impose on others. We show how in queues too, internalizing the externalities leads to self regulation. In this setting selecting the service regime is one of the tools for regulation.
(joint with Binyamin Oz, The University of Auckland)
Roy Jacobovic
Real-Time Status Updates with Multiple Correlated Sources
The digital era has opened the door for massive use of variety of portable electronic devices. At any time, these devices update their users about the most recent information including social media, whether conditions, traffic congestions, prices of financial assets, etc. This work discusses the problem that due to limited resources of the communication network, these status updates have to be loaded to the system with respect to some updating policy in order to maintain some adequate level of information freshness. In particular, the setup of two sources that generate updates according to proportional bivariate renewal process is considered. A byproduct of this investigation is the bivariate joint ergodic distribution of the age and excess life processes which is figuered by using a small modification of Smith’s key renewal theorem.
Stella Kapodistria
Performance analysis for random time-limited polling models
We consider a polling model with a service discipline based on the randomly timed gated service: the server resides at a queue for a random amount time and does not switch even if the queue becomes empty but only when the random residing clock expires. Such a service discipline has two advantages, as it enables to: i) keep the frequency of switching at a predetermined level (thus controlling the total cost, if there is a switching cost); ii) balance the time that the server spends in each queue (since, contrary to exhaustive or gated service disciplines, this discipline does not depend on the number of customers present in the various queues). This polling model violates the branching property, thus a direct analytic derivation of the joint queue length distribution turns out to be very difficult. To overcome this issue, we explore the use of (parametric) perturbation. In doing so, we have two options for the choice of the perturbed parameters: either to perturb the service and arrival rates, or to perturb the residing time. In this talk, we discuss both cases and illustrate the advantages and disadvantages of each choice. Furthermore, we compute the marginal workload distribution and prove a decomposition property that permits us to carry out the heavy traffic and/or heavy (light) tail asymptotic analysis.
(joint work with Mayank Saxena, Onno Boxma, and Rudesindo Nunez Queija, accepted for publication in the journal Probability and Mathematical Statistics)
Haya Kaspi
A Skorokhod Map on Measure Valued Paths with Applications to Priority Queues
The Skorokhod map on the half-line has proved to be a useful tool for studying processes with non-negativity constraints. In this work we introduce a measure-valued analog of this map that transforms each element ζ of a certain class of càdlàg paths that take values in the space of signed measures on [0, ∞) to a càdlàg path that takes values in the space of non-negative measures on [0, ∞) in such a way that for each x > 0, the path t 1→ ζt[0, x] is transformed via a Skorokhod map on the half-line, and the regulating functions for different x > 0 are coupled. We establish regularity properties of this map and show that the map provides a convenient tool for studying queueing systems in which tasks are prioritized according to a continuous parameter. Among such well known models are the earliest-deadline-first, both for a single and the many server queueing systems. We show how the map provides a framework within which to form fluid model equations, prove unique- ness of solutions to these equations and establish convergence of scaled state processes to the fluid model. In particular, for these models, we obtain new convergence results in time-inhomogeneous settings, which appear to fall outside the purview of existing approaches and are essential when studying the EDF policy for many servers queues.
(joint work with Rami Atar, Anup Biswas and Kavita Ramanan)
Offer Kella
Infinite server queues with shot noise modulated Poisson arrivals
We consider an infinite server queue to which the input process is a conditional nonhomogeneous Poisson process. The (stochastic) rate function is a generalized shot noise process (a shot noise with respect to a subordinator rather than just a compound Poisson process). Both the steady state and transient behavior of this system can be studied. For example, the mean, variance and autocorrelation of the stationary version have an explicit formula, moreover the joint Laplace-Stieltjes transform of the number in system in two different epochs can be computed. Instead of one infinite server queue, one may also consider a network of such queues or a conditional shot noise process to which the jumps arrive according to the same type of conditional Poisson process.
(joint work in progress with Onno Boxma, Michel Mandjes and Mayank Saxena)
Yoav Kerner
Strategic behavior in an observable retrial queue
We consider a Markovian service system at which a customer who finds the server busy upon arrival is sent to an orbit. While waiting in the orbit, each customer should decide when to inspect the server’s availability. The decision should take into account the number of customers in the orbit and their strategies. We show that the symmetric Nash equilibrium profile is mixed and obtain the sequence of continuous distributions on the positive half real line that possess the symmetric Nash equilibrium. We also obtain the performance measures (e.g., distributions of waiting time in the orbit and the number of customers in the orbit) of the system.
(joint work with Ricky Roet-Green (Rochester))
Igor Kleiner
Decomposition results for single server queues with vacations and impatience
We study general vacation models in the M/M/1 queue under two types of abandonments: bulking and reneging. Decomposition formulas are obtained in terms of combination of improper and proper generating functions. There exists a certain mixture relation between the vacation M/M/1 queue and certain versions of M/M/1-type queues in which the busy periods start with a random number of customers.
(joint work with David Perry and Esther Frostig)
Ton de Kok
The Newsvendor equation as a link between a deterministic perspective and a stochastic perspective on inventory management
In this presentation we discuss the well-known Newsvendor equation. This equation gives the optimal order size in the single period inventory management problem with stochastic demand and linear holding and penalty costs. We show that the Newsvendor equation holds for virtually any inventory problem where the forecast error follows a stationary distribution. This includes classical problems like the stochastic economic lot sizing problem with stochastic dynamic demand, and multi-item multi-echelon inventory problems as extensively studied in both deterministic and stochastic OR literature.
Johan van Leeuwaarden
Clustering and subgraphs in complex networks
Take a complex network with many nodes and edges, and consider c(k), the probability that two neighbors of a degree-k node are neighbors themselves. So take any two coauthors of David Perry and ask whether they themselves have published together. How does this event depend on the number of David’s coauthors k? We investigate how c(k) scales with k and discover a universal curve that consists of three k-ranges where c(k) remains flat, starts declining, and eventually settles on a power law with an exponent that depends on the power law of the degree distribution. We test these results against ten contemporary real-world networks (please approach us if you have your own network data set that needs to be tested) and then generalize our theory to any finite subgraph. (joint work with Clara Stegehuis, Remco van der Hofstad and Guido Janssen)
Andreas Löpker
Time reversal for the M/G/1 workload and related processes
The workload process of the M/G/1 queue, sometimes called unfinished work or virtual waiting time, is a continuous time Markov process measuring the remaining work to be processed at a given time. Under obvious conditions on the arrival rate and the service rate the process is ergodic and has a stationary distribution. At first sight it seems that every conceivable question regarding the workload process has been answered. However, we think that there is no proper account of the time reversal for this process, i.e. of the process that we obtain if we take a stationary M/G/1 workload process X(t) and define the reversed process simply by X*(t)=X(T-t), with T being a fixed point in time. This new Markov process exhibits some perhaps surprising properties. For example the process does not show constant jump rates anymore. Instead a fairly short formula, involving the derivative of the logarithm of the stationary density, connects the arrival rate and the new state dependent jump rate. Among other things we discuss how PASTA (which I encountered first in a queuing course held by David Perry in 1998) relates to the time reversal formulas. We also show how the M/G/1 case inspires one to study time reversals of more general processes.
(joint work with Zbigniew Palmowski)
Michel Mandjes
On a class of reflected AR(1) processes
In this talk I’ll discuss a reflected AR(1) process, i.e. a process (Z_n)_n obeying the recursion Z_{n+1}= max{a Z_n + X_n,0}, with (X_n)_n a sequence of independent and identically distributed (i.i.d.) random variables. I’ll show explicit results for the distribution of Z_n (in terms of transforms) in case X_n can be written as Y_n – B_n, with (B_n)_n being a sequence of independent random variables which are all Exp(λ) distributed, and (Y_n)_n i.i.d.; when |a|<1 the corresponding stationary analysis can be performed, too. Extensions are possible to the case that (B_n)_n are of phase-type. Under a heavy-traffic scaling, I’ll show that the process converges to a reflected Ornstein–Uhlenbeck process; the corresponding steady-state distribution converges to the distribution of a normal random variable conditioned on being positive.
(joint work with Onno Boxma and Josh Reed)
Binyamin Oz
Analyzing nontrivial queueing models using a rate balance principle
The use of a rate balance principle will be demonstrated in analyzing nontrivial state-dependent queueing models; including M/G/1 with state- and last event-dependent arrival rates, M/G/1 with batch arrivals, M/G/1 with vacations, and two versions of M/M/1 with retrials.
(joint work with Ivo Adan and Moshe Haviv)
David Perry
A set of Pollaczek-Khinchine – Type Formulas Applied to Queues, Perishable Inventories, Mountains and Insurance Risk
Using the Level crossings methodology, we review a set of Pollaczek- Khinchine (PK) type formulas.
(joint works with O.J. Boxma and W. Stadje; it includes past applications and new frontiers)
Ohad Perry
Control of Polling Systems with Large Switchover Times
We consider an optimal-control problem of polling systems with large switchover times, when a linear holding cost is incurred on the queues. Specifically, we consider cyclic controls, so that the order at which queues are polled is predetermined, and the control specifies when the server should switch. To study this problem, we employ a fluid approximation that is represented via a Hybrid Dynamical System (HDS), namely, a dynamical system exhibiting both continuous and discrete dynamics. That fluid approximation is achieved as a functional weak law under proper scaling of the switchover times.
We first study a family of stationary Markov controls, which can be translated to a threshold control for the HDS. We characterize the stability region in the control-parameter space, and prove that the exhaustive policy is optimal for the fluid limit among all those threshold controls, when long-run average costs are considered. However, since the stability region is relatively small, we consider a larger family of non-Markov stationary controls, which can be translated into a Proportion Reduction Control (PRC) for the HDS. For those controls, the system is stable for any choice of control parameters, and the exhaustive policy is again proved to be optimal in the long run.(joint work with Jing Dong and Yue Hu.)
Rachel Ravid
A Note on Repair Systems with Exchangeable Items and the Longest Queue Mechanism
A repair facility consisting of one repairman and two arrival streams of failed items, from bases 1 and 2 is considered. The arrival processes are independent Poisson processes, and the repair times are independent and identically exponentially distributed. The item types are exchangeable in the sense that a customer leaves the system with a fixed item, not necessarily the item he has brought. The rule according to which backorders are satisfied by repaired items is the longest queue rule: at the completion of a service (repair), the repaired item is delivered to the base that has the largest number of failed items. We obtain simple expressions for the marginal queue length distributions
and for the probability mass function of the difference between the queue lengths. Finally we derive a recursive expression for the Laplace transform of the customer’s sojourn time in system, given the length of the queue at the arrival time point.
Liron Ravner
An infinite server queueing system with heterogeneous servers and finite capacity
We consider a service system with an infinite number of exponential servers sharing a finite service capacity. The servers are ordered from the fastest to the slowest, and arriving customers join the fastest idle server. A capacity allocation is an infinite decreasing series of service rates. We study the probabilistic properties of this system by considering overflows from sub-systems with a finite number of servers. Several stability measures are suggested and analysed. The tail of the series of service rates that minimizes the average expected delay (service time) is shown to be approximately geometrically decreasing. We use this property in order to approximate the optimal allocation of service rates by constructing an appropriate dynamic program.
(joint work with Refael Hassin, Tel Aviv University)
Ad Ridder
Monte Carlo simulation of aggregate insurance claims using reproducibility
In this paper we consider the problem of computing tail probabilities of the distribution of a random sum of positive random variables. We assume that the individual variables follow a reproducible natural exponential family (NEF) distribution, and that the random number has a NEF counting distribution with a cubic variance function. This specific modelling is supported by data of the aggregated claim distribution of an insurance company. Large tail probabilities are important as they reflect the risk of large losses, however, analytic or numerical expressions are not available. We propose several simulation algorithms which are based on an asymptotic analysis of the distribution of the counting variable and on the reproducibility property of the claim distribution. We conclude by numerical experiments of these algorithms.
(joint work with Shaul Bar-Lev)
Nahum Shimkin
What to Tell Heterogeneous Customers to Make Them Join a Queue
We consider a queueing system, to which customers arrive sequentially. Upon arrival, each customer receives from the system manager some information about his or her expected quality of service (for example, the expected waiting time in the queue, based on the current queue size which is unobservable by the arriving customer), and may then decide whether to balk or join the system. The customers’ preferences, which may be heterogeneous, are captured by a demand curve. The manager is committed to truth telling, but can provide partial information. We ask what information should be provided to arriving customers to maximize the throughput, namely the fraction of customers that choose to join. This question is formulated within the general framework of Bayesian persuasion games. Concrete solutions are derived, whose form depends on the convexity or concavity properties of the demand curve.
Gideon Weiss
FCFS Parallel Service Systems and Matching Models
We consider three parallel service models in which customers of several types are served by several types of servers subject to a bipartite compatibility graph, and the service policy is first come first served. Two of the models have a fixed set of servers. The first is a queueing model in which arriving customers are assigned to the longest idling compatible server if available, or else queue up in a single queue, and servers that become available pick the longest waiting compatible customer, as studied by Adan and Weiss, 2014. The second is a redundancy service model where arriving customers split into copies that queue up at all the compatible servers, and are served in each queue on FCFS basis, and leave the system when the first copy completes service, as studied by Gardner et al., 2016. The third model is a matching queueing model with a random stream of arriving servers. Arriving customers queue in a single queue and arriving servers match with the first compatible customer and leave the system at the moment of arrival, or they leave without a customer. The last model is relevant to organ transplants, to housing assignments, to adoptions and many other situations.
We study the relations between these models, and show that they are closely related to the FCFS infinite bipartite matching model, in which two infinite sequences of customers and servers of several types are matched FCFS according to a bipartite compatibility graph, as studied by Busic et al., 2017.
(joint work with Ivo Adan, TU Eindhoven; Ronda Righter, Berkeley)
Uri Yechiali
Dynamic Allocation of Stochastically-Arriving Flexible Resources to Random Streams of Objects with Application to Kidney Cross-Transplantation
Two distinct random streams of discrete objects flow into a system and queue in two separate lines. In parallel, two distinct types of resources arrive stochastically over time. Upon arrival, each resource unit is matched with a waiting object. One resource type is ‘flexible’ and can be allocated to either one of the object types. However, units of the other, non-flexible, resource type can be allocated only to units of one specific object type. The allocation probabilities are not fixed and may depend on both queue sizes of the two objects. If a resource unit is not allocated immediately, it is lost. The goal is to find an optimal state-dependent probabilistic dynamic allocation policy.
We formulate the system as a two-dimensional Markov process, analyze its probabilistic behavior, and derive its performance measures.
We then apply the model to the problem of organ cross-transplantation and propose a novel measure of system effectiveness, called Expected Value of Transplantation (EVT), based on the histocompatibility between organs and candidates. We further show that it is possible to balance the objectives of achieving equity in candidates’ waiting times (EW) and maximizing EVT by equating the value of EW/EVT between the two groups.
(joint work with Yael Perlman and Amir Elalouf)
Bert Zwart
Sample path large deviations for random walks and Levy processes with Weibullian jumps
We consider sample path large deviations for the superposition of univariate Levy processes and/or random walks with heavy tailed semiexponential increments. In contrast with the light-tailed case, proving a LDP requires the development of a different framework. By combining ideas from both the light-tailed and heavy-tailed worlds, we develop a sample-path large deviation which significantly generalizes a result of Gantert (1998) and is powerful enough to shed light on an open problem (posed by Foss at the Erlang Centennial conference in 2009) on the queue with multiple servers and Weibullian service times.
(joint work with Mihail Bazhba, Chang-Han Rhee (CWI) and Jose Blanchet (Stanford))
Registration
Registration for this event is free, but compulsory: REGISTRATION FORM
Practical Information
● Venue
Eurandom, Mathematics and Computer Science Dept, TU Eindhoven,
De Groene Loper 5, 5612 AE EINDHOVEN, The Netherlands
Eurandom is located on the campus of Eindhoven University of Technology, in the MetaForum building, 4th floor (more about the building). The university is located at 10 minutes walking distance from Eindhoven main railway station (take the exit north side and walk towards the tall building on the right with the sign TU/e).
Accessibility TU/e campus and map.
● Accommodation
For invited speakers, we will take care of accommodation. Other attendees will have to make their own arrangements.
For hotels around the university, please see: Hotels (please note: prices listed are “best available”).
More hotel options can be found on Tourist Information Eindhoven.
● Travel
For those arriving by plane, there is a convenient direct train connection between Amsterdam Schiphol airport and Eindhoven. This trip will take about one and a half hour. For more detailed information, please consult the NS travel information pages.
Many low cost carriers also fly to Eindhoven Airport. There is a bus connection to the Eindhoven central railway station from the airport. (Bus route number 401) For details on departure times consult Public Transport.
The University can be reached easily by car from the highways leading to Eindhoven. For details: Route and map TU/e campus.
● Conference facilities
Conference room, MetaForum Building “MF11 & 12”.
The meeting-room is equipped with a data projector, an overhead projector, a projection screen and a blackboard. Please note that speakers and participants giving an oral presentation are kindly requested to bring their own laptop or their presentation on a memory stick.
● Conference Secretariat
Upon arrival, participants should register with the workshop officer, and collect their name badges. The workshop officer will be present for the duration of the conference, taking care of the administrative aspects and the day-to-day running of the conference: registration, issuing certificates and receipts, etc.
● Cancellation
Should you need to cancel your participation, please contact secretariaat.sto@tue.nl.
● Contact
Chantal Reemers/Petra Rozema, secretariaat.sto@tue.nl