We study web and mobile applications that are used to schedule advance
service, from medical appointments to restaurant reservations. We model them as
online weighted bipartite matching problems with non-stationary arrivals. We
propose new algorithms with performance guarantees for this class of problems.
Specifically, we show that the expected performance of our algorithms is
bounded below by $1-\sqrt{\frac{2}{\pi}}\frac{1}{\sqrt{k}}+O(\frac{1}{k})$
times that of an optimal offline algorithm, which knows all future information
upfront, where $k$ is the minimum capacity of a resource. This is the tightest
known lower bound. This performance analysis holds for any Poisson arrival
process. Our algorithms can also be applied to a number of related problems,
including display ad allocation problems and revenue management problems for
opaque products. We test the empirical performance of our algorithms against
several well-known heuristics by using appointment scheduling data from a major
academic hospital system in New York City. The results show that the algorithms
exhibit the best performance among all the tested policies. In particular, our
algorithms are $21\%$ more effective than the actual scheduling strategy used
in the hospital system according to our performance metric.

本文研究预约服务的 Web 和移动应用程序，针对该类问题提出了带性能保证的新算法，并在纽约市卫生系统的预约数据上进行了测试。