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

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 dis...

Full description

Saved in:
Bibliographic Details
Published in:Operations research 2017-11, Vol.65 (6), p.1638-1656
Main Authors: Jiang, Ruiwei, Shen, Siqian, Zhang, Yiling
Format: Article
Language:English
Subjects:
Administration
appointment scheduling
convex hulls
distributionally robust optimization
Hospitals
Integer programming
Likelihood functions
Methods
mixed-integer programming
no-show uncertainty
totally unimodularity
valid inequalities
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. The e-companion is available at https://doi.org/10.1287/opre.2017.1656 .
ISSN:0030-364X
1526-5463
DOI:10.1287/opre.2017.1656