Service platforms must determine rules for matching heterogeneous demand (customers) and supply (workers) that arrive randomly over time and may be lost if forced to wait too long for a match. Our objective is to maximize the cumulative value of matches, minus costs incurred when demand and supply wait. We develop a fluid model, that approximates the evolution of the stochastic model, and captures explicitly the nonlinear dependence between the amount of demand and supply waiting and the distribution of their patience times. The fluid model invariant states approximate the steady-state mean queue-lengths in the stochastic system, and, therefore, can be used to develop an optimization problem whose optimal solution provides matching rates between demand and supply types that are asymptotically optimal (on fluid scale, as demand and supply rates grow large). We propose a discrete review matching policy that asymptotically achieves the optimal matching rates. We further show that when the aforementioned matching optimization problem has an optimal extreme point solution, which occurs when the patience time distributions have increasing hazard rate functions, a state-independent priority policy, that ranks the edges on the bipartite graph connecting demand and supply, is asymptotically optimal. A key insight from this analysis is that the ranking critically depends on the patience time distributions, and may be different for different distributions even if they have the same mean, demonstrating that models assuming, e.g., exponential patience times for tractability, may lack robustness. Finally, we observe that when holding costs are zero, a discrete review policy, that does not require knowledge of inter-arrival and patience time distributions, is asymptotically optimal.
翻译:服务平台必须确定匹配不同需求( 客户) 和供应( 工人) 的规则, 这些规则随时间随机地到达, 如果被迫等待时间过长, 可能会丢失。 我们的目标是最大限度地增加匹配的累积值, 减去供需等待时产生的成本。 我们开发了一个流体模型, 接近随机模式的演进, 并明确捕捉需求量和供应等待量及其耐心时间分布之间的非线性依赖性。 流体模型的状态接近稳定状态平均队列长度, 如果被迫等待时间过长, 可能会丢失。 因此, 我们的目标是将最佳解决方案提供需求类型和供应类型之间的匹配率最大化, 在供需和供需等待时, 我们的目标是: 在流动模式中, 需求与供需量和供需量增长大幅增长时, 我们提出一个不固定的匹配政策。 当上述匹配问题具有最佳的极端点解决方案时, 当耐性时间分布的耐受度增加时, 州际的耐力度、 依赖性优先政策, 也就是在双方端端端端端的供需求, 当我们最终的供需需求, 度分析时, 最优的时, 最优的供需需需, 最优的供需经期分配是最优的时, 最优的供需。