A hybrid Tabu Search Algorithm to Cell Formation Problem and its Variants

Authors: Tai-Hsi Wu, Jinn-Yi Yeh, Chin-Chih Chang

Abstract:

Cell formation is the first step in the design of cellular manufacturing systems. In this study, a general purpose computational scheme employing a hybrid tabu search algorithm as the core is proposed to solve the cell formation problem and its variants. In the proposed scheme, great flexibilities are left to the users. The core solution searching algorithm embedded in the scheme can be easily changed to any other meta-heuristic algorithms, such as the simulated annealing, genetic algorithm, etc., based on the characteristics of the problems to be solved or the preferences the users might have. In addition, several counters are designed to control the timing of conducting intensified solution searching and diversified solution searching strategies interactively.

Keywords: Cell formation problem, Tabu search

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1062000

References:

[1] Wemmerlov, U. & N. Hyer, "Research issues in cellular manufacturing," International Journal of Production Research, 25, 413-431, 1987.
[2] Moon, C., & Kim, J., "Genetic algorithm for maximizing the parts flow within cells in manufacturing cell design," Computers & Industrial Engineering, 36, 379-389, 1999.
[3] Ballakur, A. & H.J. Steudel., "A within cell utilization based heuristic for designing cellular manufacturing systems," International Journal of Production Research, 25, 639-655, 1987.
[4] Wang, J., "Formation of machine cells and part families in cellular manufacturing systems using a linear assignment algorithm," Automatica, 39, 1607-1615, 2003
[5] Albadawi, Z., H.A. Bashir & M. Chen, "A mathematical approach for the formation of manufacturing cells," Computers and Industrial Engineering, 48, 3-21, 2005
[6] Lei, D. & Z. Wu, "Tabu search approach based on a similarity coefficient for cell formation in generalized group technology," International Journal of Production Research, 43(19), 4035-4047, 2005.
[7] Wu, T.-H., C. Low & W.-T. Wu, "A tabu search approach to the cell formation problem," International Journal of Advanced Manufacturing Technology, 23, 916-924, 2004.
[8] Wu, T.-H., C.-C. Chang & S.-H. Chung, "A simulated annealing algorithm to manufacturing cell formation problems," Expert Systems with Applications, 34, 1609-1617, 2008.
[9] Yin, Y. & K. Yasuda, "Similarity coefficient methods applied to the cell formation problem: A taxonomy and review," International Journal of Production Economics, 101, 329-352, 2006.
[10] Alhourani, F. & H. Seifoddini, "Machine cell formation for production management in cellular manufacturing systems," International Journal of Production Research, 45(4), 913-934, 2007.
[11] Kusiak, A., "The generalized group technology concept," International Journal of Production Research, 25, 561-569, 1987.
[12] Diallo, M., H. Perreval & A. Quillot, "Manufacturing cell design with flexible routing capability in presence of unreliable machines," International Journal of Production Economics, 74(1-3), 175-182, 2001.
[13] Das, K., R.S. Lashkari & S. Sengupta, "Reliability consideration in the design and analysis of cellular manufacturing systems," International Journal of Production Economics, 105, 243-262, 2007.
[14] Jabal Ameli, M. S. & J. Arkat, "Cell formation with alternative process routings and machine reliability consideration," International Journal of Advanced Manufacturing Technology, 35, 761-768, 2008.
[15] Harhalakis, G., R. Nagi & J.M. Proth, "An efficient heuristic in manufacturing cell formation for group technology applications," International Journal of Production Research, 28, 185-198, 1990.
[16] Nair, G.J. & T.T. Narendran, "CASE: a clustering algorithm for cell formation with sequence data," International Journal of Production Research, 36, 157-179, 1998.
[17] Chandrashekharan, M. P., & Rajagopalan, R, "An ideal seed non-hierarchical clustering algorithm for cellular manufacturing," International Journal of Production Research, 24(2), 451-464, 1986.
[18] Kumar, C.S., & Chandrasekharan, M.P., "Grouping efficacy: A quantitative criterion for goodness of block diagonal forms of binary matrices in group technology," International Journal of Production Research, 28, 233-243, 1990.
[19] Glover, F., "Tabu searchÔÇöpart I," ORSA Journal on Computing, 1(3), 190-206, 1989.
[20] Glover, F., "Tabu searchÔÇöpart II" ORSA Journal on Computing, 2(1), 4-32, 1990.
[21] Kusiak, A. & M. Cho, "Similarity coefficient algorithms for solving the group technology problem," International Journal of Production Research, 30, 2633-2646, 1992.
[22] Won, Y.K. & S.H. Kim, "Multiple criteria clustering algorithm for solving the group technology problem with multiple process routings," Computers and Industrial Engineering, 32, 207-220, 1997.
[23] Wu, T.-H., S.-H. Chung & C.-C. Chang, "Hybrid simulated annealing algorithm with mutation operator to the cell formation problem with alternative process routings," Expert Systems with Applications, 36, 3652-3661, 2009.
[24] Rolland, E, Schilling, D. A., and Current, J. R., "An efficient tabu search procedure for the p-Median problem," European Journal of Operational Research, 96, 329-342, 1996.
[25] Sun, M., Aronson, J. E., McKeown, P. G., and Drinka, D. "A tabu search heuristic procedure for the fixed charge transportation problem," European Journal of Operational Research, 106, 441-456, 1998.