On the dynamic control of matching queues

We consider the optimal control of matching queues with dynamically arriving jobs. In this model, jobs arrive to their dedicated queues, and wait to be matched with jobs from other (possibly many) queues. Given that all jobs in a match are present in the system, the matching itself is instantaneous. The objective is to minimize cumulative job holding costs. In the special case of linear (and equal across classes) holding costs, this is equivalent to maximizing the number of matched jobs. The key control question is whether to match myopically, or to keep “inventory ” of jobs, to facilitate more profitable matches in the future. Problems of holding cost minimization have been well-studied in the processing networks literature, and, in the traditional parallel server setting, MaxWeight scheduling policies and variants thereof have been proved to perform well. The heavy-traffic phenomena of state-space collapse and the ensuing reduction of the problem to a one-dimensional Brownian control problem (under appropriate resource pooling conditions), that are the drivers of these well-known results, do not hold in the matching queue setting that we study here. This difference is driven by the fundamentally different notions of capacity underlying the two settings. 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 types. In essence, the imbalance at a time t captures the number of additional jobs required so that some control policy could have matched all the jobs that have arrived by that time (thus leaving the queues empty). The imbalance facilitates the construction of a lower bound that is specified, at each time point, by a solution to a simple constrained optimization problem. Achieving this lower bound requires, in general, “re-shuffling ” past matches. Under a so-called match-pooling condition, we are able to devise a discrete-review matching policy that asymptotically – as the arrival rates becomes large – achieves the imbalance-based lower bound. Our optimality results hold for both stationary and non-stationary arrivals. 1