Abstract
It is observed that the optimization technique Genetic Algorithm is gaining more importance over the past several years. With high computing power we are able to apply soft computing techniques to solve complex problems in less time. An approach through Genetic Algorithm to solve job shop scheduling problems using inversion operator has been tried, with make-span objective. Computational experiments of this attempt have shown better solutions coupled with appreciable reduction in computer processing time. A set of 20 selected benchmark problems were tried with the proposed heuristic for validation and the results are encouraging. The inversion operator is found to perform better.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Franch S (1981) Sequencing and scheduling – an introduction to the mathematics of the job-shop. Wiley, New York
Baker KR (1974) Introduction to sequencing and scheduling. Wiley, New York
Pinedo M, Chao X (1999) Operation scheduling with applications in manufacturing and services. McGraw-Hill, Boston
Nakano R, Yamada T (1991) Conventional genetic algorithms for job-shop problems. In: Belew RK, Booker LB (eds) Proceedings of the Fourth International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, pp 477–479
Yamada T, Nakano R (1992) A genetic algorithm applicable to large-scale job shop problems. In: Manner R, Manderick B (eds) Parallel problem solving from nature: PPSN II, Elsevier Science, North-Holland, pp 281–290
Fang H, Ross P, Corne D (1993) A promising genetic algorithm approach to job shop scheduling, rescheduling and open shop scheduling. In: Forrest S (ed) Proceedings of the Fifth International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, pp 375–382
Gen M, Tsujimura J, Kubota E (1994) Solving job-shop scheduling problem using genetic algorithms. In: Gen M, Kobayashi S (eds) Proceedings of the 16th International Conference on Computers and Industrial Engineering, Ashikaga, Japan, pp 576–579
Ferreira C (2002) Combinatorial Optimization by Gene expression programming: Inversion revisited. Argentine Symposium on Artificial Intelligence, pp 160–174
Shubhra Sankar Ray, Sanghamitra Bandyopadhyay, Sankar K. Pal (2004) New operators of Genetic Algorithms for Traveling Salesman Problem. IEEE Int. Conf. on Pattern Recognition (ICPR 04) pp 497–500
Filho JLR, Treleaven PC (1994) Genetic algorithm programming environments. IEEE Comput 27(6):28–43
Gen M, Cheng R (1997) Genetic algorithms and engineering design. Wiley, New York
Bierwirth C (1995) A generalized permutation approach to job shop scheduling with genetic algorithm. OR Spectrum 17:87–92
Mattfeld DC (1996) Evolutionary search and the job shop: investigations on genetic algorithms for production scheduling. Physica-Verlag, Heidelberg, Germany
Ponnambalam SG, Aravindan P, Sreenivasa Rao P (2001) Comparative evaluation of genetic algorithms for job-hop scheduling. Prod Plan Control 12(6):560–574
Holland JH (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, MI, USA
Fisher H, Thompson GL (1963) Probabilistic learning combinations of local job-shop scheduling rules. In: Muth JF, Thompson GL (eds) Industrial scheduling. Prentice-Hall, Englewood Cliffs, NJ, USA, pp 225–251
Adams J, Balas E, Zawak D (1988) The shifting bottle-neck procedure for job-shop scheduling. Manage Sci 34(3):391–401
Applegate D, Cook W (1991) A computational study of the job-shop scheduling problems. ORSA-J Comput 3:149–156
Lawrence S (1984) Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques. Technical report, Graduate School of Industrial Administration, Carnegie Melon University, USA
Beasley JE (1990) OR-Library. http://mscmga.ms.ic.ac.uk/info.html. Cited 20 November 2004
Acknowledgements
Thanks are due to Dr. C. Rajendran, Professor, Department of Humanities and Social sciences, Indian Institute of Technology, Chennai, India for useful suggestions that helped improve the paper.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Amirthagadeswaran, K.S., Arunachalam, V.P. Enhancement of performance of Genetic Algorithm for job shop scheduling problems through inversion operator. Int J Adv Manuf Technol 32, 780–786 (2007). https://doi.org/10.1007/s00170-005-0392-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-005-0392-3