Изменена: 2025-03-04
Аннотация
This article is devoted to the well-known onedimensional packing problem - BPP. The problem is actual and may be found in many areas - logistics, industrial cutting and design, scheduling and other areas. BPP is an NP-hard problem and requires the development of heuristic solution methods. However, simple heuristics usually allow you to get not too good solutions with respect to the objective function. The authors propose a probabilistic variation of the simple "first fit decreasing" heuristic. The first approach suggests making the packaging of the next item in the FFD algorithm a random event with some probability - a parameter of the algorithm. And the second approach is to make nondeterm the packing process – we choose fit bin with some probability. So, first algorithm is Random Permutation with Parameter – RPP, and the second one – Random Bin with Parameter – RBP. The experiments prove that adding nondeterm strategy to a simple heuristic allow to improve the effectiveness of algorithm. Also, we detect that the behavior of algorithms significantly depends on kind of task. So-called “uniform” tasks are solved better with parameters close to 1, and triplet tasks an opposite shows the best results with algorithm’s parameters close to zero. In general, the proposed simple nondeterm algorithms allow us to obtain better solutions than the parent simple heuristic FFD.
Ключевые слова
Литература
1. Tsao Yu.Ch., Tai Jo.Y., Vu T.L., Chen Ts.H. Multiple bin-size bin packing problem considering incompatible product categories. Expert Systems with Applications. 2024. Т. 247. С. 123340.
2. Fischer C., Röglin H. Probabilistic analysis of online (class-constrained) bin packing and bin covering. Lecture Notes in Computer Science. 2018. Т. 10807 LNCS. С. 461-474.
3. Usmanova A.R., Valiakhmetova Yu.I. Osobennosti metoda poiska s zapretami dlya zadachi upakovki – Systems engineering and information technologies. 2022. Т.
4. № 2 (9). С. 37-42. 4. Usmanova A.R., Valiakhmetova Yu.I. Osobennosti zadaaach-tripletov v zadache upakovki. Systems engineering and information technologies. 2023. Т.
5. № 1 (10). С. 34-40. 5. Falkenauer E. A hybrid Grouping Genetic Algorithm for Bin Packing. Journal of Heuristics, Vol.2, No 1,1996.- pp.5-30.
6. Hartono N., Ismail A.H., Zeybek S., Caterino M., Jiang K., Sahin M., Natalia Ch.The 1-D Bin Packing Problem optimization using bees algorithm. Journal Industrial Servicess. 2022. Т.
7. № 2. С. 323. 7. Alem D., Morabito R. 2012. Risk-averse two-stage stochastic programs in furniture plants. OR Spectrum 35 (4). pp.773–806
8. Florent Teichteil-Koenigsbuch, Guillaume Infantes, and Ugur. RFF: A robust, FF-based MDP planning algorithm for generating policies with low probability of failure. In Sixth International Planning Competition at ICAPS’08, 2008. T.8.
9. Li Y., Chen M., Huo J. 2022. A hybrid adaptive large neighborhood search algorithm for the large-scale heterogeneous container loading problem. Expert Systems with Applications 189: 115909.
10. Valério de Carvalho J.M. 2002. LP models for bin packing and cutting stock problems. European Journal of Operational Research 141 (2). P. 253–273.
11. .Fredericson G.N. Probabilistic analysis for simple one- and two-dimensional bin packing algorithms. Information Processing Letters, Vol.11, No 4-5, 1980.-P.156-161.
12. Melega G.M., de Araujo S.A., Jans R. 2018. Classification and literature review of integrated lotsizing and cutting stock problems. European Journal of Operational Research 271 (1). . 1–19.
13. Ekici A. 2022. Variable-sized bin packing problem with conflicts and item fragmentation. Computers & Industrial Engineering 163: 107844.
14. Andrade P.R. de L., de Araujo S.A., Cherri A.C., Lemos F.K. 2021. The integrated lot sizing and cutting stock problem in an automotive spring factory. Applied Mathematical Modelling 91. P. 1023–1036. .
15. Li Y., Chen M., Huo J. 2022. A hybrid adaptive large neighborhood search algorithm for the large-scale heterogeneous container loading problem. Expert Systems with Applications 189: 115909.
16. Mahonina Yu..V., Neimark Yu.А. Reshenie zadachi raskroya-upakovki s pomoshchyu combinirovannogo evolucionno-geneticheskogo algoritma. Trudy NGTU im. R.E. Alekseeva. 2021. № 2 (133). С. 24-31.
17. Mayramty M.V. Issledovanie evristicheskih I metaevristicheskih algoritmov resheniya zadach raskroya-upakovki. Nauchnyi aspekt. 2023. Т. 16. № 6. С. 2009-2015.
18. Kovel I.V. Veroyatnostnyi sposob perebora razhirovannyh resheniy zadachi raskroya-upakovki. Modern information technologies. 2008. № 8. С. 170- 171.
19. Vasilyeva L.I., Dyaminova E.I., Mihailova A.N. Testirovanie stohasticheskih algoritmov zadach raskroya-upakovki i razmeshcheniya. Mavlutovskie cteniya. Materials of XIV All-Russian Youth scince conference. 2020. С. 3.
20. Meliani Y., Hani Ya., Lissane Elhaq S., El Mhamedi. A Tabu search based approach for the heterogeneous fleet vehicle routing problem with three-dimensional loading constraints. Applied Soft Computing. 2022. Т. 126. С. 109239.