期刊
MATHEMATICAL PROGRAMMING
卷 157, 期 1, 页码 245-276出版社
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-016-0990-x
关键词
Chance-constrained programming; Service scheduling; Mixed-integer linear programming; Decomposition; Branch-and-cut
类别
资金
- National Science Foundation [CMMI-1433066]
- University of Michigan
- Div Of Civil, Mechanical, & Manufact Inn
- Directorate For Engineering [1433066] Funding Source: National Science Foundation
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据