Modeling and Optimization of Part Type Selection and Loading Problem in Flexible Manufacturing System Using Real Coded Genetic Algorithms

Authors: Wayan F. Mahmudy, Romeo M. Marian, Lee H. S. Luong

Abstract:

 This paper deals with modeling and optimization of two NP-hard problems in production planning of flexible manufacturing system (FMS), part type selection problem and loading problem. The part type selection problem and the loading problem are strongly related and heavily influence the system’s efficiency and productivity. These problems have been modeled and solved simultaneously by using real coded genetic algorithms (RCGA) which uses an array of real numbers as chromosome representation. The novel proposed chromosome representation produces only feasible solutions which minimize a computational time needed by GA to push its population toward feasible search space or repair infeasible chromosomes. The proposed RCGA improves the FMS performance by considering two objectives, maximizing system throughput and maintaining the balance of the system (minimizing system unbalance). The resulted objective values are compared to the optimum values produced by branch-and-bound method. The experiments show that the proposed RCGA could reach near optimum solutions in a reasonable amount of time.

Keywords: Flexible manufacturing system, production planning, part type selection problem, loading problem, real-coded genetic algorithm.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1336322

References:

[1] F.T.S. Chan and H.K. Chan, "A Comprehensive Survey and Future Trend of Simulation Study on Fms Scheduling," Journal of Intelligent Manufacturing, vol. 15, no. 1, pp. 87-102, 2004.
[2] I. Badr, "An Agent-Based Scheduling Framework for Flexible Manufacturing Systems," International Journal of Computer, Information, and Systems Science, and Engineering, vol. 2, no. 2, pp. 123-129, 2008.
[3] N. Kumar and K. Shanker, "A Genetic Algorithm for Fms Part Type Selection and Machine Loading," International Journal of Production Research, vol. 38, no. 16, pp. 3861-3887, 2000.
[4] Z. Binghai, X. Lifeng, and C. Yongshang, "A Heuristic Algorithm to Batching and Loading Problems in a Flexible Manufacturing System," The International Journal of Advanced Manufacturing Technology, vol. 23, no. 11, pp. 903-908, 2004.
[5] J. Venkateswaran, Y.-J. Son, and A. Jones. "Hierarchical Production Planning Using a Hybrid System Dynamic-Discrete Event Simulation Architecture," in Proceedings of the 2004 Winter Simulation Conference, 2004.
[6] M. Ben-Daya, "Fms Short Term Planning Problems: A Review," in Manufacturing Research and Technology, A. Raouf and M. Ben-Daya, Eds., Elsevier. p. 113-139, 1995.
[7] K.E. Stecke, "Design, Planning, Scheduling, and Control Problems of Flexible Manufacturing Systems," Annals of Operations Research, vol. 3, no. 1, pp. 1-12, 1985.
[8] S. Özpeynirci and M. Azizoglu, "Bounding Approaches for Operation Assignment and Capacity Allocation Problem in Flexible Manufacturing Systems," Computers & Operations Research, vol. 36, no. 9, pp. 2531-2540, 2009.
[9] S. Bilgin and M. Azizoglu, "Capacity and Tool Allocation Problem in Flexible Manufacturing Systems," The Journal of the Operational Research Society, vol. 57, no. 6, pp. 670-681, 2006.
[10] F.T.S. Chan and R. Swarnkar, "Ant Colony Optimization Approach to a Fuzzy Goal Programming Model for a Machine Tool Selection and Operation Allocation Problem in an Fms," Robotics and Computer-Integrated Manufacturing, vol. 22, no. 4, pp. 353-362, 2006.
[11] J.-H. Chen and S.-Y. Ho, "A Novel Approach to Production Planning of Flexible Manufacturing Systems Using an Efficient Multi-Objective Genetic Algorithm," International Journal of Machine Tools and Manufacture, vol. 45, no. 7–8, pp. 949-957, 2005.
[12] R. Swarnkar and M.K. Tiwari, "Modeling Machine Loading Problem of Fmss and Its Solution Methodology Using a Hybrid Tabu Search and Simulated Annealing-Based Heuristic Approach," Robotics and Computer-Integrated Manufacturing, vol. 20, no. 3, pp. 199-209, 2004.
[13] A.K. Choudhary, M.K. Tiwari, and J.A. Harding, "Part Selection and Operation-Machine Assignment in a Flexible Manufacturing System Environment: A Genetic Algorithm with Chromosome Differentiation-Based Methodology," Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, vol. 220, no. 5, pp. 677-694, 2006.
[14] S. Biswas and S. Mahapatra, "Modified Particle Swarm Optimization for Solving Machine-Loading Problems in Flexible Manufacturing Systems," The International Journal of Advanced Manufacturing Technology, vol. 39, no. 9, pp. 931-942, 2008.
[15] S.G. Ponnambalam and L.S. Kiat, "Solving Machine Loading Problem in Flexible Manufacturing Systems Using Particle Swarm Optimization," World Academy of Science, Engineering and Technology, vol. 39, 2008.
[16] A. Prakash, N. Khilwani, M.K. Tiwari, and Y. Cohen, "Modified Immune Algorithm for Job Selection and Operation Allocation Problem in Flexible Manufacturing Systems," Adv. Eng. Softw., vol. 39, no. 3, pp. 219-232, 2008.
[17] M.T. Tabucanon, D.N. Batanov, and S. Basu, "Using Simulation to Evaluate the Batching Approach to Part Type Selection in Flexible Manufacturing Systems," Integrated Manufacturing Systems, vol. 9, no. 1, pp. 5-14, 1998.
[18] H.-W. Kim, J.-M. Yu, J.-S. Kim, H.-H. Doh, D.-H. Lee, and S.-H. Nam, "Loading Algorithms for Flexible Manufacturing Systems with Partially Grouped Unrelated Machines and Additional Tooling Constraints," The International Journal of Advanced Manufacturing Technology, vol. 58, no. 5, pp. 683-691, 2012.
[19] K. Seok Shin, J.O. Park, and Y. Keun Kim, "Multi-Objective Fms Process Planning with Various Flexibilities Using a Symbiotic Evolutionary Algorithm," Computers and Operations Research, vol. 38, no. 3, pp. 702-712, 2011.
[20] M.K. Tiwari, S. Kumar Jha, and R. Bardhan Anand, "Operation Allocation and Part Type Selection in E-Manufacturing: An Auction Based Heuristic Supported by Agent Technology," Robotics and Computer-Integrated Manufacturing, vol. 26, no. 4, pp. 312-324, 2010.
[21] M.K. Tiwari, S. Kumar, S. Kumar, Prakash, and R. Shankar, "Solving Part-Type Selection and Operation Allocation Problems in an Fms: An Approach Using Constraints-Based Fast Simulated Annealing Algorithm," IEEE Transaction on Systems, Man, and Cybernetics—Part A: Systems and Humans, vol. 36, no. 6, pp. 1170-1184, 2006.
[22] W. Shen, "Genetic Algorithms in Agent-Based Manufacturing Scheduling Systems," Integr. Comput.-Aided Eng., vol. 9, no. 3, pp. 207-217, 2002.
[23] M. Tiwari, J. Saha, and S. Mukhopadhyay, "Heuristic Solution Approaches for Combined-Job Sequencing and Machine Loading Problem in Flexible Manufacturing Systems," The International Journal of Advanced Manufacturing Technology, vol. 31, no. 7, pp. 716-730, 2007.
[24] M. Gen and R. Cheng, Genetic Algorithms and Engineering Optimization, New York: John Wiley & Sons, Inc., 2000.
[25] F. Rothlauf, Representations for Genetic and Evolutionary Algorithms, Berlin Heidelberg: Springer, 2006.
[26] M. Lozano and F. Herrera, "Fuzzy Adaptive Genetic Algorithms: Design, Taxonomy," Soft Computing, vol. 7, pp. 545–562, 2003.
[27] 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. 773-779, 2012.
[28] 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. 778-782, 2012.
[29] M. Yogeswaran, S.G. Ponnambalam, and M.K. Tiwari, "An Efficient Hybrid Evolutionary Heuristic Using Genetic Algorithm and Simulated Annealing Algorithm to Solve Machine Loading Problem in Fms," International Journal of Production Research, vol. 47, no. 19, pp. 5421-5448, 2009.
[30] M. Denizell and S. Sayin, "Part-Types Selection in Flexible Manufacturings Systems: A Bicriteria Approach with Due Dates," Journal of the Operational Research Society, vol. 49, pp. 659-669, 1998.
[31] D. Pacciarelli. "Loading Parts and Tools in a Flexible Manufacturing System," in Proceedings of the 6th IEEE Mediterranean Conference on Control and Systems. Alghero, Italy, 1998.
[32] S.K. Mukhopadhyay, S. Midha, and V.M. Krishna, "A Heuristic Procedure for Loading Problems in Flexible Manufacturing Systems," International Journal of Production Research, vol. 30, no. 9, pp. 2213, 1992.
[33] M. Liang, "Integrating Machining Speed, Part Selection and Machine Loading Decisions in Flexible Manufacturing Systems," Computers & Industrial Engineering, vol. 26, no. 3, pp. 599-608, 1994.
[34] M. Gen and R. Cheng, Genetic Algorithms and Engineering Design, New York: John Wiley & Sons, Inc., 1997.
[35] 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, pp. 503-527, 2006.
[36] F. Herrera, M. Lozano, and J.L. Verdegay, "Tackling Real-Coded Genetic Algorithms: Operators and Tools for Behavioural Analysis," Artificial Intelligence Review, vol. 12, pp. 265–319, 1998.
[37] R.M. Marian, L. Luong, and S.D. Dao, "Hybrid Genetic Algorithm Optimisation of Distribution Networks—a Comparative Study," in Intelligent Control and Innovative Computing, S.I. Ao, O. Castillo, and X. Huang, Eds., Springer US. p. 109-122, 2012.
[38] N.J. Radcliffe, "Equivalence Class Analysis of Genetic Algorithms," Complex Systems, vol. 5, no. 2, pp. 183–205, 1991.
[39] H. M¨uhlenbein and D. Schlierkamp-Voosen, "Predictive Models for the Breeder Genetic Algorithm; Continuous Parameter Optimization," Evolutionary Computation vol. 1, pp. 25–49, 1993.
[40] R.M. Marian, L.H.S. Luong, and R. Akararungruangkul, "Optimisation of Distribution Networks Using Genetic Algorithms. Part 2: The Genetic Algorithm and Genetic Operators," International Journal of Manufacturing Technology and Management, vol. 15, no. 1, pp. 84-101, 2008.