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

Ruiwei Jiang (), Siqian Shen () and Yiling Zhang ()
Additional contact information
Ruiwei Jiang: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109
Siqian Shen: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109
Yiling Zhang: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109

Operations Research, 2017, vol. 65, issue 6, 1638-1656

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 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 and to compare the results 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 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (27)

Downloads: (external link)
https://doi.org/10.1287/opre.2017.1656 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:65:y:2017:i:6:p:1638-1656

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().