Parallelized GA-PSO algorithm for solving Job Shop Scheduling Problem

摘要

One of the classic problems in NP-class is Job-Shop Scheduling Problem (JSP). It is obvious that neither brute force nor greedy algorithm is suitable for this kind of problem. Researchers have proposed many approaches to tackle JSP, which are mainly metaheuristic manners. One advantageous property of the metaheuristic algorithm is that it has the parallelizable nature. This paper proposes another GA-PSO algorithm, which implements it in both parallel and non-parallel modes. The parallel portion is taken care by CUDA programming. Experiments show that compared to original GA, the GA-PSO gives 4.58% better solution and 2.43 times faster in average; while Parallelized GA-PSO speed gives 2.79 and 5.44 times faster than that in 80×80 size GA-PSO problem with 50 and 100 particles respectively.