You are here

C3 Guest Lecture Series

Stability in dynamic bipartite matching models
Ana Bušić
Ana Bušić received her bachelor’s degree from the University of Zagreb. She obtained her master’s degree in Mathematics from the University of Versailles in 2003, and her Ph.D. degree in Computer Science from the University of Versailles in 2007. Since 2009, she is a research scientist at INRIA Rocquencourt and a member of Computer Science Department of Ecole Normale Supérieure, in the research group TREC. Her research interests include Markov chains, simulation, and performance evaluation of communication networks.
Matching models arise in many applications, such as healthcare, transportation, and energy. We consider a bipartite matching queueing model, where customers and servers play symmetrical roles. Time is discrete and at each time step, one customer and one server arrive in the system. Also, at each time step, pairs of matched customer and server, if they exist, depart from the system. Authorized matchings between customer/server classes are given by a fixed bipartite graph. A matching policy is chosen, which decides how to match when there are several possibilities. Customers/servers that cannot be matched are stored in a buffer. The evolution of the model can be described by a discrete time Markov chain. We study its stability under various admissible matching policies including: ML (Match the Longest), MS (Match the Shortest), FIFO (match the oldest), priorities. There exist natural necessary conditions for stability (independent of the matching policy) defining the maximal possible stability region. For some bipartite graphs, we prove that the stability region is indeed maximal for any admissible matching policy. For the ML policy, we prove that the stability region is maximal for any bipartite graph. For the MS and priority policies, we exhibit a bipartite graph with a non-maximal stability region.
December 5, 2012
1:00 pm
234 Larsen

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer