Real Coded Genetic Algorithms for Solving Flexible Job-Shop Scheduling Problem - Part I: Modelling

Abstract:

This paper and its companion (Part 2) deal with modelling and optimization of the flexible job-shop problem (FJSP). The FJSP is a generalised form of the classical job-shop problem (JSP) which allows an operation to be processed on several alternatives machines. To solve this NP-hard combinatorial problem, this paper proposes a customised Genetic Algorithm (GA) which uses an array of real numbers as chromosome representation so the proposed GA is called a real-coded GA (RCGA). The novel chromosome representation is designed to produces only feasible solutions which can be used to effectively explore the feasible search space. This first part of the papers focuses on the modelling of the problems and discusses how the novel chromosome representation can be decoded into a feasible solution. The second part will discuss genetic operators and the effectiveness of the RCGA to solve various test bed problems from literature.

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

References

[1] G. Zhang, X. Shao, P. Li, and L. Gao, An Effective Hybrid Particle Swarm Optimization Algorithm for Multi-Objective Flexible Job-Shop Scheduling Problem, Computers & Industrial Engineering, vol. 56 no. 4 (2009), pp.1309-1318.

DOI: 10.1016/j.cie.2008.07.021

[2] 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

[3] 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

[4] M. Yazdani, M. Gholami, M. Zandieh, and M. Mousakhani, A Simulated Annealing Algorithm for Flexible Job-Shop Scheduling Problem, J. Applied Sci, vol. 9 (2009), pp.662-670.

DOI: 10.3923/jas.2009.662.670

[5] X.-h. Xu, L.-l. Zeng, and Y.-w. Fu. "Hybrid Particle Swarm Optimization for Flexible Job-Shop Scheduling Problem and Its Implementation," in Information and Automation (ICIA), 2010 IEEE International Conference on (2010), pp.1155-1159.

DOI: 10.1109/icinfa.2010.5512310

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

[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 I: Modeling," in International Conference on Control, Automation and Robotics. Singapore: World Academy of Science, Engineering and Technology (2012), pp.773-779.

DOI: 10.1109/kst.2013.6512792

[8] 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

[9] M. Yazdani, M. Amiri, and M. Zandieh, Flexible Job-Shop Scheduling with Parallel Variable Neighborhood Search Algorithm, Expert Systems with Applications, vol. 37 no. 1 (2010), pp.678-687.

DOI: 10.1016/j.eswa.2009.06.007

[10] I. Kacem, S. Hammadi, and P. Borne, Approach by Localization and Multiobjective Evolutionary Optimization for Flexible Job-Shop Scheduling Problems, Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on, vol. 32 no. 1 (2002), pp.1-13.

DOI: 10.1109/tsmcc.2002.1009117

[11] 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

[12] 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

[13] G. Zhang, L. Gao, X. Li, and P. Li, "Variable Neighborhood Genetic Algorithm for the Flexible Job Shop Scheduling Problems," in Intelligent Robotics and Applications, C. Xiong, et al., Eds., Springer Berlin / Heidelberg. pp.503-512, (2008).

DOI: 10.1007/978-3-540-88518-4_54

[14] R.M. Marian, L.H.S. Luong, and K. Abhary, A Genetic Algorithm for the Optimisation of Assembly Sequences, Comput. Ind. Eng., vol. 50 no. 4 (2006), pp.503-527.

DOI: 10.1016/j.cie.2005.07.007