Parallel Genetic Algorithm for solving Job-Shop Scheduling Problem Using Topological sort

Job Shop Scheduling Problem (JSSP) is one of the hard combinatorial optimization problems for machines having multiple jobs and multiple processing elements. This paper presents Parallel Genetic Algorithm (PGA) by Using Topological sorting, which is able to improve the solution of JSSP. Our proposed algorithm minimizes the execution time for Make span calculation by using PGA. Proposed PGA applies parallel topological sort on initial populations to generate linear sequences. After that whatever acyclic schedules come it applies crossover mutation on that and finally calculates the minimum Make span parallely for each linear sequence in optimal time. We implemented the PGA on GPU based machine using CUDA 5.0. Results are evaluated for different combinations of JSSP. Experimental results are compared with sequential genetic algorithm for JSSP.