# Parallel Makespan Calculation for Flow Shop Scheduling Problem with Minimal and Maximal Idle Time
## 7 Solving Method
### Base SA Implementation  
SA is an iterative local search metaheuristic that employs the concept of a neighborhood. At each iteration, a neighbor \(\pi^{\prime}\) of the current solution \(\pi\) is generated and evaluated. If \(\pi^{\prime}\) is better than \(\pi\) (for our problem, this means that \(C_{\text{max}}(\pi^{\prime})<C_{\text{max}}(\pi)\)) then \(\pi^{\prime}\) is accepted and replaces \(\pi\). Otherwise, \(\pi^{\prime}\) can still be accepted with a probability based on the goal function of the neighbor and a parameter called temperature. An initial temperature is chosen and every set number of iterations \(E\) (called epoch) the temperature generally decreases according to the chosen cooling schedule. At the beginning, at a higher temperature, worse solutions are more readily accepted, allowing for diversification. When the temperature becomes lower, the algorithm starts to focus on exploring the current portion of the solution space (intensification). In general, in order to implement SA for our FSSP problem, we need to decide the following:  
1. Solution representation;
2. Definition of neighborhood;
3. Initial temperature and cooling schedule;
4. Initial solution;
5. Acceptance function;
6. Stopping condition.  
The typical structure of the SA method is shown in Algorithm 3.  
```
1\(\pi\leftarrow\text{generateInitialSolution}()\);
2\(\pi^{*}\leftarrow\pi\) ;
3\(t\leftarrow\text{sethitialTemperature}()\);
4 whilenotstoppingCondition()do
5 for\(i\in\{1,2,\dots,E\}\)do
6\(\pi^{\prime}\leftarrow\text{generateRandomNeighbor}(\pi)\);
7 if\(C_{\text{max}}(\pi^{\prime})<C_{\text{max}}(\pi)\)then
8\(\pi\leftarrow\pi^{\prime}\);
9 if\(C_{\text{max}}(\pi)<C_{\text{max}}(\pi^{*})\)then
10\(\pi^{*}\leftarrow\pi\) ;
11
12 else
13\(\delta\leftarrow\text{generateRandomNumber}(\mathcal{U}[0;1])\);
14 if\(\delta<\text{acceptanceProbability}()\)then
15\(\pi\leftarrow\pi^{\prime}\);
16
17
18
19
20
21 end if
22
23 end for
24
25 end for
```  
**Algorithm 3**Outline of the simulated annealing metaheuristicThe following SA implementation was used. The processing order \(\pi\) was employed as a solution representation. As for the neighborhood, the swap neighborhood was chosen, i.e., a neighbor \(\pi^{\prime}\) was created from \(\pi\) by swapping elements \(\pi(i)\) and \(\pi(j)\) with each other, where \(i\in\mathcal{J}\) and \(j\in\mathcal{J}\setminus\{i\}\) are chosen randomly. The initial temperature was set as follows. \(k\) random solutions were generated. Let \(\pi_{b}\) and \(\pi_{w}\) be the best and worst among those \(k\) solutions. Then, the initial temperature \(t\) is set to:  
\[t\leftarrow\frac{C_{\max}(\pi_{w})-C_{\max}(\pi_{b})}{n}. \tag{54}\]  
As for the cooling schedule, the standard geometric one was employed. The following temperature is given as \(\alpha t\), where \(\alpha\in(0;1)\) and \(t\) is the previous temperature. The initial solution \(\pi\) is chosen as a random permutation of sequence \(\{1,2,\ldots,n\}\). The acceptance probability of a neighbor solution \(\pi^{\prime}\) is given as  
\[e^{\frac{C_{\max}(\pi)-C_{\max}(\pi^{\prime})}{t}}. \tag{55}\]  
In order for the algorithm to be applicable for large problem sizes and as a local-search subroutine for other solving methods, a time limit was chosen as the stopping condition. More specifically, the algorithm stops and returns the best found solution \(\pi^{*}\) after:  
\[\frac{nm}{51.2} \tag{56}\]  
milliseconds. This way, for 1024 jobs and 50 machines, the running time is one second. After preliminary research, the parameters were set to \(k=20\), \(E=10\) and \(\alpha=0.9999\).