On the dynamic control of matching queues
On the dynamic control of matching queues
复制标题
论匹配队列的动态控制
DOI：
10.1214/13-ssy097
复制
发表时间：
2014
影响因子：
1
通讯作者：
Amy R. Ward
中科院分区：
文献类型：
--
作者：
Itai Gurvich;Amy R. Ward
考虑随机到达匹配队列的最优控制问题。
We consider the optimal control of matching queues with random arrivals.
In this model, items arrive to dedicated queues, and wait to be matched
with items from other (possibly multiple) queues. A match type corresponds
to the set of item classes required for a match. Once a decision has been
made to perform a match, the matching itself is instantaneous and the
matched items 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 items 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 item classes. A non-zero value of the imbalance at time t
means that no control could have matched all the items 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 dedicated
item condition (an analogue of the local traffic condition in bandwidth
sharing networks). We devise a myopic discrete-review matching control
that asymptotically–as the arrival rates become large–achieves the
imbalance-based lower bound.