Solving Part Type Selection and Loading Problem in Flexible Manufacturing System Using Real Coded Genetic Algorithms – Part I: Modeling

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

Abstract:

This paper and its companion (Part 2) deal 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. The complexity of the problems is harder when flexibilities of operations such as the possibility of operation processed on alternative machines with alternative tools are considered. 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. These real numbers can be converted into part type sequence and machines that are used to process the part types. This first part of the papers focuses on the modeling of the problems and discussing how the novel chromosome representation can be applied to solve the problems. The second part will discuss the effectiveness of the RCGA to solve various test bed problems.

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.1082451

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] Y.Z. Mehrjerdi, "A Decision-Making Model for Flexible Manufacturing System," Assembly Automation, vol. 29, no. 1, pp. 32-40, 2009.
[5] 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.
[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] 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.
[8] 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.
[9] 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.
[10] 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.
[11] 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.
[12] 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.
[13] W. Shen, "Genetic Algorithms in Agent-Based Manufacturing Scheduling Systems," Integr. Comput.-Aided Eng., vol. 9, no. 3, pp. 207-217, 2002.
[14] 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.
[15] M. Gen and R. Cheng, Genetic Algorithms and Engineering Optimization, New York: John Wiley & Sons, Inc., 2000.
[16] F. Rothlauf, Representations for Genetic and Evolutionary Algorithms, Berlin Heidelberg: Springer, 2006.
[17] M. Lozano and F. Herrera, "Fuzzy Adaptive Genetic Algorithms: Design, Taxonomy," Soft Computing, vol. 7, pp. 545-562, 2003.
[18] 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.
[19] 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.
[20] 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.
[21] 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.
[22] 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.
[23] 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.
[24] 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.
[25] 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.
[26] 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.
[27] 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.
[28] 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.
[29] M. Gen and R. Cheng, Genetic Algorithms and Engineering Design, New York: John Wiley & Sons, Inc., 1997.
[30] 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.
[31] 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.
[32] 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.
[33] N.J. Radcliffe, "Equivalence Class Analysis of Genetic Algorithms," Complex Systems, vol. 5, no. 2, pp. 183-205, 1991.
[34] 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.