KESME VE PAKETLEME PROBLEMLERİ ÜZERİNE BİR İNCELEME

Cam, kağıt, tekstil, ağaç, metal, mermer, mobilya v.s. gibi sektörlerde görülen, uygun boyuttaki ana malzemenin seçimi, uygun kesim planlarının oluşturulabilmesi, bir seferde daha fazla ürünü bir yerden diğerine taşıma ve ürünleri palet, konteynır, kutu, araç, v.b. içersine yerleştirme problemleri, literatürde "Kesme ve Paketleme Problemleri" olarak birlikte ele alınmaktadır. Bu sektörlerde faaliyet gösteren işletmelerin maliyetleri düşürme çalışmalarında ana malzemenin en verimli şekilde kullanılması ve kesme kaybının en küçüklenmesi temel problemlerden biridir. Maliyetleri en küçüklemek adına yapılan araştırmalara ışık tutmak amacıyla kesme ve paketleme problemleri gruplandırılarak her grup içindeki çalışmalar da ayrıca tasnif edilmiştir. Bu çalışmadaki amaç, az çalışılan alanların önemini vurgulayarak dikkatleri bu alanlara çekmek ve araştırmalarda kullanılabilecek çözüm tekniklerinde üzerinde durulması gerekli faktörlerin benimsenmesini sağlamaktır.

A SURVEY ON CUTTING AND PACKING PROBLEMS

Producers operating in paper, textile, wood, metal, marble, furniture, etc. sectors are very much in stress because of the inventory costs of holding raw materials in stock. Their basic problems are: using the base material more efficiently and optimizing the cutting stock losses. Selection of appropriate size and the appropriate cutting plans of the material problems are mainly similar to the packing and loading problems and in literature all are said to be "Cutting and Packing Problems". In order to be useful to the researchers all the cutting stock problems were grouped and also all the studies within each group were classified too. The purpose of this study is: emphasizing the importance of less-studied areas, drawing attention to these areas and offering new techniques in optimizing the wastage rates to be used in the businesses.

