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

В статье рассматривается один алгоритм оптимального распределения объектов произвольной природы по хранилищам, сущность которых определяется предметной областью. Рассматриваются некоторые предметные области, для которых актуальна проблема оптимального распределения. Ускорение операции Join для больших данных за счет параллельной реализации операции Join необходимо равномерное распределение данных между процессорами кластера. В этом случае параллельная реализация операции Join будет эффективной только тогда, когда вычислительные сложности ее выполнения во всех фрагментах базы данных будут минимально отличаться друг от друга. Критерий оптимальности должен обеспечить равномерность распределения данных. В складской логистике рассматривается не стандартная задача, состоящая в минимизации количества хранилищ или максимизации веса (числа, массы, площади или объема) загруженных объектов (товаров, материалов). Решаемая задача состоит в размещении объектов по хранилищам таким образом, чтобы сумма свободных мест в хранилищах была минимальной. Задача образовательной логистики заключается в справедливом распределении бюджетных мест с учетом направления подготовки, требований регионов и возможностей университетов. Она характеризуется большим набором ограничений, которые определяют минимальное и максимальное количество требуемых бюджетных мест для каждого региона и университета. Приведено подробное описание эвристического алгоритма оптимального распределения. Предложены целевые функции для рассматриваемых задач. Приведено описание экспериментов, которые позволили дать оценку качества эвристического жадного алгоритма оптимального распределения. В результате этих экспериментов были выявлены зависимости времени выполнения алгоритма от количества распределяемых объектов и качества распределения (разности между максимумом и минимумом заполнения хранилищ) от количества хранилищ и интервала значений весов объектов. Показано, что алгоритм достаточно прост и может быть легко реализован в любом языке программирования. Время работы алгоритма даже для big data мало, что позволяет эффективно использовать его при подготовке данных для параллельного решения задач с высокой вычислительной сложностью. алгоритм показывает хорошие результаты при распределении объектов по хранилищам. Наибольшее заполнение хранилищ отличается от наименьшего на незначительную величину.
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.
№3 (2020)