TITLE:
Comparative Study of Different Representations in Genetic Algorithms for Job Shop Scheduling Problem
AUTHORS:
Vedavyasrao Jorapur, V. S. Puranik, A. S. Deshpande, M. R. Sharma
KEYWORDS:
Job Shop Scheduling, Genetic Algorithm, Genetic Representation, Conceptual Model
JOURNAL NAME:
Journal of Software Engineering and Applications,
Vol.7 No.7,
June
10,
2014
ABSTRACT:
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.