Decomposition algorithms for optimizing multi-server appointment scheduling with chance constraints

作者：Deng Yan; Shen Siqian^*

来源：Mathematical Programming, 2016, 157(1): 245-276.

DOI：10.1007/s10107-016-0990-x

• Chance-constrained programming
• Service scheduling
• Mixed-integer linear programming
• Decomposition
• Branch-and-cut

This paper investigates a problem of scheduling appointments with random service durations on multiple servers with operating time limits. We minimize the cost of operating servers and serving appointments, subject to a joint chance constraint limiting the risk of server running overtime. With finite samples of random service time, we consider a mixed-integer linear programming extended formulation and propose a two-stage decomposition framework with cutting planes. The first stage considers a relaxed master problem as a variant of the chance-constrained binary packing problem discussed in Song et al. (INFORMS J Comput 26(4):735-747, 2014), which packs appointments into servers under chance-constrained server overtime. Given appointment-to-server assignments, the second stage seeks feasible schedules on individual servers. We propose strengthening, bounding, and branch-and-cut methods for computing problems in both stages. Via testing instances with diverse sizes, we compare different decomposition schemes. In particular, we demonstrate the efficacy of our branch-and-cut algorithm that incorporates server-based decomposition for optimizing the problem.

• 出版日期2016-5