Solving a Dynamic Cell Formation Problem with Machine Cost and Alternative Process Plan by Memetic Algorithms

  • Reza Tavakkoli-Moghaddam
  • Nima Safaei
  • Masoud Babakhani
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3777)


In this paper, we present a new model of a cell formation problem (CFP) for a multi-period planning horizon where the product mix and demand are different in each period, but they are deterministic. As a consequence, the formed cells in the current period may be not optimal for the next period. This evolution results from reformulation of part families, manufacturing cells, and reconfiguration of the CFP as required. Reconfiguration consists of reforming part families, machine groups, and machine relocations. The objective of the model is to determine the optimal number of cells while minimizing the machine amortization/relocation costs as well as the inter-cell movements in each period. In the proposed model, parts have alternative process plans, operation sequence, and produce as batch. The machine capacity is also limited and machine duplication is allowed. The proposed model for real-world instances cannot be solved optimally within a reasonable amount of computational time. Thus, we propose an efficient memetic algorithm (MA) with a simulated annealing-based local search engine for solving the proposed model. This model is solved optimally by the Lingo software then the optimal solution is compared with the MA implementation.


Dynamic cell formation Alternative process plan Machine relocation Memetic Algorithm 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Wemmerlov, U., Hyer, N.: Cellular manufacturing in the US industry: A survey of users. Int. J. of Production research 27, 1511–1530 (1989)CrossRefGoogle Scholar
  2. 2.
    Schaller, J.E., Erenguc, S.S., Vakharia, A.J.: A mathematical approach for integrating the cell design and production planning decision. Int. J. of Production Research 38, 3953–3971 (2000)zbMATHCrossRefGoogle Scholar
  3. 3.
    Chen, M.: A model for integrated production planning in cellular manufacturing systems. Integrated Manufacturing Systems 12, 275–284 (2001)CrossRefGoogle Scholar
  4. 4.
    Foulds, L.R., Neumann, K.: Techniques for machine group formation in manufacturing cells. Mathematical and Computer Modeling 38, 623–635 (2003)zbMATHCrossRefMathSciNetGoogle Scholar
  5. 5.
    Shafer, S., Rogers, D.: A goal programming approach to the cell formation problem. J. of Operations Management 10, 28–43 (1991)CrossRefGoogle Scholar
  6. 6.
    Wilhelm, W., Chou, C., Chang, D.: Integrating design and planning considerations in cell formation. Annals of Operations Research 77, 97–107 (1998)zbMATHCrossRefGoogle Scholar
  7. 7.
    Chen, M.: A mathematical programming model for systems reconfiguration in a dynamic cell formation condition. Annals of Operations Research 77, 109–128 (1998)zbMATHCrossRefGoogle Scholar
  8. 8.
    Monteruiln, B., Laforge, A.: Dynamic layout design given a scenario tree of probable future. Eur. J. of Operational Research 63, 271–286 (1992)CrossRefGoogle Scholar
  9. 9.
    Rogers, G., Bottaci, L.: Modular production systems: A new manufacturing paradigm. J. of Intelligent Manufacturing 8, 147–156 (1997)CrossRefGoogle Scholar
  10. 10.
    Black, J.T.: The design of the factory with a future. McGraw-Hill, New York (1991)Google Scholar
  11. 11.
    Baykasogylu, A., Gindy, N.: A simulated annealing algorithm for dynamic layout problem. Computers and Operation Research 28, 1403–1426 (2001)CrossRefGoogle Scholar
  12. 12.
    Lacksonen, T.A.: Static and dynamic layout problems with varying areas. J. of Operational Research Society 45, 59–69 (1994)zbMATHGoogle Scholar
  13. 13.
    Lacksonen, T.A.: Preprocessing for static and dynamic layout problems. Int. J. of Production Research 35, 1095–1106 (1997)zbMATHCrossRefGoogle Scholar
  14. 14.
    Song, S., Hitomi, K.: Integrating the production planning and cellular layout for flexible cellular manufacturing. Int. J. of Production Planning and Control. 7, 585–593 (1996)CrossRefGoogle Scholar
  15. 15.
    Harhalaks, G., Nagi, R., Proth, J.: An effective heuristic in manufacturing cell formation for group technology applications. Int. J. of Production Research. 28, 185–198 (1990)CrossRefGoogle Scholar
  16. 16.
    Caux, C., Bruniaux, R., Pierreval, H.: Manufacturing cell formation with alternative process plans and machine capacity constraints: a new combined approach. Int. J. of Production Economics. 64, 279–284 (2000)CrossRefGoogle Scholar
  17. 17.
    Kollen, A., Pesch, E.: Genetic local search in combinatorial optimization. Discrete Applied Mathematics and Combinatorial Operation Research and Computer Science 48, 273–284 (1994)Google Scholar
  18. 18.
    Merz, P., Freisleben, B.: Fitness landscapes and memetic algorithm design. In: Corne, D., Dorigo, M., Glover, F. (eds.) New ideas in optimization. McGraw-Hill, London (1999)Google Scholar
  19. 19.
    Moscato, P., Cotta, C.: A gentle introduction to memetic algorithms. In: Glower, F., Kochenberger, G. (eds.) Handbook of metaheuristics, pp. 1–56. Kluwer, Dordrecht (1999)Google Scholar
  20. 20.
    Moscato, P.: On evolution, search, optimization, genetic algorithms and martial arts: toward memetic algorithms, Caltech Concurrent Computation Program, California Institute of Technology, Pasadena, Technical Report 790 (1989)Google Scholar
  21. 21.
    Moscato, P.: A memetic approach for the traveling salesman problem implementation of a computational ecology for combinatorial optimization on message-passing systems. In: Valero, M., Onate, E., Jane, M., Larriba, J.L., Suarez, B. (eds.) Parallel computing and transporter Applications, pp. 176–177. IOS Press, Amsterdam (1992)Google Scholar
  22. 22.
    Dawkins, R.: The selfish gene. Oxford University Press, Oxford (1976)Google Scholar
  23. 23.
    Moscato, P., Norman, M.G.: A memetic approach for the Traveling Salesman Problem implementation of a computational ecology for combinatorial optimization on message-passing systems. In: Valero, M., Onate, E., Jane, M., Larriba, J.L., Suarez, B. (eds.) Parallel computing and Transporter Applications, pp. 177–186. IOS Press, Amsterdam (1992)Google Scholar
  24. 24.
    Berretta, R.E., Moscato, P.: The number partitioning problem: An open challenge for evolutionary computation? In: Corne, D., Glover, F., Dorigo, M. (eds.) New ideas in optimization, ch. 17, pp. 261–278. McGraw-Hill, Maidenhead (1999)Google Scholar
  25. 25.
    Holstein, D., Moscato, P.: Memetic algorithms using guided local search: A case study. In: Corne, D., Glover, F., Dorigo, M. (eds.) New ideas in optimization, ch. 15, pp. 235–244. McGraw-Hill, Maidenhead (1999)Google Scholar
  26. 26.
    Merz, P.: Analysis of gene expression profiles: an application of memetic algorithms to the minimum sum-of-squares clustering problem. BioSystems 72, 99–109 (2003)CrossRefGoogle Scholar
  27. 27.
    Merz, P., Katayama, K.: Memetic algorithms for the unconstrained binary quadratic programming problem. BioSystems 78, 99–118 (2004)CrossRefGoogle Scholar
  28. 28.
    Berrettaa, R., Rodrigues, L.F.: A memetic algorithm for a multistage capacitated lot-sizing problem. Int. J. Production Economics 87, 67–81 (2004)CrossRefGoogle Scholar
  29. 29.
    Lacomme, P., Prins, C., Ramdane, W.: cherif, Competitive memetic algorithms for arc routing problems. Annals of Operations Research 131, 159–185 (2004)zbMATHCrossRefMathSciNetGoogle Scholar
  30. 30.
    Buriol, L., Franca, P.M., Moscato, P.: A New Memetic Algorithm for the asymmetric traveling salesman problem. J. of Heuristics 10, 483–506 (2004)zbMATHCrossRefGoogle Scholar
  31. 31.
    Tavakkoli-Moghaddam, R., Aryanezhad, M.B., Safaei, N., Azaron, A.: Solving a dynamic cell formation problem using metaheuristics. Applied Mathematics and Computation (Article in press) (2005)Google Scholar
  32. 32.
    Glover, F., Greenberg, H.: New approach heuristic search: a bilateral linkage with artificial intelligence. Eur. J. Oper. Res. 39(2), 119–130 (1989)zbMATHCrossRefMathSciNetGoogle Scholar
  33. 33.
    Krasnogor, N.: Studies on the theory and design space of memetic algorithms. Ph.D. dissertation, Univ. of the West of England, Bristol, U.K. (2002)Google Scholar
  34. 34.
    Gen, M., Cheng, R.: Genetic algorithms and engineering design. Wiley, New York (1997)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Reza Tavakkoli-Moghaddam
    • 1
  • Nima Safaei
    • 2
  • Masoud Babakhani
    • 2
  1. 1.Department of Industrial Engineering, Faculty of EngineeringUniversity of TehranTehranIran
  2. 2.Department of Industrial EngineeringIran University of Science and TechnologyTehranIran

Personalised recommendations