Hybridization of Genetic Algorithm with Parallel Implementation of Simulated Annealing for Job Shop Scheduling

Abstract

Problem statement: The Job Shop Scheduling Problem (JSSP) is observed as one of the most difficult NP-hard, combinatorial problem. The problem consists of determining the most efficient schedule for jobs that are processed on several mac hines. Approach: In this study Genetic Algorithm (GA) is integrated with the parallel version of Sim ulated Annealing Algorithm (SA) is applied to the job shop scheduling problem. The proposed algor ithm is implemented in a distributed environment using Remote Method Invocation concept. The new genetic operator and a parallel simulated annealing algorithm are developed for sol ving job shop scheduling. Results: The implementation is done successfully to examine the convergence and effectiveness of the proposed hybrid algorithm. The JSS problems tested with very well-known benchmark problems, which are considered to measure the quality of prop osed system. Conclusion/Recommendations: The empirical results show that the proposed geneti c algorithm with simulated annealing is quite successful to achieve better solution than the indi vidual genetic or simulated annealing algorithm.