The Contextual Appointment Scheduling Problem

ASP studies with uncertain service times often assume full distributional information about the job durations (i.e. full joint distribution of the jobs is known, or jobs are independent and marginal distributions are known). Excellent surveys of ASP models can be found in(?; ?).

Sample Average Approximation (SAA) is a common method used to solve the stochastic ASP. SAA approach can be computationally intensive, and require knowledge of the joint distribution of the job service durations (?).

Further, when the joint distribution of the uncertain parameters is not known to us, other types of modeling is proposed in the literature. ? ? proposed Robust Optimization (RO) for the ASP where job durations lie within interval uncertainty sets. ? ? proposed Distibutionally Robust Optimization (DRO) for ASP assuming partial distributional information of the uncertain parameters such as support and moments are known. The appointments are made to minimize the worst-case expected objective value among all possible distributions with the specified support and moments information. Finally, ? ? proposed using DRO with moment uncertainty set and derived an approximate semidefinite programming model.

Solving many real world problems requires two main steps of estimation (prediction) and optimization (prescription). Due to the complex nature of each step, researchers typically solve these two steps separately. The major issue with this approach is that the optimization problem is blind to the prediction process and its sensitivity to over/under estimation of the parameter. In contrast to the Separated Estimation and Optimization (SEO) approach, another framework is proposed by ? ?. They referred to this method as ”prescriptive analytics”. They combined the ideas from Machine Learning (ML) and Operations Research and Management Science (OR/MS) in developing a framework for using auxiliary data to prescribe optimal decisions.

A general framework for the Integrated Estimation and Optimization (IEO) approach was proposed later by ? ?. They called their framework ”Smart Predict, then Optimize” (SPO). Training a model with respect to the SPO loss is computationally challenging, and therefore they also proposed a surrogate loss function, called the SPO+ loss, which upper bounds the SPO loss, has desirable convexity properties, and is statistically consistent under mild conditions. Minimizing an application-specific loss function is refereed to as ”training with direct loss” (?) or task-based model learning (?) in the ML literature. In this paper, we proposed using DNN to solve the feature-based ASP.

We consider $n$ jobs arriving at a single server given a predetermined sequence $1,2,3,\dots,n$. Job $i$ has a random service duration ${p_{i}}$. The planner determines time allowances $S_{i}\geq 0$ for each job $i$. If job $i$ cannot be started at its planned start time due to a delay of completion of the previous job, a waiting time cost will be incurred per unit time of delay. Let $W_{i}$ denote the waiting time of the job $i$. On the other hand, if job $i-1$ completed sooner than its planned start time, an idling time cost will be incurred per time. Let $I_{i}$ denote the idling time of the server between job $i-1$ and job $i$. The goal is to optimize the decisions of scheduling for arrival times of each job, or equivalently, assigning time intervals between each two jobs.

The random job durations $\bm{p}$ follow a joint probability distribution $F(\bm{p})$. For any job $i$, the support of ${p_{i}}$ is independent from other jobs and is denoted by $\mathds{D}_{i}$; therefore, $\mathds{D}=\mathds{D}_{1}\times\dots\times\mathds{D}_{n}$. Given time allowances $\bm{S}\in\bm{\Re^{+}}$ and a realization of the random service times, denoted by $\bm{p}$, the waiting and idling times should satisfy the following constraints:

Moreover, $W_{i},I_{i}\in\Re^{+}$. It is also worth noting that because of the punctually arrival assumption $W_{1}=I_{1}=0$. Assuming linear costs for waiting and idling, the total waiting and idling cost is denoted by

where $c^{\mathcal{W}}$ and $c^{\mathcal{I}}$ (non-negative) represent the costs of waiting and idling, respectively.

In the previous section, we reviewed classic approaches to model ASP. In a realistic situation, the classic models are too simplistic to represent many real scenarios because one can collect data on exogenous information about the jobs’ characteristics as well as the job durations. In other words, the planner has access to a richer data set for decision making. Further, most of the models fail to consider context in estimating the job durations. The classic models obtain an estimate of the probability distribution and solve the optimization problem separately. The approximation process of the probability distributions involves errors, especially when historical data is scarce or when durations are not i.i.d.

In practice, the job durations depend on many observable features (equivalently, covariates or context). For example, in patient appointment scheduling, the characteristics of the patients can be used as features. If the jobs are flight arrivals, then the attributes of the flights can be used (i.e. day, month, season, weather, origin and destination airports).

Assuming the planner schedules $n$ jobs with $m$ features at each time period and s/he has access to historical data for $T$ periods, we have $\{(\bm{x}^{t},\bm{p}^{t})\}_{t=1}^{T}$ where $\bm{x}^{t}=(x_{1}^{t},\dots,x_{n}^{t})$ and $\bm{p}^{t}=(p_{1}^{t},\dots,p_{n}^{t})$. For notation brevity, we denote all the $m$ features for the job $i$ at time $t$ with $x_{i}^{t},1\leq i\leq n$, i.e. $x_{i}^{t}=(x_{i1}^{t},\dots,x_{im}^{t})$.

In the feature-based ASP model, the features are available to the planner prior to the decision making process. In other words, the decision maker optimizes the conditional expected cost function:

where the scheduling decisions $\bm{S}(.)$ are now functions mapping the feature space $\mathcal{X}\subset\Re^{m}$ to the positive real numbers ($\Re^{+}$) and the expected waiting and idling costs that we minimize is now conditional on the feature vector $\bm{x}^{t}\in\mathcal{X}$.

