JSEA  Vol.7 No.7 , June 2014
Comparative Study of Different Representations in Genetic Algorithms for Job Shop Scheduling Problem
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.


Cite this paper
Jorapur, V. , Puranik, V. , Deshpande, A. and Sharma, M. (2014) Comparative Study of Different Representations in Genetic Algorithms for Job Shop Scheduling Problem. Journal of Software Engineering and Applications, 7, 571-580. doi: 10.4236/jsea.2014.77053.
References
[1]   Brucker, P. (2005) Complex Scheduling. Springer Publications, Berlin.

[2]   Applegate, D. and Cook, W. (1991) A Computational Study of the Job-Shop Scheduling Problem. ORSA Journal on Computing, 3, 149-156.

[3]   Balas, E. and Vazacopoulos, A. (1998) Guided Local Search with Shifting Bottleneck for Job-Shop Scheduling. Management Science, 44, 262-275.

[4]   Jain, A.S. and Meeran, S. (1999) Deterministic Job-Shop Scheduling: Past, Present and Future. European Journal of Operational Research, 113, 390-434.

[5]   Ponnambalam and Jawahar, S.G. (2007) Hybrid Search Heuristics to Schedule Bottleneck Facility. In: Levner, E., Ed., Manufacturing Systems-Multiprocessor Scheduling: Theory and Applications, Itech Education and Publishing, Vienna, 436.

[6]   Cheng, R., Gen, M. and Tsujimura, Y. (1996) A Tutorial Survey of Job-Shop Scheduling Problems Using Genetic Algorithms—I. Representation. Computers and Industrial Engineering, 30, 983-997.

[7]   Anderson, E.J., Glass, C.A. and Potts, C.N. (2003) Local Search in Combinatorial Optimization. Princeton University Press, Princeton.

[8]   Manne, A.S. (1960) On the Job-Shop Scheduling Problem. Operations Research, 8, 219-223.
http://dx.doi.org/10.1287/opre.8.2.219

[9]   Roy, B. and Sussmann, B. (1964) Les Problemes d’ Ordon Ordonnancement Avec Constraints Disjunctives. SEMA, Note D.S., Paris.

[10]   Abdelmaguid, T.F. (2009) Permutation-Induced Acyclic Networks for the Job Shop Scheduling Problem. Applied Mathematical Modeling, 33, 1560-1572.
http://dx.doi.org/10.1016/j.apm.2008.02.004

[11]   Carlier, J. and Pinson, E. (1989) An Algorithm for Solving the Job-Shop Problem. Management Science, 35, 164-176. http://dx.doi.org/10.1287/mnsc.35.2.164

[12]   Adams, J., Balas, E. and Zawack, D. (1988) The Shifting Bottleneck Procedure for Job Shop Scheduling. Management Science, 34, 391-401.

[13]   Monch, L., Schabacker, R., Pabst, D., et al. (2007) Genetic Algorithm Based Subproblem Solution Procedures for a Modified Shifting Bottleneck Heuristic for Complex Job Shop. European Journal of Operations Research, 3, 2100-2118. http://dx.doi.org/10.1016/j.ejor.2005.12.020

[14]   Bowman, H. (1959) The Schedule-Sequencing Problem. Operations Research, 7, 621-624.
http://dx.doi.org/10.1287/opre.7.5.621

[15]   Sivanandan, S.N. and Deepa, S.N. (2008) ISBN 978-3-540-73189-4, Springer Publications.

[16]   Yun, Y.S. (2007) GA with FUZZY Logic Controller for Preemptive and Non-Preemptive Job Shop Scheduling Problems. Computers and Industrial Engineering, 3, 623-644.

[17]   Abdelmaguid, T.F. (2010) Representations in Genetic Algorithm for the Job Shop Scheduling Problem: A Computational Study. Journal of Software Engineering and Applications, 3, 1155-1162.

[18]   Giffler, B. and Thompson, G.L. (1960) Algorithms for Solving Production Scheduling Problems. Operations Research, 8, 487-503. http://dx.doi.org/10.1287/opre.8.4.487

[19]   Bean, J. (1994) Genetic Algorithms and Random Keys for Sequencing and Optimization. ORSA Journal of Computing, 6, 154-160. http://dx.doi.org/10.1287/ijoc.6.2.154

[20]   Bierwirth, C. (1995) A Generalized Permutation Approach to Job Shop Scheduling with Genetic Algorithms. OR Spektrum, 17, 87-92.

[21]   Anderson, E.J., Glass, C.A. and Potts, C.N. (2003) Local Search in Combinatorial Optimization. Princeton University Press, Princeton.

[22]   Holsapple, C.W., Jacob, V.S., Pakath, R. and Zaveri, J.S. (1993) Genetics-Based Hybrid Scheduler for Generating Static Schedules in Flexible Manufacturing Contexts. IEEE Transactions on Systems, Man, and Cybernetics, 23, 953-971. http://dx.doi.org/10.1109/21.247881

[23]   Goldberg, D. and Lingle, R. (1985) Alleles, Loci and the Traveling Salesman Problem. Proceedings of the 1st International Conference on Genetic Algorithms and Their Applications, Los Angeles, 1985, 154-159.

[24]   Davis, L. (1985) Applying Adaptive Algorithms to Epistatic Domains. Proceedings of the 9th International Joint Conference on Artificial Intelligence, 1989, 162-164.

[25]   Syswerda, G. (1989) Uniform Crossover in Genetic Algorithms. Proceedings of the 3rd International Conference on Genetic Algorithms, San Mateo, 2-9.

[26]   Beasley, J.E. (2008) Job Shop Scheduling.
http://people.brunel.ac.uk/~mastjjb/jeb/orlib/jobshopinfo.html

 
 
Top