SIMULATED ANNEALING ALGORITHM AND IMPLEMENTATION SOFTWARE FOR FABRIC CUTTING PROBLEM

Development of loom technology has significantly increased the efficiency of fabric output in the textile industry. Additionally, preventing the occurrence of defects during the manufacturing process on the fabric is not easy. Therefore, after the production completed, the aim is deciding the cutting location of the product, which has the error map, to increase the first quality product quantity by considering the customer quality parameters. In this article, a decision support system has been developed to help the inspector in the final stage which will also prevent losses. The first of the proposed two algorithms is Simulated Annealing algorithm, which is well known and rendered good results for the different type of problems in the literature, and the other is the K-means method which is frequently used in clustering. In the study, a sample problem is used to explain the adaptation of algorithms to the problem, the results of methods are compared, and design of the experiment is deployed to obtain the best parameter values for the selected algorithm. Finally, the software, which is prepared to use the algorithm in the real production environment, is introduced and the results of the performance analysis are evaluated. The results demonstrated that the developed software is capable of making high ratio first quality fabric decision within seconds.

Keywords:

Cutting algorithms, Simulated Annealing,

PDF

___

1. Brandao, F., & Pedroso, J. P. (2014). Fast pattern-based algorithms for cutting stock. Computers & Operations Research, 48, 69-80.
2. De Carvalho, J. V., & Rodrigues, A. G. (1995). An LP-based approach to a two-stage cutting stock problem. European Journal of Operational Research, 84(3), 580-589.
3. Vanderbeck, F. (2000). Exact algorithm for minimising the number of setups in the one-dimensional cutting stock problem. Operations Research, 48(6), 915-926.
4. De Carvalho, J. V. (2002). LP models for bin packing and cutting stock problems. European Journal of Operational Research, 141(2), 253-273.
5. Boschetti, M. A., Mingozzi, A., & Hadjiconstantinou, E. (2002). New upper bounds for the two‐dimensional orthogonal non‐guillotine cutting stock problem. IMA Journal of Management Mathematics, 13(2), 95-119.
6. Bobrowski, P. M. (1990). Branch‐and‐Bound Strategies for the Log Bucking Problem. Decision Sciences, 21(1), 1-13.
7. Haessler, R. W., & Sweeney, P. E. (1991). Cutting stock problems and solution procedures.
8. Wäscher, G., Haußner, H., & Schumann, H. (2007). An improved typology of cutting and packing problems. European journal of operational research, 183(3), 1109-1130.
9. Gilmore, P. C., & Gomory, R. E. (1965). Multistage cutting stock problems of two and more dimensions. Operations research, 13(1), 94-120.
10. Faina, L. (1999). An application of simulated annealing to the cutting stock problem. European Journal of Operational Research, 114(3), 542-556.
11. Lodi, A., Martello, S., & Monaci, M. (2002). Two-dimensional packing problems: A survey. European journal of operational research, 141(2), 241-252.
12. Cui, Y., & Zhao, Z. (2013). Heuristic for the rectangular two-dimensional single stock size cutting stock problem with two-staged patterns. European Journal of Operational Research, 231(2), 288-298.
13. Kim, K., Kim, B. I., & Cho, H. (2014). Multiple-choice knapsack-based heuristic algorithm for the two-stage two-dimensional cutting stock problem in the paper industry. International Journal of Production Research, 52(19), 5675-5689.
14. Afsharian, M., Niknejad, A., & Wäscher, G. (2014). A heuristic, dynamic programming-based approach for a two-dimensional cutting problem with defects. OR spectrum, 36(4), 971-999.
15. Javanshir, H., Rezaei, S., Najar, S. S., & Ganji, S. S. (2010). Two dimensional cutting stock management in fabric industries and optimizing the large object’s length. Journal of Research and Reviews in Applied Sciences, 4(3), 243-249.
16. Cherri, A. C., Arenales, M. N., Yanasse, H. H., Poldi, K. C., & Vianna, A. C. G. (2014). The one-dimensional cutting stock problem with usable leftovers–A survey. European Journal of Operational Research, 236(2), 395-402.
17. Gradišar, M., Jesenko, J., & Resinovič, G. (1997). Optimization of roll cutting in clothing industry. Computers & Operations Research, 24(10), 945-953.
18. Poldi, K. C., & Arenales, M. N. (2009). Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths. Computers & Operations Research, 36(6), 2074-2081.
19. Poltroniere, S. C., Poldi, K. C., Toledo, F. M. B., & Arenales, M. N. (2008). A coupling cutting stock-lot sizing problem in the paper industry. Annals of Operations Research, 157(1), 91-104.
20. Arbib, C., & Marinelli, F. (2014). On cutting stock with due dates. Omega, 46, 11-20.
21. Araujo, S. A. D., Poldi, K. C., & Smith, J. (2014). A genetic algorithm for the one-dimensional cutting stock problem with setups. Pesquisa Operacional, 34(2), 165-187.
22. Yanasse, H. H., & Limeira, M. S. (2006). A hybrid heuristic to reduce the number of different patterns in cutting stock problems. Computers & Operations Research, 33(9), 2744-2756.
23. Lai, K. K., & Chan, J. W. (1997). Developing a simulated annealing algorithm for the cutting stock problem. Computers & industrial engineering, 32(1), 115-127.
24. Brandao, F., & Pedroso, J. P. (2014). Fast pattern-based algorithms for cutting stock. Computers & Operations Research, 48, 69-80.
25. Eroğlu, D. Y., Özmutlu, H. C., & Köksal, S. A. Bölünebilir ve sıra bağımlı hazırlık süreli işler içeren, ilişkisiz paralel makine çizelgeleme problemi için genetik algoritma-dokuma tezgahı çizelgeleme. Tekstil ve Konfeksiyon, 24(1), 66-73.
26. Ozdamar, L. (2000). The cutting-wrapping problem in the textile industry: optimal overlap of fabric lengths and defects for maximizing return based on quality. International Journal of Production Research, 38(6), 1287-1309.
27. Whitaker, D., & Cammell, S. (1990). A partitioned cutting-stock problem applied in the meat industry. Journal of the Operational Research Society, 41(9), 801-807.
28. Sculli, D. (1981). A stochastic cutting stock procedure: cutting rolls of insulating tape. Management Science, 27(8), 946-952.
29. Sweeney, P. E. (1988). One-dimensional cutting stock decisions for rolls with multiple quality grades.
30. Sarker, B. R. (1988). An optimum solution for one-dimensional slitting problems: a dynamic programming approach. Journal of the Operational Research Society, 39(8), 749-755.
31. Hartigan, J. A., & Wong, M. A. (1979). Algorithm AS 136: A k-means clustering algorithm. Journal of the Royal Statistical Society. Series C (Applied Statistics), 28(1), 100-108.
32. Jain, A. K. (2010). Data clustering: 50 years beyond K-means. Pattern recognition letters, 31(8), 651-666.
33. Wagstaff, K., Cardie, C., Rogers, S., & Schrödl, S. (2001, June). Constrained k-means clustering with background knowledge. In ICML (Vol. 1, pp. 577-584).
34. Chen, T. S., Tsai, T. H., Chen, Y. T., Lin, C. C., Chen, R. C., Li, S. Y., & Chen, H. Y. (2005, December). A combined K-means and hierarchical clustering method for improving the clustering efficiency of microarray. In Intelligent Signal Processing and Communication Systems, 2005. ISPACS 2005. Proceedings of 2005 International Symposium on (pp. 405-408). IEEE.
35. Salvador, S., & Chan, P. (2004, November). Determining the number of clusters/segments in hierarchical clustering/segmentation algorithms. In Tools with Artificial Intelligence, 2004. ICTAI 2004. 16th IEEE International Conference on (pp. 576-584). IEEE.
36. Krishna, K., & Murty, M. N. (1999). Genetic K-means algorithm. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 29(3), 433-439.
37. Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598), 671-680.

ISSN: 1300-3356
Yayın Aralığı: Yılda 4 Sayı
Yayıncı: Ege Üniversitesi Tekstil ve Konfeksiyon Araştırma & Uygulama Merkezi

Arşiv