Page 121 - IJOCTA-15-2

¨
E. Sonu¸c, E. Ozcan / IJOCTA, Vol.15, No.2, pp.311-329 (2025)

Master Thread
Begin
Read the problem instance

Set the number of threads (nt)

Thread #0 ... Thread #(nt-1)
Initiate history list Initiate history list

Create a candidate solution Create a candidate solution

Evaluate the candidate Evaluate the candidate
solution solution

Is the new solution Is the new solution
acceptable? acceptable?
No Yes No Yes

Keep the current Accept the Keep the current Accept the
solution candidate solution solution candidate solution

Update the history list Update the history list

Is the stopping Is the stopping
No No
criterion met? criterion met?
Yes Yes

Master Thread
Return the global best
solution among threads.

End

Figure 2. The flowchart of the proposed PLAHC algorithm

outperforms L = 100, suggesting that paralleliza- increasing L. In particular, L = 50 significantly
tion allows for more efficient exploration of the so- outperforms other configurations for the largest
lution space with shorter history lists. This par- instances, suggesting that increased parallelism
allel approach appears to mitigate the need for allows efficient solution space exploration with
very long history lists in some cases, likely due to moderate history list lengths. However, an unex-
multiple threads simultaneously exploring differ- pected performance drop occurs at L = 100, es-
ent regions of the solution space. Overall, the 4- pecially for the largest problems, indicating that
thread implementation significantly improves the very long history lists combined with high paral-
effectiveness of the algorithm, achieving better re- lelism can sometimes lead to suboptimal explo-
sults with shorter history lists than the sequen- ration. This 8-thread implementation highlights
tial version, potentially reducing computational the improved effectiveness of the algorithm with
requirements while improving solution quality. increased parallelism, achieving superior results
Table 4 shows the gap scores of PLAHC us- with shorter history lists.
ing 8 threads. It shows further performance im-
provements over the 4-thread version. It achieves Table 5 shows the gap scores of PLAHC us-
the best overall results at L = 50, with an av- ing 16 threads. It achieves optimal solutions
erage gap score of 0.29. Small and medium in- for small and medium instances across all his-
stances consistently reach optimal solutions over tory list lengths, demonstrating good perfor-
most L values, while larger instances benefit from mance. However, its performance on the largest
316