## 3 Our Parallel Strategies
### Parallel Initialization on GPU
#### 3.2.1 Facility Sequence Generation  
To generate facility sequences randomly, the conventional method (INI_FS1) is usually adopted, i.e., if there are \(p\) facilities, \(p\) random numbers are generated and any two numbers cannot be identical. An example to illustrate INI_FS1 is shown in Figure 4. Assume there are seven facilities, and they are represented by letters, A to G, respectively. Actually, each letter is associated with a code, e.g., 1 to 7 for A to G. Initially, we need a facility sequence to generate different facility sequences from it, which is called the seed facility sequence. The seed facility sequence is set according to alphabetical order, as shown on the left side of Figure 4. To generate a new individual of the facility sequence, Step 1 is to produce one random integer number, 5 in this example. Then at Step 2, the second random integer number, 3, is produced. In order to avoid generating two identical facilities, we have to compare the newly generated facility with all previous ones at every step. Therefore, at Step 2, the second number, 3, is compared with the first number, 5, and we conclude that 3 can be kept. Next, at Step 3 the number 5 is produced, however, it is identical to the first number in the sequence. Therefore, the newly generated facility with number 5 should be abandoned and regeneration of the third number is required. At Step 4, the code number 4 is randomly produced, which can be accepted through comparing it with the preceding numbers. Repetition of random number generation and duplication avoidance like above steps, finally a new facility sequence is generated, as shown on the right-hand side of Figure 4. In this method, a large number of comparisons are required, making the complexity of the algorithm equal to O(\(p^{2}\)). Therefore, our improved method (INI_FS2) is proposed below to eliminate comparisons and also to avoid regeneration of random numbers for the same array element. The main idea of INI_FS2 method is to get a new facility sequence by performing a swap operation several times on the seed facility sequence to fully randomizing the facility positions. If there are  
Figure 4: An example of the INI_FS1 method. \begin{table}
\begin{tabular}{c c} \hline
**Kernel Function** & **Number of Blocks (B)** & **Number of Threads per Block (T)** \\ \hline Parallel facility sequences generation & \(15\) & \(500\) \\ Parallel bay divisions generation & \(15\) & \(500\) \\ Parallel roulette wheel selection & \(15\) & \(500\) \\ Parallel mutation operator & \(15\) & \(500\) \\ Parallel migration operator & \(15\) & \(5\text{*}\beta\)1  \\ \end{tabular}
\end{table} 
Table 5: Configuration of each kernel function. \(p\) facilities, \(p\) swaps are performed. How the \(p\) swaps are performed is based on an array, called'swap position', which contains \(p\) random numbers and the value of each random number is between 0 and \((p-1)\). It is not required that any two of the \(p\) random numbers are not identical, which is crucial to eliminate comparisons of duplicates. The random numbers stored in the array of swap position will be extracted from the head to the end, one by one, to perform a swap on the seed facility sequence. At Step \(i\), we exchange two positions in the seed facility sequence, one is the position \((p-1-i)\), another is the position specified by the random number stored in the \((i-1)\)-th element in the array of swap position. An example is shown in Figure 5 to illustrate the method of INI_FS2. Firstly, we generate seven random numbers without checking duplicate and store them in the array of swap position, as shown on the left-hand side of Figure 5. At Step 1, because the first random number in the array of swap position is 5, we exchange the two elements on Positions 6 and 5 in the array of facilities. At Step 2, because the second random number in swap position is 3, Positions 3 and 5 in the facilities array are exchanged. Similarly, Positions 2 and 5 are swapped at Step 3.