A Petri Net-Based Algorithm for Solving the One-Dimensional Cutting Stock Problem
Source abstract
Abstract
This paper addresses the one-dimensional cutting stock problem, focusing on minimizing total stock usage. Most procedures that deal with this problem reside on linear programming methods, heuristics, metaheuristics, and hybridizations. These methods face drawbacks like handling only low-complexity instances or requiring extensive parameter tuning. To address these limitations we develop a Petri-net model to construct cutting patterns. Using the filtered beam search algorithm, the reachability tree of the Petri net is constructed level by level from its root node to find the best solution, pruning the nodes that worsen the solution as the search progresses through the tree. Our algorithm is compared with the Least Lost Algorithm and the Generate and Solve algorithm over five datasets of instances. These algorithms share some characteristics with ours and have proven to be effective and efficient. Experimental results demonstrate that our algorithm effectively finds optimal and near-optimalsolutions for both low and high-complexity instances. These findings confirm that Petri nets are suitable for modeling and solving the one-dimensional cutting stock problem.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Optimization and Packing Problems · Advanced Manufacturing and Logistics Optimization · Manufacturing Process and Optimization
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Área Académica de Ingeniería y Arquitectura, Instituto de Ciencias Básicas e Ingeniería, Universidad Autónoma del Estado de Hidalgo, Carretera Pachuca-Tulancingo km. 4.5, Ciudad del Conocimiento, Mineral de la Reforma 42184, Mexico
References (68)
Show source-provided references
1. A survey on the cutting and packing problems10.1007/s40574-020-00253-6 ↗
2. An improved typology of cutting and packing problems10.1016/j.ejor.2005.12.047 ↗
3. Lee, D., Son, S., Kim, D., and Kim, S. (2020). Special-Length-Priority Algorithm to Minimize Reinforcing Bar-Cutting Waste for Sustainable Construction. Sustainability, 12.10.3390/su12155950 ↗
4. An efficient mathematical model for solving one-dimensional cutting stock problem using sustainable trim
5. LP models for bin packing and cutting stock problems10.1016/S0377-2217(02)00124-8 ↗
6. Aluminum bar cutting optimization for door and window manufacturing10.15446/dyna.v87n212.82636 ↗
7. A new evolutionary approach to cutting stock problems with and without contiguity10.1016/S0305-0548(01)00039-9 ↗
8. Scheduling flexible manufacturing systems using Petri nets and heuristic search10.1109/70.282537 ↗
9. Ali, M., Pan, J.S., Chen, S.M., and Horng, M.F. (2014, January 3–6). Heuristic Search for Scheduling Flexible Manufacturing Systems Using Multiple Heuristic Functions. Proceedings of the Modern Advances in Applied Intelligence, Kaohsiung, Taiwan.
10. Xu, G., and Chen, Y. (2022). Petri-Net-Based Scheduling of Flexible Manufacturing Systems Using an Estimate Function. Symmetry, 14.10.3390/sym14051052 ↗
11. A new Hybrid Filtered Beam Search algorithm for deadlock-free scheduling of flexible manufacturing systems using Petri Nets10.1016/j.cie.2017.04.034 ↗
12. A filtered beam search method for the m-machine permutation flowshop scheduling problem minimizing the earliness and tardiness penalties and the waiting time of the jobs10.1016/j.cor.2019.104824 ↗
13. Iterative beam search algorithms for the permutation flowshop10.1016/j.ejor.2021.10.015 ↗
14. Mathematical methods of organizing and planning production10.1287/mnsc.6.4.366 ↗
15. A Linear Programming Approach to the Cutting-Stock Problem10.1287/opre.9.6.849 ↗
16. A linear programming approach to the cutting stock problem—Part II10.1287/opre.11.6.863 ↗
17. Branch-and-Price Algorithms for the One-Dimensional Cutting Stock Problem10.1023/A:1018346107246 ↗
18. Belov, G., and Scheithauer, G. (2003). The Number of Setups (Different Patterns) in One-Dimensional Stock Cutting, Institute for Numerical Mathematics, Dresden University. Technical Report MATH-NM-15-2003.
19. A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting10.1016/j.ejor.2004.08.036 ↗
20. A branch-and-price-and-cut algorithm for the pattern minimization problem10.1051/ro:2008027 ↗
21. One-dimensional cutting stock problem problems and solution procedures10.1016/0895-7177(92)90074-U ↗
22. A sequential heuristic procedure for one-dimensional cutting10.1016/S0377-2217(98)00140-4 ↗
23. Pattern reduction in one-dimensional cutting stock problems10.1080/002075400188780 ↗
24. A hybrid heuristic to reduce the number of different patterns in cutting stock problems10.1016/j.cor.2005.02.026 ↗
25. A pattern reduction procedure in a one-dimensional cutting stock problem by grouping items according to their demands
26. Exact solution of bin-packing problems using column generation and branch-and-bound10.1023/A:1018952112615 ↗
27. Arc-flow formulations for the one-dimensional cutting stock problem with multiple manufacturing modes10.1051/ro/2023001 ↗
28. A New Linear Programming Approach to the Cutting Stock Problem10.1287/opre.29.6.1092 ↗
29. A comparative study of the arcflow model and the one-cut model for one-dimensional cutting stock problems10.1016/j.ejor.2017.10.008 ↗
30. A New Heuristic Algorithm for the One-Dimensional Cutting Stock Problem
31. Arc flow formulations based on dynamic programming: Theoretical foundations and applications10.1016/j.ejor.2021.04.024 ↗
32. Bin packing and cutting stock problems: Mathematical models and exact algorithms10.1016/j.ejor.2016.04.030 ↗
33. Peng, J., and Chu, Z.S. (2010, January 26–28). A Hybrid Multi-chromosome Genetic Algorithm for the Cutting Stock Problem. Proceedings of the 2010 3rd International Conference on Information Management, Innovation Management and Industrial Engineering, Kunming, China.10.1109/ICIII.2010.128 ↗
34. A Genetic Algorithm for the One-dimensional Cutting Stock Problem with Setups10.1590/0101-7438.2014.034.02.0165 ↗
35. Parmar, K.B., Prajapati, H.B., and Dabhi, V.K. (2015, January 19–20). Cutting stock problem: A solution based on novel pattern based chromosome representation using modified GA. Proceedings of the 2015 International Conference on Circuits, Power and Computing Technologies [ICCPCT-2015], Nagercoil, India.10.1109/ICCPCT.2015.7159318 ↗
36. Chen, Y.H., Huang, H.C., Cai, H.Y., and Chen, P.F. (2019, January 12–14). A Genetic Algorithm Approach for the Multiple Length Cutting Stock Problem. Proceedings of the 2019 IEEE 1st Global Conference on Life Sciences and Technologies (LifeTech), Osaka, Japan.10.1109/LifeTech.2019.8884020 ↗
37. Liang, K.H., Yao, X., Newton, C., and Hoffman, D. (1998, January 25–27). Solving cutting stock problems by evolutionary programming. Proceedings of the 7th Annual Conference on Evolutionary Programming, EP 1998, San Diego, CA, USA.10.1007/BFb0040826 ↗
38. A Comparison between Genetic Algorithms and Evolutionary Programming based on Cutting Stock Problem
39. Shi, Y., van Albada, G.D., Dongarra, J., and Sloot, P.M.A. (2007, January 27–30). A Heuristic Particle Swarm Optimization for Cutting Stock Problem Based on Cutting Pattern. Proceedings of the Computational Science—ICCS 2007, Beijing China.
40. Wang, Y., Cheung, Y.M., and Liu, H. (2006, January 3–6). General Particle Swarm Optimization Based on Simulated Annealing for Multi-specification One-Dimensional Cutting Stock Problem. Proceedings of the Computational Intelligence and Security, Guangzhou, China.
41. Ben Lagha, G., Dahmani, N., and Krichen, S. (2014, January 1–3). Particle swarm optimization approach for resolving the cutting stock problem. Proceedings of the 2014 International Conference on Advanced Logistics and Transport (ICALT), Tunis, Tunisia.10.1109/ICAdLT.2014.6866321 ↗
42. One-dimensional cutting stock problem with single and multiple stock lengths using DPSO
43. Ant colony optimization and local search for bin packing and cutting stock problems10.1057/palgrave.jors.2601771 ↗
44. Peng, J., and Chu, Z.S. (2010, January 9–10). A hybrid ant colony algorithm for the Cutting Stock Problem. Proceedings of the 2010 International Conference on Future Information Technology and Management Engineering, Changzhou, China.
45. Georgiev, K., Todorov, M., and Georgiev, I. (2016, January 20–22). Ant Colony Optimization Algorithm for 1D Cutting Stock Problem. Proceedings of the Advanced Computing in Industrial Mathematics: 11th Annual Meeting of the Bulgarian Section of SIAM, Sofia, Bulgaria. Revised Selected Papers.
46. Solving an one-dimensional cutting stock problem by simulated annealing and tabu search10.1186/2251-712X-8-24 ↗
47. One-dimensional cutting stock problem to minimize the number of different patterns10.1016/S0377-2217(02)00239-4 ↗
48. One-Dimensional Cutting Stock Problem with a Given Number of Setups: A Hybrid Approach of Metaheuristics and Linear Programming10.1007/s10852-005-9031-0 ↗
49. A Least-Loss Algorithm for a Bi-Objective One-Dimensional Cutting-Stock Problem
50. Sá Santos, J.V., and Nepomuceno, N. (2022). Computational Performance Evaluation of Column Generation and Generate-and-Solve Techniques for the One-Dimensional Cutting Stock Problem. Algorithms, 15.10.3390/a15110394 ↗
51. Pattern generating procedure for the cutting stock problem10.1016/S0925-5273(01)00134-7 ↗
52. Fang, J., Rao, Y., Luo, Q., and Xu, J. (2023). Solving One-Dimensional Cutting Stock Problems with the Deep Reinforcement Learning. Mathematics, 11.10.3390/math11041028 ↗
53. A Petri net-based particle swarm optimization approach for scheduling deadlock-prone flexible manufacturing systems10.1007/s10845-015-1161-2 ↗
54. Policy to cope with deadlocks and livelocks for flexible manufacturing systems using the max’-controlled new smart siphons10.1049/iet-cta.2014.0005 ↗
55. Job shop scheduling with beam search10.1016/S0377-2217(98)00319-1 ↗
56. A Method of Filtered Beam Search Based Delivery Scheduling10.1541/ieejias.113.1061 ↗
57. A Beam Search Heuristic for the Traveling Salesman Problem with Time Windows
58. A beam search for the equality generalized symmetric traveling salesman problem10.1051/ro/2021148 ↗
59. A beam search implementation for the irregular shape packing problem10.1007/s10732-008-9095-x ↗
60. A beam search approach to solve the convex irregular bin packing problem with guillotine cuts10.1016/j.ejor.2018.03.029 ↗
61. Solving a large cutting problem in the glass manufacturing industry10.1016/j.ejor.2020.05.016 ↗
62. Hybridizing Beam Search with Tabu Search for the Irregular Packing Problem
63. An anytime tree search algorithm for the 2018 ROADEF/EURO challenge glass cutting problem10.1016/j.ejor.2020.10.050 ↗
64. Filtered beam search in scheduling10.1080/00207548808947840 ↗
65. Liveness Analysis of Petri Nets Using Siphons and Mathematical Programming10.3182/20140514-3-FR-4046.00078 ↗
66. PIPE2: A Tool for the Performance Evaluation of Generalised Stochastic Petri Nets10.1145/1530873.1530881 ↗
67. Yao, X. (1995, January 4–6). Genetic algorithms for cutting stock problems: With and without contiguity. Proceedings of the Progress in Evolutionary Computation, Granada, Spain.
68. (2023, October 18). OR Library by J. E. Beasley. Available online: http://people.brunel.ac.uk/~mastjjb/jeb/info.html.