Optimizing cut order planning: A comparative study of heuristics, metaheuristics, and MILP algorithms
Submitted: 2024-07-31
|Accepted: 2024-11-23
|Published: 2025-01-31
Copyright (c) 2025 Sharif Al-Mahmud, Jose Alejandro Cano, Emiro Antonio Campo, Stephan Weyers
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Downloads
Keywords:
COP, Cut order planning, Heuristics, Metaheuristics, MILP, Garment manufacturing
Supporting agencies:
Abstract:
Cut Order Planning (COP) optimizes production costs in the apparel industry by efficiently cutting fabric for garments. This complex process involves challenging decision-making due to order specifications and production constraints. This article introduces novel approaches to the COP problem using heuristics, metaheuristic algorithms, and commercial solvers. Two different solution approaches are proposed and tested through experimentation and analysis, demonstrating their effectiveness in real-world scenarios. The first approach uses conventional metaheuristic algorithms, while the second transforms the nonlinear COP mathematical model into a Mixed Integer Linear Programming (MILP) problem and uses commercial solvers for solution. Modifications to existing heuristics, combined with tournament selection in genetic algorithms (GA), improve solution quality and efficiency. Comparative analysis shows that Particle Swarm Optimization (PSO) outperforms GA, especially for small and medium-sized problems. Cost and runtime evaluations confirm the efficiency and practical applicability of the proposed algorithms, with commercial solvers, delivering superior solutions in shorter computation times. This study suggests the use of solvers for the COP problem, especially for smaller orders, and reserves PSO and GA for larger orders where commercial solvers may not provide a solution.
References:
Abd Jelil, R. (2018). Review of Artificial Intelligence Applications in Garment Manufacturing. In S. Thomassey & X. Zeng (Eds.), Artificial Intelligence for Fashion Industry in the Big Data Era. Springer Series in Fashion Business. (pp. 97-123). Springer Singapore. https://doi.org/10.1007/978-981-13-0080-6_6
Abeysooriya, R. ., & Fernando, T. G. . (2012a). Canonical Genetic Algorithm To Optimize Cut Order Plan Solutions in Apparel. Journal of Emerging Trends in Computing and Information Sciences, 3(2), 150-154.
Abeysooriya, R. ., & Fernando, T. G. . (2012b). Hybrid Approach to Optimize Cut Order Plan Solutions in Apparel Manufacturing. International Journal of Information and Communication Technology Research, 2(4), 348-353.
Abualigah, L., Gandomi, A. H., Elaziz, M. A., Hamad, H. Al, Omari, M., Alshinwan, M., & Khasawneh, A. M. (2021). Advances in meta-heuristic optimization algorithms in big data text clustering. Electronics (Switzerland), 10(2), 101. https://doi.org/10.3390/electronics10020101
Alhijawi, B., & Awajan, A. (2023). Genetic algorithms: theory, genetic operators, solutions, and applications. Evolutionary Intelligence. https://doi.org/10.1007/s12065-023-00822-6
Alsamarah, W., Younes, B., & Yousef, M. (2022). Reducing waste in garment factories by intelligent planning of optimal cutting orders. The Journal of The Textile Institute, 113(9), 1917-1925. https://doi.org/10.1080/00405000.2021.1956711
Boussaïd, I., Lepagnot, J., & Siarry, P. (2013). A survey on optimization metaheuristics. Information Sciences, 237, 82-117. https://doi.org/10.1016/j.ins.2013.02.041
Cano, J. A., Cortés, P., Muñuzuri, J., & Correa-Espinal, A. (2023). Solving the picker routing problem in multi-block high-level storage systems using metaheuristics. Flexible Services and Manufacturing Journal, 35(1), 376-415. https://doi.org/10.1007/s10696-022-09445-y
Chang, D., Shi, H., Liu, C., & Meng, F. (2024). Scheduling optimization of flexible flow shop with buffer capacity limitation based on an improved discrete particle swarm optimization algorithm. Engineering Optimization, 1-27. https://doi.org/10.1080/0305215X.2024.2328191
Chen, B., Zhang, R., Chen, L., & Long, S. (2021). Adaptive Particle Swarm Optimization with Gaussian Perturbation and Mutation. Scientific Programming, 2021, 6676449. https://doi.org/10.1155/2021/6676449
Degraeve, Z., & Vandebroek, M. (1998). A Mixed Integer Programming Model for Solving a Layout Problem in the Fashion Industry. Management Science, 44(3), 301-310. https://doi.org/10.1287/mnsc.44.3.301
Ezugwu, A. E., Shukla, A. K., Nath, R., & Akinyelu, A. A. (2021). Metaheuristics: a comprehensive overview and classification along with bibliometric analysis. In Artificial Intelligence Review (Vol. 54, Issue 6). Springer Netherlands. https://doi.org/10.1007/s10462-020-09952-0
Filipič, B., Fister, I., & Mernik, M. (2006). Evolutionary search for optimal combinations of markers in clothing manufacturing. GECCO '06: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, 1661-1666. https://doi.org/10.1145/1143997.1144270
Fister, I., Mernik, M., & Filipic, B. (2010). A hybrid self-adaptive evolutionary algorithm for marker optimization in the clothing industry. Applied Soft Computing, 10, 409-422. https://doi.org/10.1016/j.asoc.2009.08.001
Fister, I., Mernik, M., & Filipič, B. (2008). Optimization of markers in clothing industry. Engineering Applications of Artificial Intelligence, 21(4), 669-678. https://doi.org/10.1016/j.engappai.2007.06.002
Gogna, A., & Tayal, A. (2013). Metaheuristics: Review and application. In Journal of Experimental and Theoretical Artificial Intelligence (Vol. 25, Issue 4, pp. 503-526). Taylor & Francis. https://doi.org/10.1080/0952813X.2013.782347
Gómez-Montoya, R. A., Cano, J. A., Cortés, P., & Salazar, F. (2020). A discrete particle swarm optimization to solve the put-away routing problem in distribution centres. Computation, 8(4), 1-17. https://doi.org/10.3390/computation8040099
IBM. (2022). IBM ILOG CPLEX Optimization Studio. Relative MIP Gap Tolerance. https://www.ibm.com/docs/en/icos/22.1.1?topic=parameters-relative-mip-gap-tolerance
Jacobs-Blecha, C., Ammons, J. C., Schutte, A., & Smith, T. (1998). Cut order planning for apparel manufacturing. IIE Transactions, 30(1), 79-90. https://doi.org/10.1080/07408179808966439
Jarboui, B., Damak, N., Siarry, P., & Rebai, A. (2008). A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems. Applied Mathematics and Computation, 195(1), 299-308. https://doi.org/10.1016/j.amc.2007.04.096
Katoch, S., Chauhan, S. S., & Kumar, V. (2021). A review on genetic algorithm: past, present, and future. In Multimedia Tools and Applications (Vol. 80, Issue 5). Multimedia Tools and Applications. https://doi.org/10.1007/s11042-020-10139-6
Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. Proceedings of ICNN'95 - International Conference on Neural Networks, 4, 1942-1948. https://doi.org/10.1109/ICNN.1995.488968
Kennedy, J., & Eberhart, R. C. (1997). A discrete binary version of the particle swarm algorithm. IEEE International Conference on Computational Cybernetics and Simulation, 4104-4108. https://doi.org/10.1109/ICSMC.1997.637339
M'Hallah, R., & Bouziri, A. (2016). Heuristics for the combined cut order planning two-dimensional layout problem in the apparel industry. International Transactions in Operational Research, 23(1), 321-353. https://doi.org/10.1111/itor.12104
Martens, J. (2004). Two genetic algorithms to solve a layout problem in the fashion industry. European Journal of Operational Research, 154(1), 304-322. https://doi.org/10.1016/S0377-2217(02)00706-3
Nascimento, D. B., Neiva De Figueiredo, J., Mayerle, S. F., Nascimento, P. R., & Casali, R. M. (2010). A state-space solution search method for apparel industry spreading and cutting. International Journal of Production Economics, 128(1), 379-392. https://doi.org/10.1016/j.ijpe.2010.07.035
Nasrin, U., & Alam, S. M. R. (2023). Implementing circular economy principles in the apparel production process: Reusing pre-consumer waste for sustainability of environment and economy. Cleaner Waste Systems, 6(April), 100108. https://doi.org/10.1016/j.clwas.2023.100108
Nchalala, A., Alexander, T., & Taifa, I. W. R. (2023). Establishing standard allowed minutes and sewing efficiency for the garment industry in Tanzania. Research Journal of Textile and Apparel, 27(2), 246-263. https://doi.org/10.1108/RJTA-09-2021-0112
Poli, R., Kennedy, J., & Blackwell, T. (2007). Particle swarm optimization: An overview. Swarm Intelligence, 1, 33-57. https://doi.org/10.1007/s11721-007-0002-0
Prasad, S., Panghal, M., & Ali, T. M. (2022). Developing a cost-effective and heuristic tool to solve cut order planning problems in the apparel industry. International Journal of Mathematics in Operational Research, 21(1), 26-45. https://doi.org/10.1504/IJMOR.2022.120314
Puasakul, K., & Chaovalitwongse, P. (2016). The review of mark planning problem. Engineering Journal, 20(3), 91-112. https://doi.org/10.4186/ej.2016.20.3.91
Ramos-Figueroa, O., Quiroz-Castellanos, M., Mezura-Montes, E., & Kharel, R. (2021). Variation Operators for Grouping Genetic Algorithms: A Review. Swarm and Evolutionary Computation, 60(September 2020). https://doi.org/10.1016/j.swevo.2020.100796
Ranaweera, R. N. M. P., Rathnayaka, R. M. K. T., & Chathuranga, L. L. G. (2023). Optimal Cut Order Planning Solutions using Heuristic and Meta-Heuristic Algorithms: A Systematic Literature Review. KDU Journal of Multidisciplinary Studies, 5(1), 86-97. https://doi.org/10.4038/kjms.v5i1.66
Rose, D. M., & Shier, D. R. (2007). Cut scheduling in the apparel industry. Computers & Operations Research, 34(11), 3209-3228. https://doi.org/10.1016/j.cor.2005.12.001
Shami, T. M., El-saleh, A. A., & Member, S. (2022). Particle Swarm Optimization: A Comprehensive Survey. IEEE Access, 10031-10061. https://doi.org/10.1109/ACCESS.2022.3142859
Shang, X., Shen, D., Wang, F.-Y., & Nyberg, T. R. (2019). A heuristic algorithm for the fabric spreading and cutting problem in apparel factories. IEEE/CAA Journal of Automatica Sinica, 6(4), 961-968. https://doi.org/10.1109/JAS.2019.1911573
Shen, M., Zhan, Z., Chen, W., Gong, Y., & Member, S. (2014). Bi-Velocity Discrete Particle Swarm Optimization and Its Application to Multicast Routing Problem in Communication Networks. IEEE Transactions on Industrial Electronics, 61(12), 7141-7151. https://doi.org/10.1109/TIE.2014.2314075
Silva, P. H. H. P. N. De, Lanel, G. H. J., & Perera, M. T. M. (2017). Integer Quadratic Programming (IQP) Model for Cut Order Plan. IOSR Journal of Mathematics, 13(02), 76-80. https://doi.org/10.9790/5728-1302027680
Toaza, B., & Esztergár-Kiss, D. (2023). A review of metaheuristic algorithms for solving TSP-based scheduling optimization problems. Applied Soft Computing, 148(January). https://doi.org/10.1016/j.asoc.2023.110908
Tsao, Y.-C., Delicia, M., & Vu, T. L. (2022). Marker planning problem in the apparel industry: Hybrid PSO-based heuristics. Applied Soft Computing, 123, 108928. https://doi.org/10.1016/j.asoc.2022.108928
Tsao, Y.-C., Vu, T.-L., & Liao, L.-W. (2020). Hybrid heuristics for the cut ordering planning problem in apparel industry. Computers & Industrial Engineering, 144(1), 106478. https://doi.org/10.1016/j.cie.2020.106478
Ünal, C., & Yüksel, A. D. (2020). Cut Order Planning Optimisation in the Apparel Industry. Fibres and Textiles in Eastern Europe, 28(1), 8-13. https://doi.org/10.5604/01.3001.0013.5851
Wijethilake, C., Upadhaya, B., & Lama, T. (2023). The role of organisational culture in organisational change towards sustainability: evidence from the garment manufacturing industry. Production Planning & Control, 34(3), 275-294. https://doi.org/10.1080/09537287.2021.1913524
Wong, W. K. Ã., & Leung, S. Y. S. (2008). Genetic optimization of fabric utilization in apparel manufacturing. International Journal of Production Economics, 114(1), 376-387. https://doi.org/10.1016/j.ijpe.2008.02.012
Xiang, W., Hui, D., Li, Y., & Wen-An, Z. (2022). Hybrid optimization algorithm for cut order planning of multicolor garment. Control and Decision, 37(6), 1531-1540. https://doi.org/10.13195/j.kzyjc.2020.1749
Xu, Y., Thomassey, S., & Zeng, X. (2020). Optimization of garment sizing and cutting order planning in the context of mass customization. The International Journal of Advanced Manufacturing Technology, 106(1), 3485-3503. https://doi.org/10.1007/s00170-019-04866-w
Yang, C. L., Huang, R. H., & Huang, H. L. (2011). Elucidating a layout problem in the fashion industry by using an ant optimisation approach. Production Planning and Control, 22(3), 248-256. https://doi.org/10.1080/09537287.2010.498600
Yang, Yali, Zhang, Y., Zuo, H., & Yan, N. (2023). The effective practical application of modern intelligent manufacturing technology in textile and garment industry. International Journal on Interactive Design and Manufacturing (IJIDeM). https://doi.org/10.1007/s12008-023-01559-3
Yang, Yizhe, Liu, B., Li, X., Jia, Q., Duan, W., & Wang, G. (2024). Fidelity-adaptive evolutionary optimization algorithm for 2D irregular cutting and packing problem. Journal of Intelligent Manufacturing. https://doi.org/10.1007/s10845-024-02329-y
