Solving Part Type Selection and Loading Problem in Flexible Manufacturing System Using Real Coded Genetic Algorithms – Part I: Modeling
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.
[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.
[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.
@article{"International Journal of Mechanical, Industrial and Aerospace Sciences:63157", author = "Wayan F. Mahmudy and Romeo M. Marian and Lee H. S. Luong", title = "Solving Part Type Selection and Loading Problem in Flexible Manufacturing System Using Real Coded Genetic Algorithms – Part I: Modeling", 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", volume = "6", number = "9", pages = "2012-7", }
