Kesme ve Paketleme problemleri ve araştırmaya yönelik bir metot geliştirilmesi ve bu metodun etkinliğinin sınanması

Abstract

Yöneylem Araştırması alanında, en önemli problemlerden biri de Kesme ve Paketleme problemleridir. Kesme ve Paketleme problemleri, tasarımdan, üretimin çeşitli sınıfından, dağıtım ve satışa kadar tüm iş alanlarında görülmektedir. Kombinatoryal optimizasyon alanında yer alan bu problemler, matematiksel çözümün çok zor olduğu, NP-Hard sınıfı problemler olarak bilinirler. Makul bir zamanda bu problemleri çözebilecek, herhangi bir çözüm metodu bilinmemektedir. Bu nedenle, son zamanlarda sezgisel (heuristic) tekniklerin kullanımı ön plana çıkmıştır. Bu çalışmanın ilk bölümünde, Kesme ve Paketleme problemlerinin, optimizasyon problemleri arasında, hangi sınıfa dahil olduğunu göstermek için, optimizasyon hakkında bilgi verilmiştir. Optimizasyon problemleri ve bunlara ilişkin çözüm metotları sınıflandırılmıştır. İkinci bölümde, Kesme ve Paketleme problemlerinin yerleştirme problemleri ile ilişkisi açıklanmış ve bu problemlerin çözüm metotlarının, Kombinatoryal Optimizasyon Problemleri çözüm metotları arasında yer aldığı gösterilmiştir. Son bölümde ise, düzgün dikdörtgensel parçalardan oluşan iki boyutlu Kesme ve Paketleme problemleri için sezgisel bir teknik geliştirilmiştir. Bu yaklaşımın adımları ve uygulanması kısmında oluşacak alternatifler açıklanmıştır. Çözümün geçerliliğini test etmek için, çeşitli örnekler kullanılmış ve ortaya çıkan sonuçlar karşılaştırılmıştır. ANAHTAR SÖZCÜKLER: Kombinatoryal Optimizasyon / Kesme ve Paketleme Problemleri / Sezgisel

One of the most important problems in Operational Research are Cutting and Packing problems. Cutting and Packing problems are seen in eveiy business areas as; in design, in some types of production, in delivery and sale. These problems, belonging to Combinatorial Optimization area, are known as NP-Hard class problems of which the mathematical solution is very hard. No solution method is known to solve these problems in a reasonable time. So using the heuristic techniques have gained importance and become popular recently. In the first part of this study, information about optimization is given to point out the class of Cutting and Packing problems between optimization problems. Optimization problems and the solution methods relating to these are classified. In the second part, the relation of Cutting and Packing problems with placement problems is explained and it is pointed out that, the solution methods of these problems are taking part between the solution methods of combinatorial optimization problems. In the last part, a heuristic technique is improved for two dimensional Cutting and Packing problems forming of regular rectangular parts. The future possible alternatives are explained in the steps and application part of this approachment. Various samples are used to test the validity of the solution and the conclusions are compared. KEY WORDS : Combinatorial optimization / Cutting and Packing Problems / heuristic