Integer programming approaches for appointment scheduling with random no-shows and service durations

Ruiwei Jiang, Siqian Shen, Yiling Zhang

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

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 penalty cost of appointment waiting, server idleness, and overtime into the objective or constraints. Our models flexibly adapt to di erent 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 e cacy of our approaches and to compare the results of various DR models given perfect or ambiguous distributional information.

Original languageEnglish (US)
Pages (from-to)1638-1656
Number of pages19
JournalOperations research
Volume65
Issue number6
DOIs
StatePublished - Nov 1 2017

Bibliographical note

Funding Information:
Funding:The first author is supported in part by the National Science Foundation [Grant CMMI-1555983] and the second and third author are supported in part by the National Science Foundation [Grant CMMI-1433066]. SupplementalMaterial: The e-companion is available at https://doi.org/10.1287/opre.2017.1656.

Keywords

  • Appointment scheduling
  • Convex hulls
  • Distributionally robust optimization
  • Mixed-integer programming
  • No-show uncertainty
  • Totally unimodularity
  • Valid inequalities

Fingerprint Dive into the research topics of 'Integer programming approaches for appointment scheduling with random no-shows and service durations'. Together they form a unique fingerprint.

Cite this