Comparative Study of Different Representations in Genetic Algorithms for Job Shop Scheduling Problem
- 1 Visvesvaraya Technological University, Belgaum, India
- 2 Visvesvaraya Technological University, Belgaum, India
- 3 Visvesvaraya Technological University, Belgaum, India
- 4 Visvesvaraya Technological University, Belgaum, India
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.
- Brucker, P. (2005) Complex Scheduling. Springer Publications, Berlin.
- Applegate, D. and Cook, W. (1991) A Computational Study of the Job-Shop Scheduling Problem. ORSA Journal on Computing, 3, 149-156.
- Balas, E. and Vazacopoulos, A. (1998) Guided Local Search with Shifting Bottleneck for Job-Shop Scheduling. Management Science, 44, 262-275.
- Jain, A.S. and Meeran, S. (1999) Deterministic Job-Shop Scheduling: Past, Present and Future. European Journal of Operational Research, 113, 390-434.
- 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.
- 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.
- Anderson, E.J., Glass, C.A. and Potts, C.N. (2003) Local Search in Combinatorial Optimization. Princeton University Press, Princeton.
- 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
- Roy, B. and Sussmann, B. (1964) Les Problemes d’ Ordon Ordonnancement Avec Constraints Disjunctives. SEMA, Note D.S., Paris.
- 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
- 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
- Adams, J., Balas, E. and Zawack, D. (1988) The Shifting Bottleneck Procedure for Job Shop Scheduling. Management Science, 34, 391-401.
- 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
- Bowman, H. (1959) The Schedule-Sequencing Problem. Operations Research, 7, 621-624. http://dx.doi.org/10.1287/opre.7.5.621
- Sivanandan, S.N. and Deepa, S.N. (2008) ISBN 978-3-540-73189-4, Springer Publications.