Comparative Study of Different Representations in Genetic Algorithms for Job Shop Scheduling Problem

摘要

Due to NP-Hard nature of the Job Shop Scheduling Problems (JSP), exact methods fail to provide the optimal solutions in quite reasonable computational time. Due to this nature of the problem, so many heuristics and meta-heuristics have been proposed in the past to get optimal or near-optimal solutions for easy to tough JSP instances in lesser computational time compared to exact methods. One of such heuristics is genetic algorithm (GA). Representations in GA will have a direct impact on computational time it takes in providing optimal or near optimal solutions. Different representation schemes are possible in case of Job Scheduling Problems. These schemes in turn will have a higher impact on the performance of GA. It is intended to show through this paper, how these representations will perform, by a comparative analysis based on average deviation, evolution of solution over entire generations etc.