×

Multi-objective FMS process planning with various flexibilities using a symbiotic evolutionary algorithm. (English) Zbl 1201.90104

Summary: This paper presents an evolutionary algorithm, called the multi-objective symbiotic evolutionary algorithm (MOSEA), to solve a multi-objective FMS process planning (MFPP) problem with various flexibilities. The MFPP problem simultaneously considers four types of flexibilities related to machine, tool, sequence, and process and takes into account three objectives: balancing the machine workload, minimizing part movements, and minimizing tool changes. The MOSEA is modeled as a two-leveled structure to find a set of well-distributed solutions close to the true Pareto optimal solutions. To promote the search capability of such solutions, two main processes imitating symbiotic evolution and endosymbiotic evolution are introduced, together with an elitist strategy and a fitness sharing scheme. Evolutionary components suitable for the MFPP problem are provided. With a variety of test-bed problems, the performance of the proposed MOSEA is compared with those of existing multi-objective evolutionary algorithms. The experimental results show that the MOSEA is promising in solution convergence and diversity.

MSC:

90B50 Management decision making, including multiple objectives
90B30 Production models
90C59 Approximation methods and heuristics in mathematical programming

Software:

SPEA2; EMOO; PAES
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Guerrero, F.; Lozano, S.; Koltai, T.; Larraneta, J., Machine loading and part type selection in flexible manufacturing systems, International Journal of Production Research, 37, 1303-1317 (1999) · Zbl 0949.90509
[2] Stecke, K. E., Formulation and solution of nonlinear integer production planning problem for flexible manufacturing systems, Management Science, 29, 273-288 (1983) · Zbl 0517.90035
[3] Das, K.; Baki, M. F.; Li, X., Optimization of operation and changeover time for production planning and scheduling in a flexible manufacturing system, Computers & Industrial Engineering, 56, 1, 283-293 (2009)
[4] Maimon, O. Z.; Gershwin, S. B., Dynamic scheduling and routing for flexible manufacturing systems that have unreliable machines, Operations Research, 36, 279-292 (1988)
[5] Stecke, K. E.; Raman, N., FMS planning decisions, operating flexibilities, and system performance, IEEE Transactions on Engineering Management, 42, 82-90 (1995)
[6] Bilge, Ű.; Firat, M.; Albey, E., A parametric fuzzy logic approach to dynamic part routing under full routing flexibility, Computers & Industrial Engineering, 55, 1, 15-33 (2008)
[7] Modi, B. K.; Shanker, K., Models and solution approaches for part movement minimization and load balancing in FMS with machine, tool and process plan flexibilities, International Journal of Production Research, 33, 1791-1816 (1994) · Zbl 0909.90164
[8] Kumar, N.; Shanker, K., A genetic algorithm for FMS part type selection and machine loading, International Journal of Production Research, 38, 3861-3887 (2000) · Zbl 1094.90531
[9] Tiwari, M. K.; Vidyarthi, N. K., Solving machine loading problems in a flexible manufacturing system using a genetic algorithm based heuristic approach, International Journal of Production Research, 38, 3357-3384 (2000) · Zbl 1094.90548
[10] Bilge Ű, Albey E. A hierarchical approach to FMS planning and control with simulation-based capacity anticipation. International Journal of Production Research 2010; doi:10.1080/00207543.2010.482570; Bilge Ű, Albey E. A hierarchical approach to FMS planning and control with simulation-based capacity anticipation. International Journal of Production Research 2010; doi:10.1080/00207543.2010.482570
[11] Grieco, A.; Semeraro, Q.; Tolio, T., A review of different approaches to the FMS loading problem, International Journal of Flexible Manufacturing Systems, 13, 4, 361-384 (2001)
[12] Chen, J.-H.; Ho, S.-Y., A novel approach to production planning of flexible manufacturing systems using an efficient multi-objective genetic algorithm, International Journal of Machine Tools & Manufacture, 45, 949-957 (2005)
[13] Coello, C. A.C.; Lamont, G. B.; Veldhuizen, D. A.V., Evolutionary algorithms for solving multi-objective problems (2007), Springer: Springer New York · Zbl 1142.90029
[14] Coello, CAC. List of references on evolutionary multiobjective optimization. Available at: http://www.lania.mx/∼ccoello/EMOO/EMOObib.html; Coello, CAC. List of references on evolutionary multiobjective optimization. Available at: http://www.lania.mx/∼ccoello/EMOO/EMOObib.html
[15] Potter MA. The design and analysis of a computational model of cooperative coevolution. PhD dissertation, George Mason University; 1997.; Potter MA. The design and analysis of a computational model of cooperative coevolution. PhD dissertation, George Mason University; 1997.
[16] Kim, J. Y.; Kim, Y.; Kim, Y. K., An endosymbiotic evolutionary algorithm for optimization, Applied Intelligence, 15, 2, 117-130 (2001) · Zbl 0981.68137
[17] Kim, Y. K.; Park, K.; Ko, J., A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling, Computers & Operations Research, 30, 8, 1151-1171 (2003) · Zbl 1049.90026
[18] Kim, J. Y.; Kim, Y. K., Multileveled symbiotic evolutionary algorithm: application to FMS loading problems, Applied Intelligence, 22, 3, 233-249 (2005) · Zbl 1084.68100
[19] Margulis, L., Origin of eukaryotic cells (1970), Yale University Press: Yale University Press New Haven, CT
[20] Ho, Y. C.; Moodie, C. L., Solving cell formation problems in a manufacturing environment with flexible processing and routing capabilities, International Journal of Production Research, 34, 2901-2923 (1996) · Zbl 0929.90020
[21] Schaffer JD. Multiple objective optimization with vector evaluated genetic algorithms. In: Proceedings of the first international conference on genetic algorithms, Lawrence Erlbaum; 1985. p. 93-100.; Schaffer JD. Multiple objective optimization with vector evaluated genetic algorithms. In: Proceedings of the first international conference on genetic algorithms, Lawrence Erlbaum; 1985. p. 93-100.
[22] Goldberg, D. E., Genetic algorithms in search, optimization, and machine learning (1989), Addison-Wesley: Addison-Wesley Massachusetts · Zbl 0721.68056
[23] Fonseca CM, Fleming PJ. Genetic algorithm for multiobjective optimization, formulation, discussion and generalization. In: Forrest S, editor. Genetic algorithms: proceeding of the fifth international conference, 1993. p. 416-23.; Fonseca CM, Fleming PJ. Genetic algorithm for multiobjective optimization, formulation, discussion and generalization. In: Forrest S, editor. Genetic algorithms: proceeding of the fifth international conference, 1993. p. 416-23.
[24] Srinivas, N.; Deb, K., Multiobjective optimization using nondominated sorting in genetic algorithms, Evolutionary Computation, 2, 3, 221-248 (1994)
[25] Horn, J.; Nafpliotis, N.; Goldberg, D. E., A niched Pareto genetic algorithm for multiobjective optimization, IEEE international conference on evolutionary Computation, 1, 82-87 (1994)
[26] Zitzler, E.; Thiele, L., Mutlobjective evolutionary algorithms: a comparative case study and the strength Pareto approach, IEEE Transactions on Evolutionary Computation, 3, 4, 257-271 (1999)
[27] Knowles JD, Corne DW. The Pareto archived evolution strategy: a new baseline algorithm for multi-objective optimization. In: IEEE international conference on evolutionary computation, 1999. p. 98-105.; Knowles JD, Corne DW. The Pareto archived evolution strategy: a new baseline algorithm for multi-objective optimization. In: IEEE international conference on evolutionary computation, 1999. p. 98-105.
[28] Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation, 6, 2, 182-197 (2002)
[29] Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the strength Pareto evolutionary algorithm. Technical Report 103, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich, Gloriastrasse 35, CH-8092 Zurich, Switzerland, 2001.; Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the strength Pareto evolutionary algorithm. Technical Report 103, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich, Gloriastrasse 35, CH-8092 Zurich, Switzerland, 2001.
[30] Deb, K.; Mohan, M.; Mishra, S., Evaluating the ε-dominance based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions, Evolutionary Computation, 13, 4, 501-525 (2005)
[31] Shi, C.; Yan, Z.; Shi, Z.; Zhang, L., A fast multi-objective evolutionary algorithm based on a tree structure, Applied Soft Computing, 10, 2, 468-480 (2010)
[32] Zitzler, E.; Thiele, L.; Bader, J., SPAM: Set preference algorithm for multiobjective optimization, (Rudolph; etal., Parallel problem solving from nature (PPSN X). Lecture notes in computer science, vol. 5199 (2008), Springer: Springer Dortmund), 847-858
[33] Purshouse, R. C.; Fleming, P. J., On the evolutionary optimization of many conflicting objectives, IEEE Transactions on Evolutionary Algorithms, 11, 6, 770-784 (2007)
[34] Parmee, I. C.; Watson, A. H., Preliminary airframe design using co-evolutionary multiobjective genetic algorithms, (Banzhaf; etal., Proceedings of the genetic and evolutionary computation conference (GECCO’99), vol. 2 (1999), Morgan Kaufmann), 1657-1665
[35] Keerativuttiumrong, N.; Chaiyaratana, N.; Varavithya, V., Multi-objective co-operative co-evolutionary genetic algorithm, (Merelo, Guervós, Parallel problem solving from nature (PPSN VII). Lecture notes in computer science, vol. 2439 (2002), Springer), 288-297
[36] Iorio, A. W.; Li, X., A cooperative coevolutionary multiobjective algorithm using non-dominated sorting, (Deb; etal., Proceedings of the genetic and evolutionary computation conference (GECCO’2004): part I. Lecture notes in computer science, vol. 3102 (2004), Springer), 537-548
[37] Kleeman MP, Lamont GB. Coevolutionary multi-objective EAs: the next frontier? In: IEEE Congress on evolutionary computation (CEC’2006), 2006. p. 6190-9.; Kleeman MP, Lamont GB. Coevolutionary multi-objective EAs: the next frontier? In: IEEE Congress on evolutionary computation (CEC’2006), 2006. p. 6190-9.
[38] Kim, Y. K.; Kim, J. Y.; Kim, Y., A coevolutionary algorithm for balancing and sequencing in mixed model assembly lines, Applied Intelligence, 13, 3, 247-258 (2000)
[39] Eshelmam LJ, Caruana RA, Schaffer JD. Biases in the crossover landscape. In: Proceedings of the third international conference on genetic algorithms, 1989. p.10-9.; Eshelmam LJ, Caruana RA, Schaffer JD. Biases in the crossover landscape. In: Proceedings of the third international conference on genetic algorithms, 1989. p.10-9.
[40] Shin KS, Park J-O, Kim YK. Test-bed problems for multi-objective FMS process planning using multi-objective symbiotic evolutionary algorithm. Available at: http://syslab.chonnam.ac.kr/links/MO_FMS_PP_MOSEA.doc; Shin KS, Park J-O, Kim YK. Test-bed problems for multi-objective FMS process planning using multi-objective symbiotic evolutionary algorithm. Available at: http://syslab.chonnam.ac.kr/links/MO_FMS_PP_MOSEA.doc
[41] Zitzler, E.; Deb, K.; Thiele, L., Comparison of multiobjective evolutionary algorithms: empirical results, Evolutionary Computation, 8, 2, 173-195 (2000)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.