| Title: |
Decomposition algorithms for optimizing multi-server appointment scheduling with chance constraints. |
| Authors: |
Deng, Yan1 yandeng@umich.edu, Shen, Siqian1 siqian@umich.edu |
| Source: |
Mathematical Programming. May2016, Vol. 157 Issue 1, p245-276. 32p. |
| Subject Terms: |
*Algorithms, Algorithmic randomness, Foundations of arithmetic, Recursion theory, Recursive functions |
| Abstract: |
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, ), 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. [ABSTRACT FROM AUTHOR] |
|
Copyright of Mathematical Programming is the property of Springer Nature and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Business Source Complete |
