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

This paper presents modeling and optimization of two NP-hard problems in flexible manufacturing system (FMS), part type selection problem and loading problem. Due to the complexity and extent of the problems, the paper was split into two parts. The first part of the papers has discussed the modeling of the problems and showed how the real coded genetic algorithms (RCGA) can be applied to solve the problems. This second part discusses the effectiveness of the 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.

• Wayan F. Mahmudy
• Romeo M. Marian
• Lee H. S. Luong

• Flexible manufacturing system
• production planning
• part type selection problem
• loading problem
• real-coded genetic algorithm

[1] D.J. Parrish, Flexible Manufacturing, Oxford: Butterworth-Heinemann,
1993.
[2] S. Turgay, "Agent-Based Fms Control," Robotics and Computer-
Integrated Manufacturing, vol. 25, no. 2, pp. 470-480, 2009.
[3] H.W. Kim, J.S. Kim, J.M. Yu, H.H. Doh, D.H. Lee, and S.H. Nam.
"Loading Algorithms for Flexible Manufacturing Systems with Partially
Grouped Unrelated Machines and Tooling Constraints," in Computer
Communication Control and Automation (3CA), 2010 International
Symposium on. 326-329, 2010.
[4] W.W. Luggen, Flexible Manufacturing Cells and Systems, Englewood
Cliffs, N.J: Prentice Hall, 1991.
[5] V. Malhotra, T. Raj, and A. Arora, "Excellent Techniques of
Manufacturing Systems: Rms and Fms," International Journal of
Engineering Science and Technology, vol. 2, no. 3, pp. 137-142, 2010.
[6] G. Abaza, I. Badr, P. Goehner, and S. Jeschke. "Extending an Agent-
Based Fms Scheduling Approach with Parallel Genetic Algorithms," in
IECON 2010 - 36th Annual Conference on IEEE Industrial Electronics
Society. 2689-2694, 2010.
[7] 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.
[8] 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.
[9] H.T.N.I.K. Nejad, N. Sugimura, K. Iwamura, and Y. Tanimizu,
"Integrated Dynamic Process Planning and Scheduling in Flexible
Manufacturing Systems Via Autonomous Agents," Journal of Advanced
Mechanical Design, Systems, and Manufacturing, vol. 2, no. 4, pp. 719-
734, 2008.
[10] A.H.R. Zaied, "Quantitative Models for Planning and Scheduling of
Flexible Manufacturing System," Emirates Journal for Engineering
Research, vol. 13, no. 2, pp. 11-19, 2008.
[11] 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. 193-198, 2005.
[12] 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.
[13] 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.
[14] 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.
[15] 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.
[16] 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.
[17] 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.
[18] 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.
[19] 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.
[20] 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.
[21] 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.
[22] 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.
[23] 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.
[24] 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.
[25] 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.
[26] 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.
[27] W. Shen, "Genetic Algorithms in Agent-Based Manufacturing
Scheduling Systems," Integr. Comput.-Aided Eng., vol. 9, no. 3, pp.
207-217, 2002.
[28] M. Lozano and F. Herrera, "Fuzzy Adaptive Genetic Algorithms:
Design, Taxonomy," Soft Computing, vol. 7, pp. 545-562, 2003.
[29] 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.
[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.