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

DOI10.1016/J.EJOR.2016.05.033MaRDI QIDQ323554zbMATHOpenAlexFDO

Authors Liron Ravner, Moshe Haviv, Hai L. Vu

Publication date 7 October 2016

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

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)

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.

Recommendations

• Strategic timing of arrivals to a finite queue multi-server loss system
• The concert queueing game: strategic arrivals with waiting and tardiness costs
• The concert queueing game: to wait or to be late
• Strategic arrivals into queueing networks: the network concert queueing game
• Equilibrium arrival times to queues with general service times and non-linear utility functions

Cites work

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

Cited in

(7)

• Choosing a batch to be processed
• Scheduling for a processor sharing system with linear slowdown
• Stable strategies for processor sharing systems
• Security screening queues with impatient applicants: a new model with a case study
• Individual equilibrium and learning in processor sharing systems
• Discrete-time strategic job arrivals to a single machine with waiting and lateness penalties
• On the scheduling of operations in a chat contact center

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)