Take Action

Home | Faculty & Research Overview | Research

Research Details

On the Dynamic Control of Matching Queues, Stochastic Systems


We consider the optimal control of matching queues with dynamically arriving jobs. In this model, jobs arrive to dedicated queues, and wait to be matched with jobs from other (possibly multiple) queues. A match type corresponds to the set of job-classes required for a match. Once a decision has been made to perform a match, the matching itself is instantaneous and the matched jobs depart from the system. We consider the problem of minimizing finite-horizon cumulative holding costs. The controller must decide which matchings to execute given multiple options. In principle, the controller may choose to wait until some "inventory" of jobs builds up to facilitate more profitable matches in the future. We introduce a multi-dimensional imbalance process, that at each time t , is given by a linear function of the cumulative arrivals to each of the job classes. A non-zero value of the imbalance at time t means that no control could have matched all the jobs that arrived by time t . A lower bound based on the imbalance process can be specified, at each time point, by a solution to an optimization problem with linear constraints. While not achievable in general, this lower bound can be asymptotically approached under a local traffic condition. We devise a myopic discrete-review matching control that asymptotically - as the arrival rates become large - achieves the imbalance-based lower bound.




Itai Gurvich, Amy Ward

Date Published



Gurvich, Itai, and Amy Ward. 2013. On the Dynamic Control of Matching Queues. Stochastic Systems.


Explore leading research and ideas

Find articles, podcast episodes, and videos that spark ideas in lifelong learners, and inspire those looking to advance in their careers.
learn more


Review Courses & Schedules

Access information about specific courses and their schedules by viewing the interactive course scheduler tool.


Discover the path to your goals

Whether you choose our Full-Time, Part-Time or Executive MBA program, you’ll enjoy the same unparalleled education, exceptional faculty and distinctive culture.
learn more