Real Coded Genetic Algorithms for Solving Flexible Job-Shop Scheduling Problem - Part II: Optimization

Abstract:

This paper addresses optimization of the flexible job-shop problem (FJSP) by using real-coded genetic algorithms (RCGA) that use an array of real numbers as chromosome representation. The first part of the papers has detailed the modelling of the problems and showed how the novel chromosome representation can be decoded into solution. This second part discusses the effectiveness of each genetic operator and how to determine proper values of the RCGAs parameters. These parameters are used by the RCGA to solve several test bed problems. The experimental results show that by using only simple genetic operators and random initial population, the proposed RCGA can produce promising results comparable to those achieved by other best-known approaches in the literatures. These results demonstrate the robustness of the RCGA.

• Periodical: Advanced Materials Research (Volume 701)
• Pages: 364-369
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.701.364
• Online since: May 2013
• Authors: Wayan F. Mahmudy, Romeo M. Marian, Lee H.S. Luong
• Keywords: Flexible Job-Shop Problem, Manufacturing Systems, Real-Coded Genetic Algorithm, Scheduling

References

[1] M. Gen and R. Cheng, Genetic Algorithms and Engineering Optimization, John Wiley & Sons, Inc., New York (2000).

[2] G. Tuncel, "A Heuristic Rule-Based Approach for Dynamic Scheduling of Flexible Manufacturing Systems," in Multiprocessor Scheduling: Theory and Applications, E. Levner, Ed., I-Tech Education and Publishing: Vienna, Austria, (2007).

DOI: 10.5772/5229

[3] A. Madureira and J. Santos. "Proposal of Multi-Agent Based Model for Dynamic Scheduling in Manufacturing," in The 6th WSEAS Int. Conf. on Evolutionary Computing. Lisbon, Portugal (2005), pp.193-198.

[4] H. M¨uhlenbein and D. Schlierkamp-Voosen, Predictive Models for the Breeder Genetic Algorithm; Continuous Parameter Optimization, Evolutionary Computation vol. 1 (1993), p.25–49.

DOI: 10.1162/evco.1993.1.1.25

[5] P. Brandimarte, Routing and Scheduling in a Flexible Job Shop by Tabu Search, Annals of Operations Research, vol. 41 no. 3 (1993), pp.157-183.

DOI: 10.1007/bf02023073

[6] M. Lozano and F. Herrera, Fuzzy Adaptive Genetic Algorithms: Design, Taxonomy, Soft Computing, vol. 7 (2003), p.545–562.

DOI: 10.1007/s00500-002-0238-y

[7] W.F. Mahmudy, R.M. Marian, and L.H.S. Luong. "Solving Part Type Selection and Loading Problem in Flexible Manufacturing System Using Real Coded Genetic Algorithms – Part II: Optimization," in International Conference on Control, Automation and Robotics. Singapore: World Academy of Science, Engineering and Technology (2012), pp.778-782.

DOI: 10.1109/kst.2013.6512792

[8] N.B. Ho and J.C. Tay. "Genace: An Efficient Cultural Algorithm for Solving the Flexible Job-Shop Problem," in IEEE international conference on robotics and automation (2004), p.1759–1766.

DOI: 10.1109/cec.2004.1331108

[9] F. Pezzella, G. Morganti, and G. Ciaschetti, A Genetic Algorithm for the Flexible Job-Shop Scheduling Problem, Computers & Operations Research, vol. 35 no. 10 (2008), pp.3202-3212.

DOI: 10.1016/j.cor.2007.02.014

[10] J.-q. Li, Q.-k. Pan, S.-x. Xie, B.-x. Jia, and Y.-t. Wang, A Hybrid Particle Swarm Optimization and Tabu Search Algorithm for Flexible Job-Shop Scheduling Problem, International Journal of Computer Theory and Engineering, vol. 2 no. 2 (2010), pp.1793-8201.

DOI: 10.7763/ijcte.2010.v2.139

[11] N. Al-Hinai and T. ElMekkawy, An Efficient Hybridized Genetic Algorithm Architecture for the Flexible Job Shop Scheduling Problem, Flexible Services and Manufacturing Journal, vol. 23 no. 1 (2011), pp.64-85.

DOI: 10.1007/s10696-010-9067-y

[12] R.M. Marian, L.H.S. Luong, and K. Abhary, Assembly Sequence Planning and Optimisation Using Genetic Algorithms Part I: Automatic Generation of Feasible Assembly Sequences, Applied Soft Computing, vol. 2 no. 3F (2003), pp.223-253.

DOI: 10.1016/s1568-4946(02)00064-9