İki boyutlu iki aşamalı kesme problemleri için matematiksel model tabanlı sezgisel yöntem

Öz

Bu çalışmada ana malzemelerin en uygun şekilde nasıl kesilmesi gerektiğinin belirlenmesini içeren iki boyutlu iki aşamalı giyotin kesme problemleri için farklı çözüm yaklaşımları geliştirilmiş ve uygulanmıştır. Yeni özelliklere sahip bir tamsayılı programlama modeli önerilmiştir. Uygun çözümler elde etmek için rastgele anahtar tabanlı bir genetik algoritma kullanılmış ve algoritma içinde yerel bir arama yapılarak melez bir yapı elde edilmiştir. Ayrıca, ardışık iki matematiksel modelin çözülmesi şeklinde iki aşamalı matematik model temelli sezgisel bir çözüm yöntemi önerilmiştir. Bu yöntemin ilk aşamasında, problemin gevşetilmiş hali çözülür; ikincisinde, elde edilen çözüm geliştirilir. Bu matematiksel modellerin çözümlerinin kısa sürede elde edilmesi, çözüm süreleri anlamında avantaj yaratmaktadır.

Anahtar Kelimeler

• Kesme problemleri
• Yerel arama
• Metasezgisel
• Giyotin kesim

Kaynakça

1. Referans 1 Dyckhoff, H., A typology of cutting and packing problems, European Journal of Operational Research 44, 145–159, 1978.
2. Referans 2 Delorme M., Lori M., Martello S., Bin packing and cutting stock problems: Mathematical models and exact algorithms, European Journal of Operational Research, 255, 1–20, 2016.
3. Referans 3 Dyckhoff, H., A New Linear Programming Approach to the Cutting Stock Problem, Operations Research, 29, 1092–1104, 1981.
4. Referans 4 Furini F., Martello S., Lori M., Yagiura M., Heuristic and exact algorithms for the interval minmax regret knapsack problem, INFORMS Journal on Computing 27 (2), 392–405, 2015.
5. Referans 5 Gilmore P. C., Gomory R. E., A linear programming approach to the cutting-stock problem, Operations Research, 9, 849–859, 1961.
6. Referans 6 Kasimbeyli N., Sarac T., Kasimbeyli R., A two-objective mathematical model without cutting patterns for one-dimensional assortment problems, Journal of Computational and Applied Mathematics, 235, 4663–4674, 2011.
7. Referans 7 Coffman E. G., Csirik J., Galambos G., Martello S., Vigo D., Handbook of combinatorial optimization, Springer, New York, A.B.D., 455–531, 2013.
8. Referans 8 Furini F., Malaguti E., Models for the two-dimensional two-stage cutting stock problem with multiple stock size Computers and Operations Research, 40, 1953–1962, 2013.

9. Referans 9 Gilmore P. C., Gomory R. E., Multistage cutting stock problems of two and more dimensions. Operations Research 13, 94–120, 1965.
10. Referans 10 Lodi A., Martello S., Vigo D., Recent Advances on Two-Dimensional Bin Packing Problems, Discrete Applied Mathematics, 123, 379–396, 2002.
11. Referans 11 Andrade R., Birgin E. G., Morabito R., Two-stage two-dimensional guillotine cutting stock problems with usable leftover, Intl. Trans. in Op. Res., 23, 121–145, 2016.
12. Referans 12 Lodi A., Martello S., Vigo D., Models and Bounds for Two-Dimensional Level Packing Problems, Journal of Combinatorial Optimization, 8, 363–379, 2004.
13. Referans 13 Lodi A., Martello S., Vigo D., Monaci M., Two-Dimensional Bin Packing Problems, In: Paradigms of combinatorial optimization: Problems and new approaches, Wiley and Blackwell, 107–129, 2014.
14. Referans 14 Martello S., Monaci M., Models and algorithms for packing rectangles into the smallest square, Computers and Operations Research, 63, 161–171, 2015.
15. Referans 15 Gasimov R. N., Sipahioglu A., Sarac T., A multi-objective programming approach to 1.5-dimensional assortment problem, European Journal of Operational Research, 179,64–79, 2007.
16. Referans 16 Chen C. S., Lee S. M., Shen Q.S., An analytical model for the container loading problem, European Journal of Operational Research, 80, 68–76, 1995.
17. Referans 17 Araujo L. J. P., Özcan E., Atkin J. A. D., Baumers M., Analysis of irregular three-dimensional packing problems in additive manufacturing: a new taxonomy and dataset, International Journal of Production Research, 57(18), 5920-5934, 2019.
18. Referans 18 Bean J. C., Genetic Algorithms and Random Keys for Sequencing and Optimization, ORSA Journal on Computing, 6, 154–180, 1994.
19. Referans 19 Beasley J. E., A Population heuristic for constrained two-dimensional non-guillotine cutting, European Journal of Operational Research, 156, 601–627, 2004.
20. Referans 20 Wei L., Zhang Z., Zhang D., Leung S.C.H., A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints, European Journal of Operational Research, 265, 843-859, 2018.
21. Referans 21 Meng T., Pan Q., An improved fruit fly optimization algorithm for solving the multidimensional knapsack problem, Applied Soft Computing, 50, 79-93, 2017.
22. Referans 22 Dodge M., MirHassani S. A., Hooshmand F., Solving two-dimensional cutting stock problem via a DNA computing algorithm, Natural Computing, 20, 145–159, 2021.
23. Referans 23 Chauny F., Loulou R., Sadones S., Soumis F., A two-phase heuristic for strip packing: Algorithm and probabilistic analysis, Operational Research Letters, 6(1), 25–33, 1987.
24. Referans 24 Delorme M., Lori M., Martello S., Logic based Benders’ decomposition for orthogonal stock cutting problems, Computers and Operations Research, 78, 290–298, 2017.
25. Referans 25 25. Mancapa V., Van Niekerk T. I., Hua T., A Genetic Algorithm for Two-Dimensional Strip Packing Problems, South African Journal of Industrial Engineering, 20(2), 145–162, 2009.
26. Referans 26 Bortfeldt A., A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces, European Journal of Operational Research, 172, 814–837, 2004.
27. Referans 27 Oliveira J. F., Junior A. N., Silva E., Carravilla M. A., A Survey on Heuristics for Two-Dimensional Rectangular Strip Packing Problems, Pesquisa Operacional, 36(2), 197–226, 2016.
28. Referans 28 Lodi A., Monaci M., Pietrobuoni E., Partial enumeration algorithms for Two-Dimensional Bin Packing Problem with guillotine constraints, Discrete Applied Mathematics, 217, 40-47, 2017.
29. Referans 29 Lori M., Lima V. L., Martello S., Miyazawa F. K., Exact solution techniques for two-dimensional cutting and packing, 289, 399-415, 2021.
30. Referans 30 Christensen H. I., Khan A., Pokutta S., Tetali P., Approximation and online algorithms for multidimensional binpacking: A survey, Computer Science Review, 24, 63-74, 2017.
31. Referans 31 Goncalves J. F., Resende M. G. C., Biased random-key genetic algorithms for combinatorial optimization, Journal of Heuristics, 17(5), 487–525, 2011.
32. Referans 32 Talbi E., Metaheuristics: From Design to Implementation, Wiley, New York, A.B.D, 2009.
33. Referans 33 Hifi M., Roucairol C., Approximate and exact algorithms for constrained (un) weighted two-dimensional two-staged cutting stock problems, Journal of Combinatorial Optimization 5, 465–494, 2001.