Abstract
Bu çalışmada NP-Zor bir problem olan tek boyutlu değişken ölçekli kutulama problemi ele alınmaktadır. Bu çalışmada amaç, kullanılan kutuların kapasitelerinin toplamını ve kullanılan kutu sayısını en aza indiren verimli bir çözüm bulmak, böylece şirketin depolama politikasını optimize etmek ve depoda yer tasarrufu sağlamaktır. Gerçek bir deponun problemini çözmek için üç farklı yöntem: i) İlk Bulduğun Boşluğu Doldur (İBBD), ii) En İyi Boşluğu Doldur (EİBD) ve iii) Sonraki Boşluğu Doldur (SBD) algoritmaları kullanılmıştır. Deponun veri seti, farklı boyutlarda çeşitli öğelerden oluşmakta olup amaç bu öğeleri en verimli şekilde kutulara tahsis etmektir. Deneylerden elde edilen sonuçlara göre, İBBD ve EİBD algoritmaları SBD algoritmasından daha iyi olmakla beraber, her üç algoritmanın da mevcut depo uygulamasına kıyasla depolama alanı kullanımını azaltmada ve alandan yararlanmayı arttırmada başarılı olduğu gösterilmiştir.
Keywords
Depo Değişken Boyutlu Kutulama Problemi İlk Bulduğun Boşluğu Doldur En İyi Boşluğu Doldur Sonraki Boşluğu Doldur
References
- Aarts, E., & Korst, J. (2003). Simulated Annealing and Boltzmann Machines. Wiley.
- Alenezi, Q., Aboelfotoh, H., Albdaiwi, B., & Almulla, M.A. (2015). Heuristics for the Variable Sized Bin Packing Problem Using a Hybrid P-System and CUDA Architecture. Computer Science Department, Kuwait University. Retrieved from: https://arxiv.org/abs/1602.08735
- Borgulya, I. (2024). A hybrid estimation of distribution algorithm for the offline 2D variable-sized bin packing problem. Central European Journal of Operations Research, 32, 45–65. https://doi.org/10.1007/s10100-023-00858-0
- Boyar, J., Kamali, S., Larsen, K.S., & López-Ortiz, A. (2013). Online Bin Packing with Advice. Algorithmica, 74, 507-527. doi: https://doi.org/10.48550/arXiv.1212.4016
- Coffman Jr, E.G., Garey, M.R., & Johnson, D.S. (1984). Approximation Algorithms for Bin-Packing — An Updated Survey. Algorithm Design for Computer System Design. Editors: Ausiello, G., Lucertini, M., & Serafini, P., Vienna, Springer, 49-106. Retrieved from: https://link.springer.com/chapter/10.1007/978-3-7091-4338-4_3
- Dökeroğlu T. (2017). Bir boyutlu kutulama probleminin eniyilenmesi için hiper-sezgisel paralel bir algoritma, Balıkesir Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 19(1), 1-11. doi: https://doi.org/10.25092/baunfbed.319992
- Dyckhoff, H. (1990). A typology of cutting and packing problems. European Journal of Operational Research, 44, 145-159. doi: https://doi.org/10.1016/0377-2217(90)90350-K
- Grondys, K. (2009). ABC Analysis in Spare Parts Warehouse. Polish Journal of Management Studies, 3, 147-156. Retrieved from: https://econpapers.repec.org/article/pczjournl/v_3a3_3ay_3a2009_3ai_3a1_3ap_3a147-156.htm
- Gupta, A., Guruganesh, G., Kumar, A., & Wajc, D. (2018). Fully-Dynamic Bin Packing with Limited Repacking. ArXiv, abs/1711.02078. Retrieved from: https://doi.org/10.48550/arXiv.1711.02078
- Haouari, M., & Serairi, M. (2009). Heuristics for the variable sized bin-packing problem. Computers & Operations Research, 36, 2877-2884. doi: https://doi.org/10.1016/j.cor.2008.12.016
- Hemmelmayr, V., Schmid, V., & Blum, C. (2012). Variable neighbourhood search for the variable sized bin packing problem. Computers & Operations Research, 39, 1097-1108. doi: https://doi.org/10.1016/j.cor.2011.07.003
- Jin, Z., Ito, T., & Ohno, K. (2003). The Three-Dimensional Bin Packing Problem and Its Practical Algorithm. JSME International Journal Series C Mechanical Systems, Machine Elements and Manufacturing, 46, 60-66. doi: https://doi.org/10.1299/jsmec.46.60
- Kang, J., & Park, S. (2003). Algorithms for the variable sized bin packing problem. European Journal of Operational Research, 147, 365-372. doi: https://doi.org/10.1016/S0377-2217(02)00247-3
- Karp, R.M. (1992). On-line algorithms versus off-line algorithms: How much is it worth to know the future?. International Computer Science Institute, Berkeley, California, Technical report, TR-92-044. Retrieved from: https://www1.icsi.berkeley.edu/pubs/techreports/TR-92-044.pdf
- Lodi, A., Martello, S., Monaci, M., & Vigo, D. (2013). Two-Dimensional Bin Packing Problems. Editor: Paschos, V. T. Paradigms of Combinatorial Optimization, 107-129, Wiley, GB. Retrieved from https://onlinelibrary.wiley.com/doi/10.1002/9781118600207.ch5
- Martello, S., & Vigo, D. (1998). Exact Solution of the Two-Dimensional Finite Bin Packing Problem. Management Science, 44, 388-399. Retrieved from: https://www.jstor.org/stable/2634676
- Pinto, A. R. F., Nagano, M. S., & Boz, E. (2023). A classification approach to order picking systems and policies: Integrating automation and optimization for future research. Results in Control and Optimization, 12, 100281. doi: https://doi.org/10.1016/j.rico.2023.100281
- Tompkins, J.A., & Smith, J.D. (1998). The Warehouse Management Handbook. Tompkins Press, Raleigh, North Carolina.
- Wäscher, G., Haußner, H., & Schumann, H. (2007). An improved typology of cutting and packing problems. European Journal of Operational Research, 183, 1109-1130. doi: https://doi.org/10.1016/j.ejor.2005.12.047
Abstract
This study considers the one-dimensional variable-sized bin packing problem (VSBPP) which is an NP-Hard problem. In this study, the objective is to find an efficient solution that minimizes both the total capacity of the bins used and the number of bins required, thereby optimizing the company's storage policy and saving space within the warehouse. Three algorithms are employed to solve a real warehouse’s VSBPP: i) First Fit Decreasing (FFD), ii) Best Fit Decreasing (BFD), and iii) Next Fit Decreasing (NFD). The warehouse dataset includes items of various sizes, and the goal is to allocate these items into bins most efficiently. Experimental results demonstrate that the FFD and BFD algorithms outperform the NFD algorithm. Furthermore, all three algorithms significantly reduce storage space usage and improve space utilization compared to the warehouse's current practices.
Keywords
Warehouse Variable-Sized Bin Packing Problem First Fit Decreasing Best Fit Decreasing Next Fit Decreasing
References
- Aarts, E., & Korst, J. (2003). Simulated Annealing and Boltzmann Machines. Wiley.
- Alenezi, Q., Aboelfotoh, H., Albdaiwi, B., & Almulla, M.A. (2015). Heuristics for the Variable Sized Bin Packing Problem Using a Hybrid P-System and CUDA Architecture. Computer Science Department, Kuwait University. Retrieved from: https://arxiv.org/abs/1602.08735
- Borgulya, I. (2024). A hybrid estimation of distribution algorithm for the offline 2D variable-sized bin packing problem. Central European Journal of Operations Research, 32, 45–65. https://doi.org/10.1007/s10100-023-00858-0
- Boyar, J., Kamali, S., Larsen, K.S., & López-Ortiz, A. (2013). Online Bin Packing with Advice. Algorithmica, 74, 507-527. doi: https://doi.org/10.48550/arXiv.1212.4016
- Coffman Jr, E.G., Garey, M.R., & Johnson, D.S. (1984). Approximation Algorithms for Bin-Packing — An Updated Survey. Algorithm Design for Computer System Design. Editors: Ausiello, G., Lucertini, M., & Serafini, P., Vienna, Springer, 49-106. Retrieved from: https://link.springer.com/chapter/10.1007/978-3-7091-4338-4_3
- Dökeroğlu T. (2017). Bir boyutlu kutulama probleminin eniyilenmesi için hiper-sezgisel paralel bir algoritma, Balıkesir Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 19(1), 1-11. doi: https://doi.org/10.25092/baunfbed.319992
- Dyckhoff, H. (1990). A typology of cutting and packing problems. European Journal of Operational Research, 44, 145-159. doi: https://doi.org/10.1016/0377-2217(90)90350-K
- Grondys, K. (2009). ABC Analysis in Spare Parts Warehouse. Polish Journal of Management Studies, 3, 147-156. Retrieved from: https://econpapers.repec.org/article/pczjournl/v_3a3_3ay_3a2009_3ai_3a1_3ap_3a147-156.htm
- Gupta, A., Guruganesh, G., Kumar, A., & Wajc, D. (2018). Fully-Dynamic Bin Packing with Limited Repacking. ArXiv, abs/1711.02078. Retrieved from: https://doi.org/10.48550/arXiv.1711.02078
- Haouari, M., & Serairi, M. (2009). Heuristics for the variable sized bin-packing problem. Computers & Operations Research, 36, 2877-2884. doi: https://doi.org/10.1016/j.cor.2008.12.016
- Hemmelmayr, V., Schmid, V., & Blum, C. (2012). Variable neighbourhood search for the variable sized bin packing problem. Computers & Operations Research, 39, 1097-1108. doi: https://doi.org/10.1016/j.cor.2011.07.003
- Jin, Z., Ito, T., & Ohno, K. (2003). The Three-Dimensional Bin Packing Problem and Its Practical Algorithm. JSME International Journal Series C Mechanical Systems, Machine Elements and Manufacturing, 46, 60-66. doi: https://doi.org/10.1299/jsmec.46.60
- Kang, J., & Park, S. (2003). Algorithms for the variable sized bin packing problem. European Journal of Operational Research, 147, 365-372. doi: https://doi.org/10.1016/S0377-2217(02)00247-3
- Karp, R.M. (1992). On-line algorithms versus off-line algorithms: How much is it worth to know the future?. International Computer Science Institute, Berkeley, California, Technical report, TR-92-044. Retrieved from: https://www1.icsi.berkeley.edu/pubs/techreports/TR-92-044.pdf
- Lodi, A., Martello, S., Monaci, M., & Vigo, D. (2013). Two-Dimensional Bin Packing Problems. Editor: Paschos, V. T. Paradigms of Combinatorial Optimization, 107-129, Wiley, GB. Retrieved from https://onlinelibrary.wiley.com/doi/10.1002/9781118600207.ch5
- Martello, S., & Vigo, D. (1998). Exact Solution of the Two-Dimensional Finite Bin Packing Problem. Management Science, 44, 388-399. Retrieved from: https://www.jstor.org/stable/2634676
- Pinto, A. R. F., Nagano, M. S., & Boz, E. (2023). A classification approach to order picking systems and policies: Integrating automation and optimization for future research. Results in Control and Optimization, 12, 100281. doi: https://doi.org/10.1016/j.rico.2023.100281
- Tompkins, J.A., & Smith, J.D. (1998). The Warehouse Management Handbook. Tompkins Press, Raleigh, North Carolina.
- Wäscher, G., Haußner, H., & Schumann, H. (2007). An improved typology of cutting and packing problems. European Journal of Operational Research, 183, 1109-1130. doi: https://doi.org/10.1016/j.ejor.2005.12.047
Details
| Primary Language | English |
|---|---|
| Subjects | Industrial Engineering |
| Journal Section | Research Articles |
| Authors | |
| Early Pub Date | April 16, 2025 |
| Publication Date | April 24, 2025 |
| Submission Date | February 7, 2024 |
| Acceptance Date | December 19, 2024 |
| Published in Issue | Year 2025 Volume: 33 Issue: 1 |
Cite
