סמינר מחלקתי - לירון רבנר

Abstract:

We consider the problem of scheduling arrivals to a deterministic processor sharing system, i.e. all users in the system at any given time are served simultaneously. In contrast to classical processor sharing congestion models, the processing slowdown is linear with respect to the number of users in the system at any time. This assumption is appropriate when customers do not really share service, but rather slow each other down. For example, this is the case in the transportation network of a business district or when shopping in a big store. For each user there is an ideal departure time (due date). The centralized scheduling goal is then to select arrival times so as to minimize the total penalty due to deviations from ideal times weighted with sojourn times. Due to the dynamics of the system, the scheduling objective function is non-convex even if the individual penalties are convex. We leverage the structure of the problem to derive an exact algorithm for finding the global minimum for a small number of users, and a heuristic algorithm guaranteed to converge to a local minimum for a larger number of users. We further analyse a decentralized variation of the problem as a game in which the users select their own arrival time with the goal of minimizing their individual cost.

Bio :

Liron Ravner is a post-doc in the Department of Operations Research and Statistics at Tel Aviv University, working with Rafi Hassin. Before that Liron was a Ph.D. student in the Department of Statistics at the Hebrew University of Jerusalem, under the supervision of Moshe Haviv. His research interests are in Queueing Theory, Game Theory and Applied Probability. In particular, his work has so far focused on the mathematical modelling of strategic behaviour of customers arriving at stochastic queues.

Joint work with: Yoni Nazarathy, University of Queensland,  Moshe Haviv,  Hebrew University of Jerusalem and  Hai Vu, Swinburne University of Technology