本文研究时延最小花费在线匹配(MPMD)问题，其中请求以在线的形式到来，算法需要实时地进行决策，使得请求在尽量短的时间内两两匹配。不同类别的请求匹配会产生空间开销，延迟匹配会产生时间开销。问题的目标是最小化空间开销和时间开销的总和。目前所有对于MPMD问题的研究都是假设时间开销是随时延线性增长的，但线性MPMD模型不足以涵盖对延迟极为敏感的请求匹配场景。本文研究了请求的时间开销随时延呈凸函数增长的MPMD问题，模拟了请求急需匹配的应用场景，如游戏玩家匹配，器官移植等。原有解决线性MPMD问题的算法可以保持某个请求等待很久，而不会使总时间开销增长太快。这种策略在凸函数时间代价的设置之下不再具有竞争性。本文针对凸函数MPMD问题设计了新的确定性算法。对于任意k-顶点均匀度量空间，该算法可以在一大类凸函数上获得O(k)的竞争比。此外，本文证明了均匀度量空间上的凸函数MPMD问题确定性算法的下界是Ω（k），从而说明我们给出的算法是最优的，这也说明了线性MPMD问题与凸函数MPMD问题的潜在不同。除此之外，我们还证明了针对不经意对手，均匀度量空间上的凸函数MPMD问题随机算法的下界是Ω(log k)。