SIMULATED ANNEALING ALGORITHM AND IMPLEMENTATION SOFTWARE FOR FABRIC CUTTING PROBLEM

Year 2020, Volume: 30 Issue: 1, 10 - 19, 25.03.2020

Duygu Yılmaz Eroğlu , âli Yurdun Orbak

https://doi.org/10.32710/tekstilvekonfeksiyon.521944

Cited By: 2

Abstract

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

References

• 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.