Optimization Online


Decomposition Algorithm for Optimizing Multi-server Appointment Scheduling with Chance Constraints

Yan Deng (yandeng***at***umich.edu)
Siqian Shen (siqian***at***umich.edu)

Abstract: We schedule appointments with random service durations on multiple servers with operating time limits. We minimize the costs of operating servers and serving appointments, subject to a joint chance constraint limiting the risk of server overtime. Using finite samples of the uncertainty, we formulate the problem as a mixed-integer linear program, and propose a two-stage programming framework where we keep cross-server decisions and constraints at the first stage, so that the remaining problem features a server-wise decomposable structure. The first-stage problem is a variant of the chance-constrained binary packing problem discussed in Song et al. (2014), in which appointments are packed to servers with a probabilistic overtime-free guarantee. The second-stage problem seeks feasible appointment schedules given appointment-to-server assignments. We solve the problems at both stages by methods of coefficient strengthening, bounding, and branch-and-cut with diverse forms of cutting planes. We also investigate variants that consider bounded appointment waiting time, expected overtime/waiting penalty, and use individual chance constraints to limit server overtime. We test instances with diverse problem and sample sizes to demonstrate the computational efficacy of different approaches.

Keywords: stochastic service operations; chance constraints; mixed-integer linear programming; decomposition; cutting-plane algorithms

Category 1: Integer Programming (Cutting Plane Approaches )

Category 2: Stochastic Programming


Download: [PDF]

Entry Submitted: 02/16/2014
Entry Accepted: 02/16/2014
Entry Last Modified: 10/11/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society