The planner needs to be able to solve the described problem in equation (7) efficiently given the observation $\bm{x}^{t}$. The main issue in this model is that the job durations might be correlated and allowance decisions have to be made sequentially. For example, when the first job is being processed on the server, we do not know whether the server will be idle until the next job arrives or the next job will be delayed. The uncertainty about the starting time of each job propagates through the sample of $n$ jobs at each time unit $t$. The planner needs to know the actual realization of the previous job and its starting time to optimally plan for the next one.

For the classic ASP models, we propose using SAA for the stochastic optimization models. This approach is applicable when the joint distribution of the job durations is known or when we have enough historical data. In the former case, we sample from the distribution and generate scenarios. In the latter, we treat each historical realization as a scenario. If limited distributional information is available, we propose using a cutting-plane approach to solve the DRO models.

In the feature-based ASP models, we incorporate the features to predict the job durations. This can be done in two settings: (1) SEO: Separate Estimation and Optimization, (2) IEO: Integrate Estimation and Optimization.

Inspired by medical appointment dataset (?) on Kaggle, we generated a random dataset with $4$ categorical covariates (gender, day of month, time of day, intensity) and the response variable shows the duration of the appointment (non-negative). We assume the ground truth distribution of the duration times can be from multiple different distributions, but in all of them mean and standard deviation is fixed:

Let us consider $4$ possible distributions for the response in here:

Later, we add some noise to the labels from $\mathcal{U}(-1,1)$. The appointment durations are not i.i.d, however, i.i.d is a conventional assumption for the inputs of the classic models in stochastic optimization.

To make sure predictions are non-negative, we scale the appoinment durations between $0$ and $1$. This transformation is necessary since our predictions are outputs of a sigmoid function. Since the covariates are categorical, we consider One-Hot encoding transformations of them for the training.

The Maximum Likelihood Estimates (MLEs) of the mean and standard deviation parameters from the generated data are computed and used in this section. From the dataset, we have estimated $\hat{\mu}_{MLE}=5.9254$, and $\hat{\sigma}_{MLE}=2.2151$ for the truncated Normal distribution.

We use the Gurobi $7.0$ solver API for Python to solve the models. The solver parameters for tuning are all set to their default values. We use SAA with $10$ reps and equal number of samples to the original dataset for a model with $n=5$ (scheduling $5$ jobs on a single server). The Box-plots of the objective function (16a) for different combinations of $C^{W}$ and $C^{I}$ parameters from the list of $[1,2,5]$ are depicted in Figure 1. The blue plots are related to the SAA model and the red ones are related to the DRO model.

As we can see in Figure 1, the base cost of the planning for $C^{W}=1$ and $C^{I}=1$ is estimated to be $13.40$ for SAA and $22.02$ for DRO and it is increasing proportionally by $C^{W}$ and $C^{I}$. Since DRO considers the worst-case distribution given the fixed mean and standard deviation, in all cases the total objective of DRO is higher than SAA. The actual decisions and their Box-plots are shown in Figure 2.

The interesting trends in Figure 2 are related to the optimal scheduled appointments when changing $C^{W}$ and $C^{I}$. As we can see, in settings with high ratio of $\frac{C^{W}}{C^{I}}$, the length of the allowances are increasing by the order of the jobs and in settings with with high ratio of $\frac{C^{I}}{C^{W}}$, the allowances are decreasing by the order of the jobs. Job duration estimates from DRO are generally higher than SAA. This is due to the fact that DRO considers the worst-case distribution of the job durations whereas SAA assumes the exact distribution. Further, DRO is more sensitive to the ratio of the wait/idle costs.

To make a fair comparison, we use Maximum Absolute Deviation (MAD) for the loss function of the SEO and the proposed loss function (15) for the IEO. Moreover, we evaluate the actual objective value (16a) for the solutions from both method. We also make sure all other parameters and hyperparameters of the networks are the same in both settings.

As we can see in Table 1, the performance of the IEO is better than SEO in most of the settings. The most interesting part of this table is the objective function for the base parameters $C^{W}=1$ and $C^{I}=1$. In here, the solutions from the IEO is $10.56$, and from SEO to $10.86$ and both of them are better than the objective from classic model (13.40). This fact indicates that the i.i.d assumption is not valid.

From Table1, we can also conclude that the choice of the distribution does not really affect the performance of the both models. As we expected, the performance of the SEO drops for the cases with high values of $C^{W}$ or $C^{I}$. This is due to the fact that in SEO we ignore these costs when we are estimating the job durations. The results clearly show how SEO can lead to sub-optimal solution.

The benefits of using DNNs for the contextual ASP do not end with bringing in context in decision making and creating a task-based loss function. In some cases, other ML algorithms such as SVM can be used, but they are often constrained by the assumption that we can define all the covariates. However, this is not necessarily true in many cases and making assumptions about non-numeric features can lead to low sensitivity. Deep learning is a fast-growing field that could be an ideal solution for these cases. This is due to the fact that we can learn features from raw images. In screening process for lung cancer, millions of CT scans will have to be analyzed. This is a controversial task even among radiologists. Further, radiologists often have to look through large volumes of these images that can lead to mistakes. Here, we skip the details about the screening process, and the dataset. We refer the interested readers to (?) for more details about lung nodule analysis.

Consider a scenario in which we try to schedule patients for a second screening based on their initial phase results. Therefore, if the radiologist in the initial phase detects a nodule, the patient needs more time for the second phase. The process of scheduling patients in this manner can be an overwhelming burden for the radiologists. In this paper, we use the LIDC-IDRI dataset with 8723 CT scans. Similar to the previous example, we add more covariates (gender, day, hour) and we sample the response variable (appointment duration) from a Normal distribution using similar means and standard deviations to the previous experiment. The only difference in this experiment with the previous one is that the intensity is not a categorical column anymore and it is replaced by the image.