Анализ алгоритма оптимального распределения
Аннотация
В статье рассматривается один алгоритм оптимального распределения "объектов" произвольной природы по "хранилищам", сущность которых определяется предметной областью. Рассматриваются некоторые предметные области, для которых актуальна проблема оптимального распределения. Ускорение операции Join для больших данных за счет параллельной реализации операции Join необходимо равномерное распределение данных между процессорами кластера. В этом случае параллельная реализация операции Join будет эффективной только тогда, когда вычислительные сложности ее выполнения во всех фрагментах базы данных будут минимально отличаться друг от друга. Критерий оптимальности должен обеспечить равномерность распределения данных. В складской логистике рассматривается не стандартная задача, состоящая в минимизации количества хранилищ или максимизации "веса" (числа, массы, площади или объема) загруженных объектов (товаров, материалов). Решаемая задача состоит в размещении объектов по хранилищам таким образом, чтобы сумма "свободных мест" в хранилищах была минимальной. Задача образовательной логистики заключается в "справедливом" распределении бюджетных мест с учетом направления подготовки, требований регионов и возможностей университетов. Она характеризуется большим набором ограничений, которые определяют минимальное и максимальное количество требуемых бюджетных мест для каждого региона и университета. Приведено подробное описание эвристического алгоритма оптимального распределения. Предложены целевые функции для рассматриваемых задач. Приведено описание экспериментов, которые позволили дать оценку качества эвристического жадного алгоритма оптимального распределения. В результате этих экспериментов были выявлены зависимости времени выполнения алгоритма от количества распределяемых объектов и качества распределения (разности между максимумом и минимумом заполнения хранилищ) от количества хранилищ и интервала значений весов объектов. Показано, что алгоритм достаточно прост и может быть легко реализован в любом языке программирования. Время работы алгоритма даже для big data мало, что позволяет эффективно использовать его при подготовке данных для параллельного решения задач с высокой вычислительной сложностью. алгоритм показывает хорошие результаты при распределении объектов по хранилищам. Наибольшее заполнение хранилищ отличается от наименьшего на незначительную величину.
Литература
[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
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
