A strategic timing of arrivals to a linear slowdown processor sharing system

DOI10.1016/J.EJOR.2016.05.033zbMATH Open1346.68044arXiv1508.03420OpenAlexW2248258572MaRDI QIDQ323554FDOQ323554

Liron Ravner, Moshe Haviv, Hai L. Vu

Publication date: 7 October 2016

Published in: European Journal of Operational Research (Search for Journal in Brave)

Abstract: We consider a discrete population of users with homogeneous service demand who need to decide when to arrive to a system in which the service rate deteriorates linearly with the number of users in the system. The users have heterogeneous desired departure times from the system, and their goal is to minimize a weighted sum of the travel time and square deviation from the desired departure times. Users join the system sequentially, according to the order of their desired departure times. We model this scenario as a non-cooperative game in which each user selects his actual arrival time. We present explicit equilibria solutions for a two-user example, namely the subgame perfect and Nash equilibria and show that multiple equilibria may exist. We further explain why a general solution for any number of users is computationally challenging. The difficulty lies in the fact that the objective functions are piecewise convex, i.e., non-smooth and non-convex. As a result, the minimization of the costs relies on checking all arrival and departure order permutations, which is exponentially large with respect to the population size. Instead we propose an iterated best-response algorithm which can be efficiently studied numerically. Finally, we compare the equilibrium arrival profiles to a socially optimal solution and discuss the implications.

Full work available at URL: https://arxiv.org/abs/1508.03420

zbMATH Keywords

arrival time gamelinear slowdownpiecewise-convex programmingprocessor sharingsequential timing game

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Combinatorial optimization (90C27) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Games of timing (91A55)

Cites Work

• Potential games
• Equilibrium Points in Nonzero-Sum n-Person Submodular Games
• ?/M/1: On the equilibrium distribution of customer arrivals
• Equilibrium arrival times to a queue with order penalties
• The concert queueing game: strategic arrivals with waiting and tardiness costs
• Strategic timing of arrivals to a finite queue multi-server loss system
• Scheduling for a processor sharing system with linear slowdown
• Fluid dynamics models and their applications in transportation and pricing
• The Concert Queueing Game: Fluid Regime with Random Order Service

Cited In (6)

• On the scheduling of operations in a chat contact center
• Choosing a batch to be processed
• Security screening queues with impatient applicants: a new model with a case study
• Individual equilibrium and learning in processor sharing systems
• Stable strategies for processor sharing systems
• Scheduling for a processor sharing system with linear slowdown

This page was built for publication: A strategic timing of arrivals to a linear slowdown processor sharing system

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q323554)