ALT SINIR TEMELİNE DAYALI AĞIRLIKLI TAVLAMA YÖNTEMİ İLE KUTULAMA PROBLEMİNİN ÇÖZÜMÜ
Journal Title: Mehmet Akif Ersoy Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi - Year 2018, Vol 5, Issue 3
Abstract
Bu çalışmada bir boyutlu kutulama problemi için melez yeni bir sezgisel çözüm yöntemi sunulmuştur. Önerilen yaklaşımda, başlangıç çözümü oluşturmak için alt sınıra dayalı sezgisel bir başlangıç çözüm algoritması önerilmiştir. Önerilen sezgisel ile birlikte literatürde yer alan diğer yerleştirme algoritmaları ele alınmış, elde edilen sonuçlar literatürde ulaşılan sonuçlarla karşılaştırılmıştır. Başlangıç çözümü sonrası elde edilen çözüme ağırlıklı tavlama yöntemiyle birlikte yer değiştirme algoritmaları uygulanmış ve kullanılan kutu sayısını minimize etmek amaçlanmıştır. Literatürde yer alan test kümeleri çözülmüş, çözüm süreleri ve elde edilen sonuçlar bilinen en iyi sonuçlarla ve geliştirilen diğer yöntemlerle karşılaştırılmıştır. Literatür ile yapılan karşılaştırmalarda önerilen sezgisel yöntemin daha kısa sürede çözüme ulaştığı gözlemlenmiştir. Ayrıca çözülen test kümesinin 2 örneğinde literatürdeki en iyi bilinen çözümden daha iyi bir çözüm elde edildiği gözlemlenmiştir. EXTENDED SUMMARY Background The bin packing problem, which is a combinatorial optimization problem with some similarities with the classical knapsack problems, is defined in different forms such as stock-cutting, vehicle loading, air cargo loading, container loading, scheduling, knapsack problem depending on the application being discussed. The bin packing problem, which is the problem of how to best locate the objects with the least usable length, area or volume, is classified as one, two or three dimensional according to the number of dimensions used. Regardless of the size of the bin packing problem, the solution is a non-polynomial NP-hard problem. This problem is confronted in many areas such as logistics, textile, and computer science in real life. While there are exact solutions for small scale problems, it is not possible to find an exact solution for large scale problems. Heuristic methods such as genetic algorithms, simulated annealing, weighted simulated annealing, tabu search are the most used solution approaches in the literature to obtain optimal or near optimal solutions for large scale problems. Research Problem In this study, one-dimensional bin-packing problem is considered where it is aimed to place objects in a single dimension with a minimum length within a certain length in one dimensional bin packing problems. Methodology In this study, a new two-stage, heuristic and hybrid solution method is presented for one dimensional bin packing problem. A heuristic initial solution algorithm based on the lower bound is used to create the initial solution. As the second stage of the problem solution phase, weights were assigned to the elements together with the weighted annealing method and the initial solutions were rearranged using swapping operations. Along with the weighted annealing and swapping operations, fewer number of bins have been used than the total number of bins used for the initial solution. In this study, Swap (1,0), Swap (1,1) and Swap (1,2) algorithms are used as swapping operations. Literature Review For the one dimensional bin-packing problem, a similar two-stage solution method is used by Loh et al (2006) where the initial solutions are obtained by using first fit decreasing, a weighted annealing method is used with swapping operations whereas Swap(2,2) is also used. In our study, the point of origin is to show that better results in a shorter time could be obtained than the results given in Loh et al (2006). Results and Conclusions The test sets in the literature are solved, the resolution times and the results obtained are compared with the best known solution in the literature and other developed methods. In comparisons with Loh et al (2006), it has been observed that the proposed heuristic method achieves the solutions in a shorter time. In addition, two solutions of the solved test set yielded better solutions than the best known solution of Loh et al (2006). In this context, the analysis suggested that the proposed two-stage, heuristic and hybrid solution approach is a promising approach. As a further study, this method can be investigated for two-dimensional and three-dimensional bin packing problems. In addition, it may contribute to the development of a new perspective in the research studies on the solutions of combinatorial problems such as traveling salesman problem, knapsack problem, maximum satisfaction problem and vehicle routing problem.
Authors and Affiliations
Neriman İNAK, Sezai TOKAT, Kenan KARAGÜL
Keywords
Related Articles
- EP ID EP445428
- DOI 10.30798/makuiibf.414467
- Views 119
- Downloads 0
SAĞLIK HİZMETLERİNDE EKONOMİK DEĞERLENDİRME TEKNİKLERİ ÜZERİNE BİR İNCELEME
Günümüzde sağlık harcamaları pek çok sebebe bağlı olarak hızlı bir şekilde artış göstermektedir. Bu artışın arkasında yatan temel nedenlerin başında teknolojik gelişmeler, hizmet kalitesindeki iyileşmeler ve doğumda bekl...
MERMER SEKTÖRÜ İŞLETMELERİNİN MUHASEBE-FİNANSMAN SORUNLARI VE ÇÖZÜM ÖNERİLERİ GELİŞTİRMEYE YÖNELİK BİR ARAŞTIRMA
Mermer sektörünün doğal bir hammaddeye bağımlı olarak çalışması nedeniyle üretim süreçleri oldukça zor ve karmaşıktır. Bu nedenle mermer sektöründeki işletmelerin de diğer işletmelerden farklı, kendine has bazı özellikle...
MİTOLOJİ VE İNANIŞLAR IŞIĞINDA TÜRK KÜLTÜRÜNDE HURMA AĞACI (PHOENIX DACTYLIFERA L.) VE SEMBOLLERİ
Ağaçlar insanoğlu var olduğundan bu yana yaşamış olan pek çok medeniyet tarafından kutsal kabul edilmiştir. Bu saygınlığın ve kutsallığın en önemli sebepleri; ağacın yerin altına kadar inen kökleri, buna tezat olarak da...
İBN-İ HALDUN’DA ASABİYET İLE DEVLET VE MÜLK İLİŞKİSİ
Toplumların varlıklarını refah ve güven içinde devam ettirebilmeleri, öncelikle kendi içindeki millet olma bilincini geliştirmesi ve bir arada yaşama şuuruna sahip olmasına bağlıdır. Çünkü ortak değerler üretip bunlara g...
THE EFFECT OF ACCOMMODATION ENTERPRISES WORKERS' PERCEPTION OF SERVANT LEADERSHIP ON ORGANIZATIONAL IDENTIFICATION: THE CASE OF KONYA
Servant leadership perceptions of employees affect organizational identification levels either directly or indirectly. The purpose of this study is to examine the relationship between servant leadership and organizationa...