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

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.

Authors:

• Tai-Hsi Wu
• Jinn-Yi Yeh
• Chin-Chih Chang

Keywords:

• Cell formation problem
• Tabu search

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.