Анализ алгоритма оптимального распределения

Аннотация

В статье рассматривается один алгоритм оптимального распределения "объектов" произвольной природы по "хранилищам", сущность которых определяется предметной областью. Рассматриваются некоторые предметные области, для которых актуальна проблема оптимального распределения. Ускорение операции Join для больших данных за счет параллельной реализации операции Join необходимо равномерное распределение данных между процессорами кластера. В этом случае параллельная реализация операции Join будет эффективной только тогда, когда вычислительные сложности ее выполнения во всех фрагментах базы данных будут минимально отличаться друг от друга. Критерий оптимальности должен обеспечить равномерность распределения данных. В складской логистике рассматривается не стандартная задача, состоящая в минимизации количества хранилищ или максимизации "веса" (числа, массы, площади или объема) загруженных объектов (товаров, материалов). Решаемая задача состоит в размещении объектов по хранилищам таким образом, чтобы сумма "свободных мест" в хранилищах была минимальной. Задача образовательной логистики заключается в "справедливом" распределении бюджетных мест с учетом направления подготовки, требований регионов и возможностей университетов. Она характеризуется большим набором ограничений, которые определяют минимальное и максимальное количество требуемых бюджетных мест для каждого региона и университета. Приведено подробное описание эвристического алгоритма оптимального распределения. Предложены целевые функции для рассматриваемых задач. Приведено описание экспериментов, которые позволили дать оценку качества эвристического жадного алгоритма оптимального распределения. В результате этих экспериментов были выявлены зависимости времени выполнения алгоритма от количества распределяемых объектов и качества распределения (разности между максимумом и минимумом заполнения хранилищ) от количества хранилищ и интервала значений весов объектов. Показано, что алгоритм достаточно прост и может быть легко реализован в любом языке программирования. Время работы алгоритма даже для big data мало, что позволяет эффективно использовать его при подготовке данных для параллельного решения задач с высокой вычислительной сложностью. алгоритм показывает хорошие результаты при распределении объектов по хранилищам. Наибольшее заполнение хранилищ отличается от наименьшего на незначительную величину.

Сведения об авторах

Victor Iosifovich Munerman, Смоленский государственный университет

доцент кафедры информатики, кандидат технических наук

Daniel Victorovich Munerman, Смоленский государственный университет

лаборант-стажер кафедры информатики

Литература

[1] Munerman V., Munerman D. Realization of Distributed Data Processing on the Basis of Container Technology. In: 2019 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus), Saint Petersburg and Moscow, Russia, 2019, pp. 1740-1744. (In Eng.) DOI: 10.1109/EIConRus.2019.8656766
[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
Опубликована
2019-09-30
Как цитировать
MUNERMAN, Victor Iosifovich; MUNERMAN, Daniel Victorovich. Анализ алгоритма оптимального распределения. Международный научный журнал «Современные информационные технологии и ИТ-образование», [S.l.], v. 15, n. 3, p. 619-625, sep. 2019. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/619-625>. Дата доступа: 22 oct. 2021 doi: https://doi.org/10.25559/SITITO.15.201903.619-625.
Раздел
Параллельное и распределенное программирование, грид-технологии