___

  • Adakçı, S., (2001), "Stok Kesme Problemi: Alüminyum Sektöründe Uygulaması", Yüksek lisans tezi, İstanbul Teknik Üniversitesi, FBE, s.3.
  • Alfıeri, A., Velde, S., Woenginger, G., (2006), "Roll Cutting in the Curtain Industry, or: well--solvable allocation problem", European Journal of Operational Research,183, 1397--1404.
  • Akın G., Aras N., (2009), "Dikdörtgen Şekilli Malzeme Kesme Problemleri Üzerine Yapılan Mevcut Çalışmaların Analizi ve Sınıİlandırılması", 2.Mühendislik ve Teknoloji Sempozyumu, Çankaya Üniversitesi, Ankara.
  • Almeida, A.M.C., Martins, E.Q.V. ve Rodrigues, RD., (1998), "Optimal cutting directions and rectangle orientation algorithm" EJOR, 109, 660--671.
  • Alvarez--Valdes, R., Parajon, A. ve Tamarit, .M., (2002), "A tabu search algorithm for large--scale Guillotine (un)constrained two--dimensional cutting problems" COR, 29 (7), 925--947
  • Amaral, A. ve Wright, MB., (2001), "Experiments with strategic oscillation algorithm for the pallet loading problem" IJPR, 39(11), 2341-2351.
  • Arslanov, M.Z., (2000), "Continued fractions in optimal cutting of rectangular sheet into equal small rectangles" EJOR, 125 (2), 239--248.
  • Babu, A.R. ve Babu, N.R., (1999), "Effective nesting of rectangular parts in multiple rectangular sheets using genetic and heuristic algorithms" IJPR, 37 (7), 1625-1643.
  • Bhattacharya, S., Roy, R. ve Bhattacharya, S., (1998), "An exact depth-flrst algorithm for the pallet loading problem" EJOR, 110 (3), 610--625.
  • Binkley, K. J. ve Hagiwara, M., (2007), "Applying self-adaptive evolutionary algorithms to two-dimensional packing problems using four comers' heuristic" EJOR, 183, 1230--1248.
  • Burke, E. ve Kendall, G., (1998), "Comparison of meta heuristic algorithms for clustering rectangles" CIE, 37(1-2), 383-386.
  • Carnieri, C.; G. A. Mendoza; L. G. Gavinho; (1994), "Solution Procedures for Cutting Lumber into Furniture Parts", European Journal of Operational Research, Vol. 73, pp. 495-501.
  • Chambers M.L., Dyson R.G., (1976), "The cutting stock problem in the flat glass industry selection of stock sizes", Operational Research Quarterly 27 (4), 949-- 957.
  • Chan, F. T. S., Au, K.C., Chan, L.Y. ve Lau, T.L., (2007), "Using genetic algorithms to solve quality-related bin packing problem" Robotics and Computer-- Integrated Manufacturing, 23, 71--8 l.
  • Chauhan, S.S., Martel, A., D'Amour, S., (2008), "Roll assortment optimization in paper mill: An integer programming approach", Computers and Operations Research, 614-627.
  • Chauny F., Loulou R., Sadones S., Soumis F., (1991), "A Two-phase heuristic for the Two-dimensional Cutting-Stock Problem", Journal of The Operational Research Society, 42, (1) 39-47.
  • Chen, D. ve Huang, W., (2007 ), "A new heuristic algorithm for constrained rectangle--packing problem" Asia Pacific Journal of Operational Research, 24(4), 463--478.
  • Chryssolouris,G., Papakostas, N. ve Mourtzis, D., (2000), "A decision-making approach for nesting scheduling: textile case" IJPR, 38 (17), 4555-4564.
  • Chu, C.; J. Antonio; (1999), "Approximation Algorithms to Solve Real-Life Multicriteria Cutting Stock Problems", Operations Research, Vol. 47, No. 4, JulyAugust, pp. 495--508.
  • Cizman, A. ve Cernetic, J., (2003), "Improving competitiveness in veneers production by simple to use DSS" EJOR.
  • Correia M. H, Oliveira J. F, Ferreira J. S., (2004), "Reel and sheet cutting at paper mill", Computer Operations Research,31:1223--1243.
  • Csirik, J. ve Woeginger, J., (1997), "Shelf algorithms for on-line strip packing" IPL, 63 (4), 171--175.
  • Cung, V.D., Hifi, M. ve Le Cun, B., (2000), "Constrained two-dimensional cutting stock problems best-first branch-and-bound algorithm" ITOR, (3), 185--210.
  • Dyckhoff, H.,(l990), "A Typology of Cutting and Packing Problems", European Journal of Operational Research, 44, 145--159.
  • Dyckhoff H., Finke U., (1992), "Cutting and Packing in Production and Distributions", Physica Verlag, Heidelberg.
  • Ergün K., (2004), "Kesme ve Paketleme Problemleri ve Araştırmaya Yönelik bir Metot Geliştirilmesi ve Bu Metodun Etkinliğinin S1nanmas1", Yüksek Lisans Tezi, Balıkesir Üniversitesi, FBE, Endüstri Mühendisliği ABD.
  • Ertay, T., Ruan, D. ve Tuzkaya, U. R., (2006), "Integrating data envelopment analysis and analytic hierarchy for the facility layout design in manufacturing systems" Information Sciences, 176, 237--262.
  • Faggioli, E. ve Bentivoglio, C.A., (1998), "Heuristic and exact methods for the cutting sequencing problem" EJOR, 110 (3), 564-575.
  • Faina, L., (1999), "An application of simulated annealing to the cutting stock problem" EJOR, 114 (3), 542--556.
  • Farley, A., (1983), "Trim--Loss Pattern Rearrangement and Its Relevance to the Flat-- Glass Industry", European Journal of Operational Research, Vol. 14, pp. 386--392.
  • Farley, A., (1988), "Mathematical programming models for cutting stock problems in the clothing industry", Journal of Operational Research Society, Vol.3 9, pp.4l-53.
  • Gasimov, R. N., Sipahioğlu, A. ve Saraç, T., (2004), "1.5 boyutlu stok malzemesi seçimi problemi için çok ölçütlü bir karar modeli ve çözüm yaklaD DmD" Yöneylem Araştırması/Endüstri Mühendisliği XXI Ulusal Kongresi, Gaziantep Adana.
  • Gasimov R.N., Sipahioğlu A., Saraç T., (2007), "A multi-objective programming approach to 1.5 dimensional assortment problem", European Journal of Operational Research, 179, 64--79.
  • Gilmore, F.C., Gomory, R.E., (1961), "A linear programming approach to the cuttingstock problem", Operations Research 9, 849--859.
  • Gilmore, F.C., Gomory, RE, (1963), "A linear programming approach to the cuttingstock problem--Part ll", Operations Research 11, 863--888.
  • Gilmore, F.C., and Gomory RE, (1965) "Multistage cutting stock problems of two and more dimensions", Operations Research 13, 94--120.
  • Gilmore, F.C., and Gomory, R.E. (1966), "The theory and computation of knapsack functions", Operations Research 14, 1045--1074.
  • Gonçalves, J. F., (2007), "A hybrid genetic algorithm-heuristic for twodimensional orthogonal packing problem" EJOR, 183, 1212--1229.
  • Gradisar, M.,Jesenko, J., Resinovic, G., (1997), "Optimization of Roll Cutting in Clothing Industry", Computers Ops. Res. Vol. 24, No.lO, 945-953.
  • Hadjiconstantinou, E. ve Iori, M., (2007), "A hybrid genetic algorithm for the twodimensional single large object placement problem" EJOR, 183, 1150--1166.
  • Haessler R.W., Sweeney F.E., (1991), "Cutting Stock Problems and Solution Procedures" European Journal of Operational Research, 54, (2) 141--150.
  • Hannssmann, F., (1959), "Optimal Inventory Location and Control in Production and Distribution Networks", Operations Research, Vol. 7, No. 4, 483-498.
  • Harjunkoski, 1., Westerlund, T., (1998), "Enlarging the Trim--Loss Problem to Cover the Raw Paper Mill", Computers chem.Eng., vol:22, Suppl, s1019--s1022, Great Britain.
  • Healy, F., Creavin, M. ve Kuusik, A., (1999), "An optimal algorithm for rectangle placemen ORL, 24 (1--2), 73-- 80.
  • Herz, .C., (1972), "Recursive Computational Procedure for Two-dimensional Stock Cutting" IBM Journal ofResearch and Development 16, 462--469.
  • Hifi, M., (1997a), "An improvement of Viswanathan and Bagchi's exact algorithm for constrained two-dimensional Cutting stock" COR, 24 (8), 727--736.
  • Hifi, M., (1997b), "The DH/KD algorithm: hybrid approa Hinxman A.I., (1980), "The trim-loss and Assortment problems: survey", European Journal of Operational research (1) s:8-18.
  • Hopper, E., Turton, B., (1999), "A genetic algorithm for 2D industrial packing problem" CIE, 37 (1-2), 375-378.
  • Hung, C.Y. ve Sumichrast, R.T., (2000), "A multi expert system for material cutting plan generation" ESA, 19, 19- 29.
  • Imreh, C., (2001), "Online strip packing with modifiable boxes" ORL, 29, 79-85.
  • Johnson, M. P., Rennick, C., and Zak, E., (1997), "Skiving addition to the cutting stock problem in the paper industry", SIAM Review, 39(3), 472-483.
  • Kantorovich, L. V., (1960), "Mathematical Methods of Organizing and Planning Production", reprinted in Management Science, vol.6, pp. 366-422.
  • Lee, H.F. ve Sewell, E.C., (1999), "The strip-packing problem for boat manufacturing firm" IIE run., 31 (7), 639-651.
  • Lee, S. L., (2008), "A decision support system for luggage typesetting" ESA, 35, 1620--1627.
  • Leung, T.W., Yung, CH. and Trout, M.D., (2001), "Applications of Genetic Search and Simulated Annealing to The Two-Dimensional Non-Guillotine Cutting Stock Problem", Computers Industrial Engineering, vol.40, pp.201-214.
  • Lin, C. C., (2006), "A genetic algorithm for solving the two-dimensional assortment problem" CIE, 50, 175--184.
  • Liu, D. ve Teng, H., (1999), "An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles" EJOR, 112 (2), 413-420.
  • Martens, ., (2004), "Two Genetic Algorithms to Solve Layout Problem in the Fashion Industry", European Journal of Operational Research, Vol. 154, pp. 304- 322.
  • Morabito, R. ve Garcia, V., (1998), "The cutting stock problem in hardboard industry: case study" COR, 25 (6), 469-485.
  • Morabito, R. ve Arenales, M.,(2000), "Optimizing the cutting of stock plates in furniture company" IJPR, 38 (12), 2725-2742.
  • Mukhacheva, E. A. ve Mukhacheva, A. S., (2004), "The Rectangular Packing Problem: Local Optimum Search Methods Based on Block Structures" Automation and Remote Control, 65(2) 248--257.
  • Onursal F.S., (2014), "Kesme Kaybı ve Stok Maliyetleri Optimizasyonuna Yönelik Bir Model Önerisi", Doktora Tezi, Kocaeli Üniversitesi, Fen Bilimleri Enstitüsü, Kocaeli, 10056042.
  • Parada, V., Sepulveda, M., Solar, M. ve Gomes, A., (1998), "Solution for the constrained guillotine cutting problems by simulated annealing" COR, 25(1), 37--47.
  • Pentico D.W., (2008), "The assortment problem: survey", European Journal of Operational Research, 190, 295--309.
  • Pierce, .F., (1964), "Some Large Scale Production Problems in the Paper Industry", Prentice--Hall, Englewood Cliffs, NY.
  • Raffensperger, .F., (2010), "The generalized assortment and best cutting stock length problems", Intl. Trans. In Op. Res. 17, 35--49.
  • Rönnqvist, M., (1995), "A Method for the Cutting Stock Problem with Different Oualities", European Journal of Operational Research, Vol. 83, 1995, pp. 57--68.
  • Sadowski W., (1959), "A few remarks on the assortment problem", Management Science (1) 13--24.
  • Salto, C., Alba, E. ve Molina, J. M., "Analysis of distributed genetic algorithms for solving cutting problems"1TOR, 13, 403--423, 2006.
  • Saraç, T., (2001), "Bir Kutu Fabrikası için Standart Kağıt Enlerinin Belirlenmesi", Yüksek lisans tezi, Osmangazi Universitesi, FBE, s.4.
  • Scheithauer, G. ve Sommerveib, U., (1998), "4 block heuristic for the rectangle packing problem" EJOR, 108 (3), 509--526.
  • Schnecke, V. ve Vornberger, 0., (1997), "Hybrid Genetic Algorithms for Constrained Placement Problems" IEEE Tran. EC, (4), 266--277.
  • Soke, A. ve Bingul, Z., (2006), "Hybrid genetic algorithm and simulated annealing for two--dimensional nonguillotine rectangular packing problems" Engineering Applications ofArtificial Intelligence, 19, 557--567.
  • Tiwari, S. ve Chakraborti, N., (2006), "Multi--objective optimization of twodimensional cutting problem using genetic algorithms" Journal ofMaterials Processing Technology, 173, 384--393.
  • Tombus, O., vd., (2010), "A New Network Flow Model for Determining the Assortment of Roll Types in Packaging Industry", IEEE, 1231-1235.
  • Westerlund, T., Isaksson, J. ve Harjunkoski, I., (1998), "Solving two-dimensional trim-loss problem with MILP" EJOR, 104, 572--58 1.
  • Yang, T. ve Kuo, C., (2003), "A hierarchical AHP/DEA methodology for the facilities layout design problem" EJOR, 147, 128--136.
  • Zhang, D.F., Chen, S. D. ve Liu, Y. J., (2007), "An improved heuristic recursive strategy based on genetic algorithm for the strip rectangular packing problem" Acta Automatica Sinica, 33(9), 91 1-916.
  • Zilla, S. S. ve Ittai, W., (1994), "The One Dimensional Cutting Stock Problem Using Two Objectives" The Journal ofthe Operational Research Society, 45(2), 231--236