## 3 Preliminaries and Problem Definition
### Scheduling Problem Statement  
In this subsection, the **Scheduling problem** is introduced formally. First, the notation, terminology, and assumptions are fixed and then the scheduling criteria are transformed to cost function and constraints. Let \(\mathcal{S}=\{s_{1},s_{2},\ldots,s_{|\mathcal{S}|}\}\) be the set of surgery types that can be performed in the medical department and let us assume that the duration \(d(s_{k})\) of each type of surgery \(s_{k}\in\mathcal{S}\) is a random variable with normal probability density function (pdf) \(d(s_{k})=N(\mu_{d(s_{k})},\sigma_{d(s_{k})})\), where \(\mu_{d(s_{k})}\) is the average and \(\sigma_{d(s_{k})}\) is the standard deviation. On the other hand, let \(Dt\) be the delay with respect to the starting time of a block and let \(Ct\) be the cleaning time duration of the OR after a surgery is performed. It is assumed that \(Dt\) and \(Ct\) are also random variables with normal pdf, i.e., \(Dt=N(\mu_{Dt},\sigma_{Dt})\) and \(Ct=N(\mu_{Ct},\sigma_{Ct})\). Furthermore, let us consider \(\mathcal{W}=\{w_{1},w_{2},\ldots,w_{|\mathcal{W}|}\}\) an ordered list of patients such that, if \(w_{j}\in\mathcal{W}\), \(j\) is the preference order of the patient \(w_{j}\) in the waiting list. In addition, let us assume an ordered set of time blocks \(\mathcal{B}=\{b_{1},\ldots,b_{|\mathcal{B}|}\}\) to schedule, where \(b_{|\mathcal{B}|}\) is the block corresponding to the latest date. Each block \(b_{i}\in\mathcal{B}\) has a fixed duration denoted by \(l(b_{i})\). For each time block \(b_{i}\in\mathcal{B}\) to schedule, there exists a binary decision vector \(\mathbf{S}_{i}\in\{0,1\}^{1\times|\mathcal{W}|}\) with a dimension equal to the number of the patients in the waiting list. If \(\mathbf{S}_{i}[j]=1\), then surgery of patient \(w_{j}\) should be performed in working day \(i\leq|\mathcal{B}|\). Let \(S_{b_{i}}\) be the set of surgeries scheduled in the time block \(b_{i}\); then, the total duration \(T_{b_{i}}\) of the time block \(b_{i}\) can be computed by Equation (1). That is the sum of: (i) the delay with respect to the starting time (i.e., \(Dt\)), (ii) the duration of the surgeries scheduled in the time block \(b_{i}\), and (iii) the cleaning time duration \(Ct\) between two consecutive surgeries. Notice that the cleaning time after the last surgery is not considered:  
\[T_{b_{i}}=Dt+(|S_{b_{i}}|-1)\cdot Ct\sum_{s_{k}\in S_{b_{i}}}\left[d(s_{k}) \right]. \tag{1}\]  
Because all these variables are assumed to follow a normal distribution, the total duration \(T_{b_{i}}\) of the time block \(b_{i}\) also follows a normal distribution \(T_{b_{i}}=N(\mu_{T_{b_{i}}},\sigma_{T_{b_{i}}})\). The goal of the scheduling problem is the assignment of the patients from the waiting list \(\mathcal{W}\) to the set of time blocks \(\mathcal{B}\) considering the scheduling criteria C1, C2 and C3. Let us define the following further notations:  
* \(\mathbf{\mu_{w}}\) be a row vector containing the average duration of surgeries of the patients in the waiting list \(\mathcal{W}\). For example, \(\mathbf{\mu_{w}}(j)\) represents the average duration of the surgery corresponding to the patient \(w_{j}\). * \(\mathbf{Po}\) be a row vector containing the preference order of the patients. Assuming that patients are ordered according to their priority, then \(\mathbf{Po}(j)=j\). * \(Cl\) is the minimum confidence level of not exceeding the total time. then:  
Criterion C1 is formalized by objective **O1** given by Equation (2). This equation maximizes the expected surgery time in each block (\(\mathbf{\mu_{w}}\cdot\mathbf{S}_{i}\)) giving more importance to the first ones (\(|\mathcal{B}|+1-i\)):  
\[max\sum_{i=1}^{|\mathcal{B}|}\left[\mathbf{\mu_{w}}\cdot\mathbf{S}_{i}\cdot(|\mathcal{ B}|+1-i)\right]. \tag{2}\]  
Criterion C2 is imposed by the chance probability constraint given by Equation (3).