Optimization Online


Integer Programming Approaches for Appointment Scheduling with Random No-shows and Service Durations

Ruiwei Jiang (ruiwei***at***umich.edu)
Siqian Shen (siqian***at***umich.edu)
Yiling Zhang (zyiling***at***umich.edu)

Abstract: We consider a single-server scheduling problem given a fixed sequence of appointment arrivals with random no-shows and service durations. The probability distribution of the uncertain parameters is assumed to be ambiguous and only the support and first moments are known. We formulate a class of distributionally robust (DR) optimization models that incorporate the worst-case expectation/conditional Value-at-Risk (CVaR) penalty cost of appointment waiting, server idleness, and overtime as the objective or constraints. Our models flexibly adapt to different prior beliefs of no-show uncertainty. We obtain exact mixed-integer nonlinear programming reformulations, and derive valid inequalities to strengthen the reformulations that are solved by decomposition algorithms. In particular, we derive convex hulls for special cases of no-show beliefs, yielding polynomial-sized linear programming models for the least and the most conservative supports of no shows. We test various instances to demonstrate the computational efficacy of our approaches, the results and solution performance of various DR models given perfect or ambiguous distributional information.

Keywords: appointment scheduling; no-show uncertainty; distributionally robust optimization; mixed-integer programming; valid inequalities; totally unimodularity; convex hulls

Category 1: Stochastic Programming

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Applications -- OR and Management Sciences (Scheduling )


Download: [PDF]

Entry Submitted: 08/31/2015
Entry Accepted: 08/31/2015
Entry Last Modified: 09/30/2016

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