# The Online Reservation Problem
## 3 Algorithms
### The Deterministic-Selection Algorithm (Algorithm D)  
Job \(j\) is said to be admissible to server \(i\) if it does not conflict with any previously-accepted job of server \(i\) and if the job \(j\)'s duration, \(d_{j}\), is greater than or equal to the admission threshold of server \(i\), \(\phi(i)\) (defined subsequently in Definition 2). Algorithm \(D\) assigns an incoming job to the smallest-indexed server to which it is admissible, if at least one such server exists. Otherwise, it declines the job. The pseudocode is provided below (Algorithm 1). ```
initialize \(\mathcal{I}=\emptyset\); for every incoming job \(j\) in the instancedo \(\mathcal{I}\leftarrow\{i\in[n]\text{ such that }d_{j}\geq\phi(i)\text{ and job }j\text{ does not conflict with any previously-accepted job of server }i\}\); if\(\mathcal{I}\
eq\emptyset\)then  assign job \(j\) to server \(\min\{i\text{ such that }i\in\mathcal{I}\}\); else  decline job \(j\);  end for  end for
```  
**Algorithm 1**Pseudocode for Algorithm \(D\). The admission thresholds serve to increase the likelihood that some longer duration jobs will be accepted by turning away small jobs, thereby overcoming a shortcoming of the greedy algorithms. **Definition 2**. : \[\bullet\quad t:\mathbb{N}\times[1,\infty)\mapsto\mathbb{R}\text{ such that }t(n,y)\doteq\inf\left\{x\geq 1\ \middle|\ \frac{x}{3n}\middle\lceil\frac{3n}{x}\right\rceil\ \left(1+\frac{x}{3n}\right)^{n-\left\lceil\frac{3n}{x}\right\rceil}\geq y \right\}.\] \[\bullet\quad I\doteq\left\lceil 3n/t\left(n,\Delta\right)\right\rceil.\] \[\bullet\quad\phi(i)\doteq \begin{cases}D_{min}&\text{if }i\leq I\text{ and }i\in[n+1]\text{, and}\\ \frac{t\left(n,\Delta\right)ID_{min}}{3n}\left(1+\frac{t\left(n,\Delta\right)}{3 n}\right)^{i-I-1}&\text{if }i>I\text{ and }i\in[n+1]\text{.}\end{cases} \]  
To further illustrate how Algorithm \(D\) works, we consider a numerical example where \(D_{min}=1\), \(D_{max}=2\), and \(n=3\). Therefore, \(\Delta=2\). Additionally, by Definition 2, \(\phi(1)=1\), \(\phi(2)=1\), and \(\phi(3)\approx 1.236\). Consider the instance with five jobs presented in Table 1, below. The same instance is represented pictorially in Figure 2. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Index \(j\) of Job** & **Start Time (\(s_{j}\))** & **Duration (\(d_{j}\))** \\ \hline
1 & 1.0 & 1.0 \\ \hline
2 & 1.1 & 1.2 \\ \hline
3 & 1.2 & 1.2 \\ \hline
4 & 1.3 & 2.0 \\ \hline
5 & 4.0 & 1.0 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: An instance of ORP with five jobs. Jobs arrive in the order of their index \(j\). Note that, in the instance presented in Table 1, the first four jobs overlap with each other. Job 5 does not overlap with any of the other jobs. Algorithm \(D\) makes decisions as follows:  
* **Job 1:*
* Job 1 is admissible to server 1 because the duration of job 1 is greater than or equal to admission threshold of server 1 (\(d_{1}=1\geq\phi(1)=1\)) and because no jobs were previously assigned to server 1. * Job 1 is admissible to server 2 because duration of job 1 is greater than or equal to the admission threshold of server 2 (\(d_{1}=1\geq\phi(2)=1\)) and because no jobs were previously assigned to server 2. * Job 1 is not admissible to server 3 because the duration of job 1 is smaller than the admission threshold of server 3 (\(d_{1}=1<\phi(3)\approx 1.236\)). Because server 1 has the smallest index amongst servers to which job 1 is admissible, Algorithm \(D\) assigns the job to server 1. * **Job 2:*
* Job 2 is not admissible to server 1 because it conflicts with job 1 that was previously assigned to server 1. * Job 2 is admissible to server 2 because the duration of job 2 is greater than or equal to admission threshold of server 2 (\(d_{2}=1.2\geq\phi(2)=1\)) and because no jobs were previously assigned to server 2. * Job 2 is not admissible to server 3 because the duration of job 2 is smaller than the admission threshold of server 3 (\(d_{2}=1.2<\phi(3)\approx 1.236\)). Since server 2 is the only server to which job 2 is admissible, Algorithm \(D\) assigns the job to server 2.