Abstract: The appointment scheduling problem (ASP) studies how to manage patient arrivals to a healthcare system to improve system performance. An important challenge occurs when some patients may not show up for an appointment. Although the ASP is well studied in the literature, the vast majority of the existing work does not consider the well-observed phenomenon that patient no-show is influenced by the appointment time, the usual decision variable in the ASP. This paper studies the ASP with random service time (exogenous uncertainty) with known distribution and patient decision-dependent no-show behavior (endogenous uncertainty). This problem belongs to the class of stochastic optimization with decision-dependent uncertainties. Such problems are notoriously difficult as they are typically nonconvex. We propose a stochastic projected gradient path (SPGP) method to solve the problem, which requires the development of a gradient estimator of the objective function-a nontrivial task, as the literature on gradient-based optimization algorithms for problems with decision-dependent uncertainty is very scarce and unsuitable for our model. Our method can solve the ASP problem under arbitrarily smooth show-up probability functions. We present solutions under different patterns of no-show behavior and demonstrate that breaking the assumption of constant show-up probability substantially changes the scheduling solutions. We conduct numerical experiments in a variety of settings to compare our results with those obtained with a distributionally robust optimization method developed in the literature. The cost reduction obtained with our method, which we call the value of distribution information, can be interpreted as how much the system performance can be improved by knowing the distribution of the service times, compared to not knowing it. We observe that the value of distribution information is up to 31% of the baseline cost, and that such value is higher when the system is crowded or/and the waiting time cost is relatively high.
Summary of Contribution: This paper studies an appointment scheduling problem under time-dependent patient no-show behavior, a situation commonly observed in practice. The problem belongs to the class of stochastic optimization problems with decision-dependent uncertainties in the operations research literature. Such problems are notoriously difficult to solve as a result of the lack of convexity, and the present case requires different techniques because of the presence of continuous distributions for the service times. A stochastic projected gradient path method, which includes the development of specialized techniques to estimate the gradient of the objective function, is proposed to solve the problem. For problems with a similar structure, the algorithm can be applied once the gradient estimator of the objective function is obtained. Extensive numerical studies are presented to demonstrate the quality of the solutions, the importance of modeling time-dependent no-shows in appointment scheduling, and the value of using distribution information about the service times.