×

Ant colony optimization algorithm to the inter-cell layout problem in cellular manufacturing. (English) Zbl 1067.90035

Summary: The inter-cell layout problem is discussed and a mathematical formulation for material flow between the cells is presented. The problem is modeled as a quadratic assignment problem (QAP). An ant algorithm is developed to solve the formulated problem. The performance of the proposed ant algorithm is compared to the facility layout algorithms such as H63, HC63-66, CRAFT and Bubble Search as well as other existing ant colony implementations for QAP such as FANT, HAS-QAP, MMAS-QAP\(_{2-opt}\), and ANTS algorithms. The experimental results show that the proposed ant algorithm performs significantly better than the facility layout algorithms. Also, our experimental results reveal that the proposed ant algorithm is effective and efficient as compared to other existing ant algorithms.

MSC:

90B30 Production models
90B80 Discrete location and assignment

Software:

FANT; HAS-QAP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Amirahmadi, F.; Choobineh, F., Identifying the composition of cellular manufacturing system, International Journal of Production Research, 34, 9, 2471-2488 (1996) · Zbl 0930.90018
[2] Bazargan-Lari, M., Layout designs in cellular manufacturing, European Journal of Operational Research, 112, 258-272 (1999) · Zbl 0937.90021
[3] Carraresi, P.; Malucelli, F., A new lower bound for the quadratic assignment problem, Operations Research, 40, supp. 1, S22-S27 (1992) · Zbl 0755.90083
[4] Colorni, A.; Dorigo, M.; Maniezzo, V.; Trubian, M., Ant system for job-shop scheduling, JORBEL-Belgian Journal of Operations Research Statistics and Computer Science, 34, 1, 39-53 (1994) · Zbl 0814.90047
[5] Connolly, D. T., An improved annealing scheme for the QAP, European Journal of Operational Research, 46, 93-100 (1990) · Zbl 0715.90079
[6] Cung, V.-D.; Mautor, T.; Michelon, P.; Tavares, A., A scatter search based approach for the quadratic assignment problem, (Baeck, T.; Michalewicz, Z.; Yao, X., Proceedings of ICEC’97 (1997), IEEE Press), 165-170
[7] Dorigo, M.; Gambardella, L. M., Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, 1, 1, 53-66 (1997)
[8] Dorigo, M.; Maniezzo, V.; Colorni, A., The ant system: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man and Cybernetics, 1, 26, 29-41 (1996)
[9] Fleurent, C.; Ferland, J., Genetic hybrids for the quadratic assignment problem, DIMACS Series in Mathematics and Theoretical Computer Science, 16, 190-206 (1994) · Zbl 0817.90056
[10] Gambardella, L. M.; Taillard, E. D.; Dorigo, M., Ant colonies for the QAP, Journal of Operational Research Society, 50, 167-176 (1999) · Zbl 1054.90621
[11] Gilmore, P., Optimal and suboptimal algorithms for the quadratic assignment problem, Journal of SIAM, 10, 305-313 (1962) · Zbl 0118.15101
[12] Kouvelis, P.; Chiang, W.; Yu, G., Optimal algorithms for row layout problems in automated manufacturing systems, IIE Transactions, 27, 1, 99-104 (1995)
[13] Kusiak, A.; Heragu, S. S., The facility layout problem, European Journal of Operational Research, 29, 229-251 (1987) · Zbl 0612.90035
[14] Lawler, E., The quadratic assignment problem, Management Science, 9, 586-599 (1963) · Zbl 0995.90579
[15] Logendran, R.; Chang, S. K., Manufacturing cell formation in the presence of flexible cell locations and material transporters, Computers and Industrial Engineering, 33, 545-548 (1997)
[16] Maniezzo, V., Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem, INFORMS Journal on Computing, 11, 358-369 (1999) · Zbl 1034.90526
[17] Maniezzo, V.; Colorni, A., The ant system applied to the quadratic assignment problem, IEEE Transactions on Knowledge and Data Engineering, 11, 5, 769-778 (1999)
[18] Nugent, C. E.; Vollman, T. E.; Ruml, J., An experimental comparison of techniques for the assignment of facilities to locations, Operations Research, 16, 150-173 (1968)
[19] Resende, M. G.C.; Ramakrishnan, K. G.; Drezner, Z., Computing lower bounds for the quadratic assignment problem with an interior point algorithm for linear programming, Operations Research, 43, 781-791 (1995) · Zbl 0843.90068
[20] Sahni, S.; Gonzalez, T., P-complete approximation problems, Journal of ACM, 23, 555-565 (1976) · Zbl 0348.90152
[21] Sarker, B. R.; Yu, J., A two-phase procedure for duplicating bottleneck machines in linear layout, cellular manufacturing system, International Journal of Production Research, 32, 9, 2049-2066 (1994) · Zbl 0904.90077
[22] Shafer, S. M.; Kern, G. M.; Wei, J. C., A mathematical programming approach for dealing with exceptional elements in cellular manufacturing, International Journal of Production Research, 30, 5, 1029-1036 (1992)
[23] Shankar, R.; Vrat, P., Some design issues in cellular manufacturing using the fuzzy programming approach, International Journal of Production Research, 37, 11, 2545-2563 (1999) · Zbl 0949.90566
[24] Stützle, T.; Dorigo, M., ACO algorithms for the quadratic assignment problem, (Corne, D.; Dorigo, M.; Glover, F., New Ideas in Optimization (1999), McGraw-Hill) · Zbl 0972.90056
[25] Stützle, T.; Hoos, H. H., MAX-MIN ant system, Future Generation Computer Systems, 16, 889-914 (2000)
[26] Taillard, E. D., Robust taboo search for the quadratic assignment problem, Parallel Computing, 17, 443-455 (1991)
[27] Taillard, E. D., Comparison of iterative searches for the quadratic assignment problem, Location Science, 3, 87-105 (1995) · Zbl 0916.90235
[28] Taillard, E.D., Gambardella, L.M., 1997. Adaptive memories for the quadratic assignment problem, Technical Report IDSIA-87-97, IDSIA, Lugano, Switzerland; Taillard, E.D., Gambardella, L.M., 1997. Adaptive memories for the quadratic assignment problem, Technical Report IDSIA-87-97, IDSIA, Lugano, Switzerland
[29] Tate, D. M.; Smith, A. E., A genetic approach to the quadratic assignment problem, Computers and Operations Research, 22, 1, 73-83 (1995) · Zbl 0812.90099
[30] Urban, T. L.; Chiang, W.-C.; Russell, R. A., The integrated machine allocation and layout problem, International Journal of Production Research, 38, 13, 2911-2930 (2000)
[31] Vollmann, T. E.; Buffa, E. S., The facilities layout problem in perspective, Management Science, 12, 10, 450-468 (1966)
[32] Wang, S.; Sarker, B. R., Locating cells with bottleneck machines in cellular manufacturing systems, International Journal of Production Research, 40, 2, 403-424 (2002) · Zbl 1060.90623
[33] Wang, T. Y.; Wu, K. B.; Liu, Y. W., A simulated annealing algorithm for facility layout problems under variable demand in cellular manufacturing systems, Computers in Industry, 46, 181-188 (2001)
[34] Wemmerlöv, U.; Hyer, N. L., Cellular manufacturing in the US industry: A survey of users, International Journal of Production Research, 27, 9, 1511-1530 (1989)
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.