Analysis of an Optimal Distribution Algorithm
Abstract
The article considers one algorithm for the optimal distribution of "objects" of an arbitrary nature among "storages", the essence of which is determined by the subject area. Some subject areas for which the optimal distribution problem is relevant are considered. Accelerating the Join operation for big data due to the parallel implementation of the Join operation requires uniform distribution of data between the cluster processors. In this case, parallel implementation of the Join operation will be effective only when the computational complexity of its execution in all database fragments will be minimally different from each other. The optimality criterion should ensure uniform distribution of data. In warehouse logistics, a non-standard task is considered, consisting in minimizing the number of storages or maximizing the "weight" (number, mass, area or volume) of loaded objects (goods, materials). The task at hand is to place objects in storage in such a way that the amount of "free space" in the storage is minimal. The task of educational logistics is to "equitably" allocate budget places, taking into account the direction of training, the requirements of the regions and the capabilities of universities. It is characterized by a large set of restrictions that determine the minimum and maximum number of required budget places for each region and university. A detailed description of the heuristic optimal distribution algorithm is given. Objective functions for the problems under consideration are proposed. A description is given of the experiments that made it possible to assess the quality of the heuristic greedy optimal distribution algorithm. As a result of these experiments, the dependences of the execution time of the algorithm on the number of distributed objects and the quality of distribution (the difference between the maximum and minimum storage capacity) on the number of stores and the interval of the values of the object weights were revealed. It is shown that the algorithm is quite simple and can be easily implemented in any programming language. The running time of the algorithm, even for big data, is small, which allows it to be effectively used in the preparation of data for parallel solving problems with high computational complexity. The algorithm shows good results when distributing objects across repositories. The largest storage capacity differs from the smallest by a small amount.
References
[2] Zakharov V., Kirikova A., Munerman V., Samoilova T. Architecture of Software-Hardware Complex for Searching Images in Database. In: 2019 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus), Saint Petersburg and Moscow, Russia, 2019, pp. 1735-1739. (In Eng.) DOI: 10.1109/EIConRus.2019.8657241
[3] Mohiuddin I. et al. Secure distributed adaptive bin packing algorithm for cloud storage. Future Generation Computer Systems. 2019; 90:307-316. (In Eng.) DOI: 10.1016/j.future.2018.08.013
[4] Akbar M.M., Manning E.G., Shoja G.C., Khan S. Heuristic Solutions for the Multiple-Choice Multi-dimension Knapsack Problem. In: Alexandrov V.N., Dongarra J.J., Juliano B.A., Renner R.S., Tan C.J.K. (eds) Computational Science - ICCS 2001. ICCS 2001. Lecture Notes in Computer Science, vol. 2074. Springer, Berlin, Heidelberg, 2001, pp. 659-668. (In Eng.) DOI: 10.1007/3-540-45718-6_71
[5] Fréville A. The multidimensional 0–1 knapsack problem: An overview. European Journal of Operational Research. 2004; 155(1):1-21. (In Eng.) DOI: 10.1016/S0377-2217(03)00274-1
[6] Trivella A., Pisinger D. The load-balanced multi-dimensional bin-packing problem. Computers & Operations Research. 2016; 74:152-164. (In Eng.) DOI: 10.1016/j.cor.2016.04.020
[7] Delorme M., Iori M. Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems. INFORMS Journal on Computing. 2019. (In Eng.) DOI: 10.1287/ijoc.2018.0880
[8] Abdel-Basset M., Manogaran G., Abdel-Fatah L. et al. An improved nature inspired meta-heuristic algorithm for 1-D bin packing problems. Personal and Ubiquitous Computing. 2018; 22(5-6):1117-1132. (In Eng.) DOI: 10.1007/s00779-018-1132-7
[9] Li H., Zhu G., Cui C., Tang H., Dou Y., He C. Energy-efficient migration and consolidation algorithm of virtual machines in data centers for cloud computing. Computing. 2016; 98(3):303-317. (In Eng.) DOI: 10.1007/s00607-015-0467-4
[10] Usmani Z., Singh S. A Survey of Virtual Machine Placement Techniques in a Cloud Data Center. Procedia Computer Science. 2016; 78:491-498. (In Eng.) DOI: 10.1016/j.procs.2016.02.093
[11] Sridhar R., Chandrasekaran M., Page T. Optimization of heterogeneous Bin packing using adaptive genetic algorithm. IOP Conference Series: Materials Science and Engineering. 2017; 183(1):012026. (In Eng.) DOI: 10.1088/1757-899X/183/1/012026
[12] Quiroz-Castellanos M., Cruz-Reyes L., Torres-Jimenez J., Gómez C.S., Fraire Huacujaa H.J., Alvim A.C.F. A grouping genetic algorithm with controlled gene transmission for the bin packing problem. Computers & Operations Research. 2015; 55:52-64. (In Eng.) DOI: 10.1016/j.cor.2014.10.010
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
