In recent years, wood has been considered as a building material from the perspective of SDGs. Pre-cut lumber is often used for wooden houses, including roofs, floors, and pillars. It is preprocessed into a certain shape for the joint parts and has joint brackets if necessary. The use of them has the advantages of shortening the construction period and reducing the construction cost. The number of pre-cut lumber production factories in Japan decreased from 757 in 2001 to 659 in 2011 and then increased to 730 in 2016. Compared with 2011, the number of factories with sales of <500 million yen in 2016 decreased by approximately 30%, while the number of factors with sales of ≥500 million yen increased by 80%, indicating a trend toward a larger scale [1]. Therefore, improving the productivity of these factories is imperative. We have been researching the conversion of factories into smart factories to improve the productivity of pre-cut lumber manufacturing company A. In this company, employees take 1.2 h to prepare packing plans every day, and the company faces the challenge of improving the efficiency of planning operations. Herein, we propose an algorithm using an iterative local search (ILS) with Or-opt (ILS + Or-opt) for packing formation support systems to improve the efficiency of planning operations. This algorithm has the following two features. First, it uses Or-opt to create a neighborhood for a local search. Second, uses exchange neighborhoods when repeating the ILS to achieve diversity in the search.

1. [1] Ministry of Agriculture, Forestry and Fisheries. “Annual Report on Forest and Forestry in Japan Fiscal Year 2019” (in Japanese). https://www.rinya.maff.go.jp/j/kikaku/hakusyo/r1hakusyo_h/all/chap3_3_7.html [Accessed October 1, 2021]
2. [2] R. Burke, A. Mussomeli, S. Laaper, M. Hartigan, and B. Sniderman, “The smart factory.” https://www2.deloitte.com/content/dam/insights/us/articles/4051_The-smart-factory/DUP_The-smart-factory.pdf [Accessed October 1, 2021]
3. [3] K. D. Thoben, S. Wiesner, and T. Wuest, ““Industrie 4.0” and Smart Manufacturing – A Review of Research Issues and Application Examples,” Int. J. Automation Technol., Vol.11, No.1, pp. 4-16, 2017.
4. [4] D. Kokuryo, T. Kaihara, S. S. Kuik, S. Suginouchi, and K. Hirai, “Value Co-Creative Manufacturing with IoT-Based Smart Factory for Mass Customization,” Int. J. Automation Technol., Vol.11, No.3, pp. 509-518, 2017.
5. [5] S. Imahori and S. Umetani, “Cut-and-pack problems and their applications – (2), Rectangle Packing Problem –,” Communications of the Operations Research Society of Japan, Vol.50, No.5, pp. 37-42, 2005 (in Japanese).
6. [6] P. C. Gilmore and R. E. Gomory, “Multistage cutting problems of two and more dimensions,” Operations Research, Vol.13, No.1, pp. 94-119, 1965.
7. [7] J. E. Beasley, “A population heuristic for constrained two-dimensional non-guillotine cutting,” European J. of Operational Research, Vol.156, Issue 3, pp. 601-627, 2004.
8. [8] J. F. Gonçalves and M. G. C. Resende, “A hybrid heuristic for the constrained two-dimensional non-guillotine orthogonal cutting problem,” AT&T Labs Research Technical Report TD-UNQN6, 2006.
9. [9] E. Hadjiconstantinou and N. Christofides, “An exact algorithm for general, orthogonal, two-dimensional knapsack problems,” European J. of Operational Research, Vol.83, Issue 1, pp. 39-56, 1995.
10. [10] K. K. Lai and J. W. M. Chan, “An evolutionary algorithm for the rectangular cutting stock problem,” Int. J. of Industrial Engineering, Vol.4, Issue 2, pp. 130-139, 1997.
11. [11] K. K. Lai and J. W. M. Chan, “Developing a simulated annealing algorithm for the cutting stock problem,” Computers & Industrial Engineering, Vol.32, Issue 1, pp. 115-127, 1997.
12. [12] T. W. Leung, C. K. Chan, and M. D. Troutt, “Applications of genetic search and simulated annealing to the two dimensional non-guillotine cutting stock problem,” Computers and Industrial Engineering, Vol.40, Issue 3, pp. 201-214, 2001.
13. [13] T. W. Leung, C. K. Chan, and M. D. Troutt, “Application of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem,” European J. of Operational Research, Vol.145, Issue 3, pp. 530-542, 2003.
14. [14] R. Alvarez-Valdés, A. Parajón, and J. M. Tamarit, “A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems,” Computers & Operations Research, Vol.29, Issue 7, pp. 925-947, 2002.
15. [15] R. Alvarez-Valdés, A. Parajón, and J. M. Tamarit, “A tabu search algorithm for a two-dimensional non-guillotine cutting problems,” European J. of Operational Research, Vol.183, Issue 3, pp. 1167-1182, 2007.
16. [16] R. Alvarez-Valdés, A. Parajón, and J. M. Tamarit, “A GRASP algorithm for constrained two-dimensional non-guillotine cutting problems,” J. of the Operational Research Society, Vol.56, No.4, pp. 414-425, 2005.
17. [17] S. P. Fekete and J. Shepers, “On more-dimensional packing III: Exact algorithms,” Technical Report, Mathematisches Institut, Universität zu Köln, No.97.290, 1997.
18. [18] S. P. Fekete, J. Shepers, and J. C. van der Veen, “An Exact Algorithm for Higher-Dimensional Orthogonal Packing,” Operations Research, Vol.55, No.3, pp. 569-587, 2007.
19. [19] A. Caprara and M. Monaci, “On the two-dimensional Knapsack Problem,” Operations Research Letters, Vol.32, Issue 1, pp. 5-14, 2004.
20. [20] G. F. Cintra, F. K. Miyazawa, Y. Wakabayashi, and E. C. Xavier, “Algorithms for two-dimensional cutting stock and strippacking problems using dynamic programmingand column generation,” European J. of Operational Research, Vol.191, Issue 1, pp. 61-85, 2008.
21. [21] A. Lodi, S. Martello, and M. Monaci, “Two-dimensional packing problems: A survey,” European J. of Operational Research, Vol.141, Issue 2, pp. 241-252, 2002.
22. [22] F. K. R. Chung, M. R. Garey, and D. S. Johnson, “On packing two-dimensional bins,” SIAM J. of Algebraic and Discrete Methods, Vol.3, No.1, pp. 66-76, 1982.
23. [23] J. B. Frenk and G. G. Galambos, “Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem,” Computing, Vol.39, No.3, pp. 201-217, 1987.
24. [24] J. O. Berkey and P. Y. Wang, “Two dimensional finite bin packing algorithms,” J. of the Operational Research Society, Vol.38, No.5, pp. 423-429, 1987.
25. [25] K. A. Dowsland, “Some experiments withsimulated annealing techniques for packing problems,” European J. of Operational Research, Vol.68, Issue 3, pp. 389-399, 1993.
26. [26] A. Lodi, S. Martello, and D. Vigo, “Approximation algorithms for the oriented two-dimensional bin packing problem,” European J. of Operational Research, Vol.112, Issue 1, pp. 158-166, 1999.
27. [27] E. G. Coffman Jr., M. R. Garey, D. S. Johnson, and R. E. Tarjan, “Performance bounds for level-oriented two-dimensional packing algorithms,” SIAM J. on Computing, Vol.9, No.4, pp. 801-826, 1980.
28. [28] B. S. Baker, E. G. Coffman Jr., and R. L. Rivest, “Orthogonal packing in two dimensions,” SIAM J. on Computing, Vol.9, No.4, pp. 846-855, 1980.
29. [29] B. Chazelle, “The bottom-left bin packing heuristic: An efficient implementation,” IEEE Trans. on Computers, Vol.C-32, Issue 8, pp. 697-707, 1983.
30. [30] D. Sleator, “A 2.5 times optimal algorithm for packing in two dimensions,” Information Processing Letters, Vol.10, No.1, pp. 37-40, 1980.
31. [31] I. Schiermeyer, “Reverse fit: A 2-optimal algorithm for packing rectangles,” Proc. of the 2nd Annual European Symp. Algorithms – ESA’94, pp. 290-299, 1994.
32. [32] M. Sugi, Y. Shiomi, T. Okubo, K. Inoue, and J. Ota, “A Solution for 2D Rectangular Cutting Stock Problems with 3-Stage Guillotine-Cutting Constraint,” Int. J. Automation Technol., Vol.4, No.5, pp. 461-468, 2010.
33. [33] M. Sugi, Y. Shiomi, T. Okubo, H. Nagai, K. Inoue, and J. Ota, “Solution of the Rectangular Strip Packing Problem Considering a 3-Stage Guillotine Cutting Constraint with Finite Slitter Blades,” Int. J. Automation Technol., Vol.14, No.3, pp. 447-458, 2020.
34. [34] S. Jacobs, “On genetic algorithms for the packing of polygons,” European J. of Operational Research, Vol.88, Issue 1, pp. 165-181, 1996.
35. [35] A. M. Gomes and J. F. Oliveira, “Solving Irregular Strip Packing problems by hybridising simulated annealing and linear programming,” European J. of Operational Research, Vol.171, Issue 3, pp. 811-829, 2006.
36. [36] E. Burke, R. Hellier, G. Kendall, and G. Whitwell, “A New Bottom-Left-Fill Heuristic Algorithm for the Two-Dimensional Irregular Packing Problem,” Operations Research, Vol.54, No.3, pp. 587-601, 2006.
37. [37] J. Egeblad, B. K. Nielsen, and A. Odgaard, “Fast neighborhood search for two- and three-dimensional nesting problems,” European J. of Operational Research, Vol.183, Issue 3, pp. 1249-1266, 2007.
38. [38] T. Imamichi, M. Yagiura, and H. Nagamochi, “An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem,” Discrete Optimization, Vol.6, Issue 4, pp. 345-361, 2009.
39. [39] S. C. H. Leung, Y. Lin, and D. Zhang, “Extended local search algorithm based on nonlinear programming for two-dimensional irregular strip packing problem,” Computers & Operations Research, Vol.39, Issue 3, pp. 678-686, 2012.
40. [40] J. Peralta, M. Andretta, and J. F. Oliveira, “Solving Irregular Strip Packing Problems with Free Rotations Using Separation Lines,” Pesquisa Operacional, Vol.38, No.2, pp. 195-214, 2018.