In sheet metal processing, nesting and scheduling are important factors affecting the efficiency and agility of manufacturing. The objective of nesting is to minimize the waste of material, while that of scheduling is to optimize the processing sequence. As the relation between them often becomes a trade-off, they should be considered simultaneously for the efficiency of the total manufacturing process. In this study, we propose a co-evolutionary genetic algorithm-based nesting scheduling method. We first define a cost function as a fitness value, and then we propose a grouping method that forms gene groups based on the processing layout and processing time. Finally, we validate the effectiveness of the proposed method through computational experiments.

1. [1] T. Sakaguchi, T. Tanaka, Y. Shimizu, and N. Uchiyama, “A hybrid metaheuristic for scheduling problem in sheet metal processing,” Trans. of the JSME, Vol.83, No.846, pp. 16-00333, doi:10.1299/transjsme.16-00333, 2017 (in Japanese).
2. [2] N. Christofides and C. Whitlock, “An algorithm for two-dimensional cutting problems,” Operations Research, Vol.25, No.1, pp. 30-44, doi:10.1287/opre.25.1.30, 1977.
3. [3] A. Lodi, S. Martello, and D. Vigo, “Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems,” INFORMS J. on Computing, Vol.11, No.4, pp. 345-357, doi:10.1287/ijoc.11.4.345, 1999.
4. [4] E. Hopper and B. C. H. Turton, “An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem,” European J. of Operational Research, Vol.128, No.1, pp. 34-57, doi:10.1016/S0377-2217(99)00357-4, 2001.
5. [5] M. K. Omar and K. Ramakrishnan, “Solving non-oriented two dimensional bin packing problem using evolutionary particle swarm optimisation,” Int. J. of Production Research, Vol.51, No.20, pp. 6002-6016, doi:10.1080/00207543.2013.791754, 2013.
6. [6] A. Lodi, S. Martello, and D. Vigo, “Recent advances on two-dimensional bin packing problems,” Discrete Applied Mathematics, Vol.123, No.1-3, pp. 379-396, doi:10.1016/S0166-218X(01)00347-X, 2002.
7. [7] 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, doi:10.1287/opre.1060.0293, 2006.
8. [8] A. Martinez-Sykora, R. Alvarez-Valdes, J. Bennell, and J. M. Tamarit, “Constructive procedures to solve 2-dimensional bin packing problems with irregular pieces and guillotine cuts,” Omega, Vol.52, pp. 15-32, doi:10.1016/j.omega.2014.10.007, 2015.
9. [9] G. Chrissolouris, N. Parakostas, and D. Mourtzis, “A decision-making approach for nesting scheduling: a textile case,” Int. J. of Production Research, Vol.38, No.17, pp. 4555-4564, doi:10.1080/00207540050205299, 2010.
10. [10] J. N. D. Gupta, “Two-stage, hybrid flowshop scheduling problem,” J. of the Operational Research Society, Vol.39, No.4, pp. 359-364, doi:10.1057/jors.1988.63, 1988.
11. [11] J. N. D. Gupta, A. M. A. Hariri, and C. N. Potts, “Scheduling a two-stage hybrid flow shop with parallel machines at the first stage,” Annals of Operations Research, Vol.69, No.0, pp. 171-191, doi:10.1023/A:1018976827443, 1997.
12. [12] C. N. Potts, S. V. Sevast’janov, V. A. Strusevich, L. N. Van Wassenhove, and C. M. Zwaneveld, “The two-stage assembly scheduling problem: complexity and approximation,” Operations Research, Vol.43, No.2, pp. 346-355, doi:10.1287/opre.43.2.346, 1995.
13. [13] A. Tozkapan, K. Ömer, and C.-S. Chung, “A branch and bound algorithm to minimize the total weighted flowtime for the two-stage assembly scheduling problem,” Computers & Operations Research, Vol.30, No.2, pp. 309-320, doi:10.1016/S0305-0548(01)00098-3, 2003.
14. [14] E. Torabzadeh and M. Zandieh, “Cloud theory-based simulated annealing approach for scheduling in the two-stage assembly flowshop,” Advances in Engineering Software, Vol.41, No.10-11, pp. 1238-1243, doi:10.1016/j.advengsoft.2010.06.004, 2010.
15. [15] F. S. Al-Anzi and A. Allahverdi, “A self-adaptive differential evolution heuristic for two-stage assembly scheduling problem to minimize maximum lateness with setup times,” European J. of Operational Research, Vol.182, No.1, pp. 80-94, doi:10.1016/j.ejor.2006.09.011, 2007.
16. [16] Y. Tanimizu, K. Amano, K. Harada, C. Ozawa, and N. Sugimura, “Multi-Objective Production and Transportation Scheduling Considering Carbon Dioxide Emissions Reductions in Dynamic Supply Chains,” Int. J. Automation Technol., Vol.6, No.3, pp. 322-330, doi:10.20965/ijat.2012.p0322, 2012.
17. [17] T. Sakaguchi, K. Matsumoto, and Y. Shimizu, “Study on nesting scheduling for sheet metal processing (Improvement of nesting method by parts reallocation),” Trans. of the JSME, Vol.81, No.825, pp. 14-00640, doi:10.1299/transjsme.14-00640, 2015 (in Japanese).
18. [18] T. Sakaguchi, T. Murakami, S. Fujita, and Y. Shimizu, “A scheduling method with considering nesting for sheet metal processing,” Proc. of 2012 ASME/ISCIE Int. Symp. on Flexible Automation, pp. 317-320, doi:10.1115/ISFA2012-7197, 2012.
19. [19] T. Sakaguchi, H. Ohtani, and Y. Shimizu, “Genetic Algorithm Based Nesting Method with Considering Schedule for Sheet Metal Processing,” Trans. of the Institute of Systems, Control and Information Engineers, Vol.28, No.3, pp. 99-106, doi:10.5687/iscie.28.99, 2015.
20. [20] Y. Shimizu, T. Sakaguchi, and T. Pralomkarn, “Multi-objective analysis applied to mixed-model assembly line sequencing problem through elite induced evolutionary method,” J. of Advanced Mechanical Design, Systems, and Manufacturing, Vol.6, No.5, pp. 647-660, doi:10.1299/jamdsm.6.647, 2012.
21. [21] D. E. Goldberg and R. Lingle Jr, “Alleles, loci, and the traveling salesman problem,” Proc. of the first Int. Conf. on Genetic Algorithms and Their Applications, Lawrence Erlbaum, pp. 154-159, 1985.