Single Objective Evolutionary Algorithm for Flexible Job-shop Scheduling Problem

M. Nagamani; Dr. E. Chandrasekaran; Dr. D. Saravanan

doi:https://doi.org/10.14445/22315373/IJMTT-V3I2P508

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 3 | Issue 2 | Year 2012 | Article Id. IJMTT-V3I2P508 | DOI : https://doi.org/10.14445/22315373/IJMTT-V3I2P508

Single Objective Evolutionary Algorithm for Flexible Job-shop Scheduling Problem

M. Nagamani, Dr. E. Chandrasekaran, Dr. D. Saravanan

Citation :

M. Nagamani, Dr. E. Chandrasekaran, Dr. D. Saravanan, "Single Objective Evolutionary Algorithm for Flexible Job-shop Scheduling Problem," International Journal of Mathematics Trends and Technology (IJMTT), vol. 3, no. 2, pp. 78-81, 2012. Crossref, https://doi.org/10.14445/22315373/IJMTT-V3I2P508

Abstract

A meta-heuristic approach for solving the flexible job-shop scheduling problem (FJSP) is presented in this study. This problem consists of two sub-problems, the routing problem and the sequencing problem and is among the hardest combinatorial optimization problems. We propose a Evolutionary Algorithm (EA) for the FJSP. Our algorithm uses several different rules for generating the initial population and several strategies for producing new population for next generation. Proposed EA is tested on benchmark problems and with due attention to the results of other meta-heuristics in this field, the results of EA show that our algorithm is effective and comparable to the other algorithms.

Keywords

Halley’s method, Ujević method, Numerical examples, Nonlinear equations, Newton’s method

References

[1] Brandimarte, P., 1993. Routing and scheduling in a flexible job shop by taboo search. Ann. Operat. Res., 41: 157-183.
[2] Cheng, R., M. Gen and Y. Tsujimura, 1996. A tutorial survey of job-shop scheduling problems using genetic algorithms, Part I: Representation. Comput. Ind. Eng., 30: 983-997.
[3] Gao, J., L. Sun and M. Gen, 2008. A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Comput. Operat. Res., 35: 2892-2907.
[4] Jain, A.S. and S. Meeran, 1999. Deterministic job-shop scheduling: Past, present and future. Eur. J. Operat. Res., 113: 390-434.
[5] Goldberg, D.E., 1989. Genetic Algorithms in Search, Optimization and Machine Learning. 1st Edn., AddisonWesley Publishing Company, New York, USA., ISBN: 0201157675, pp: 36-90
[5] Pinedo, M., 2002. Scheduling: Theory, Algorithms and Systems. 1st Edn., Prentice Hall, New Jersey, ISBN 0-13- 281387.