Cooperative Threads with Effective-Address in Simulated Annealing Algorithm to Job Shop Scheduling Problems

Abstract

This paper presents a parallel algorithm applied to the job shop scheduling problem (JSSP). The algorithm generates a set of threads, which work in parallel. Each generated thread, executes a procedure of simulated annealing which obtains one solution for the problem. Each solution is directed towards the best solution found by the system at the present, through a procedure called effective-address. The cooperative algorithm evaluates the makespan for various benchmarks of different sizes, small, medium, and large. A statistical analysis of the results of the algorithm is presented and a comparison of performance with other (sequential, parallel, and distributed processing) algorithms that are found in the literature is presented. The obtained results show that the cooperation of threads carried out by means of effective-address procedure permits to simulated annealing to work with increased efficacy and efficiency for problems of JSSP.

Keywords

• <i>effective-address</i>
• hamming distance
• thread
• critical section