# Outpatient Appointment Optimization: A Case Study of a Chemotherapy Service
## 5 Resolution Methods
### Genetic Algorithm  
Meta-heuristics methods received more attention as its performance increased significantly to solve resource-constrained project scheduling for healthcare services [12; 18; 19; 30]. In this problem, since it is straightforward to calculate the planning given a list of patients' entrance using FFS, we decided to use genetic algorithm to generate numerous lists and to converge toward the best.  
The main elements of our GA are as follows:  
* **Encoding:** We encode a chromosome as an ordinal sequence of patients, i.e., a chromosome is a permutation of the list of patients because we try to determine a priority list to schedule with FFS, similar to the priority-based heuristics earlier.
* **Initial population:** Given the permutation encoding scheme above, the initial population is created by randomly shuffling \(N_{P}\) times the set of patients \(\{1,2,\dots,n\}\).
* **Selection: Tournament Selector** (TS) is chosen because of its \(O(n)\) time complexity and easy _parallelization_ for speeding up calculation in practical use. Furthermore, while a large tournament results in loss of diversity, a binary tournament performance is generally inferior to a three-tournament. Hence, the tournament size is fixed by 3. Let us denote \(F_{O}\) (\(0\leq F_{O}\leq 1\)) as the fraction of population selected to give offspring.  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Priority** & **Description** & **Formulation** \\ \hline PT & Total Processing Time & \(\sum\limits_{k\in\Theta_{i}}\sum\limits_{o\in O}p_{i,k}^{o}\) \\ \hline IPT & Ideal Total Processing Time & \(\sum\limits_{k\in\Theta_{i}}IPT_{i,k}\) \\ \hline RLIPT &
\begin{tabular}{c} Request’s Length and Ideal \\ Total Processing Time \\ \end{tabular} & \((n_{i}\); \(IPT_{i})\) \\ \hline \hline \end{tabular}
\end{table}
Table 3: Priority definition.  
* **Crossover:** Due to the permutation encoding, the order of requests is critical to deduce the planning. Hence, we adopt **Partially Mapped Crossover** (PMX, Figure 5), first introduced by [PERSON] [31], so that a potentially good local order is transferred from parent to child.
* **Mutation:** The offspring are then applied **Partial Mutator Shuffle** (PSM, known as _Swap Mutator_, Figure 6) with probability \(P_{M}\)[32], so that a new order not in the current research neighborhood may appear.
* **Population management:** Denote \(F_{S}(=1-F_{O})\) as the fraction of current population that we want to keep for the next generation in order to preserve diversity. The population is kept constant by combining the children (\(\lceil F_{O}\times N_{P}\rceil\)) and parents (\(\lceil F_{S}\times N_{P}\rceil\)).
* **Stop condition:** The process is terminated after \(N_{G}\) successive generations that the objective value of the incumbent has not been changed.  
We chose \((F_{O},F_{S})=(0.5,0.5)\) for a balance of the intensity and the diversity of the search. The process stops after continuously staying at an objective value for long enough. The preliminary numerical experiments show that the incumbent rarely descends after 100 generations. Therefore, we can make the GA finish earlier by terminating it after a certain number of times, obtaining the same objective value instead of a fixed number of generations in total.