Мовчан О.В., Маслова Н.А. - Разработка и анализ метода размещения на облаке программного обеспечения для решения динамических задач распределения ресурсов.

Аннотация

О.В. Мовчан, Н.А. Маслова Разработка и анализ метода размещения на облаке программного обеспечения для решения динамических задач распределения ресурсов. Выполнен анализ и подбор методов решения задач распределения ресурсов. Рассмотрены достоинства использования «облачных» технологий. Разработана архитектура приложения.

Постановка проблемы

Задачи распределения ресурсов – один из важнейших классов задач прикладного направления кибернетики, используемого для решения множества практических задач. Это задачи о распределении денежных средств; материальных запасов; водных потоков; сетевых ресурсов; времени; оперативной или виртуальной памяти.

Распределительные задачи возникают в случае, когда имеющихся в наличии ресурсов не достаточно для эффективного выполнения работ и необходимо наилучшим образом распределить их по узлам, объектам или работам в соответствии с выбранным критерием оптимальности.

Анализ литературных источников

Основы методов решения задач распределения ресурсов заложены как в работах отечественных ученых (Михалевича B.C., Шкурбы В.В., Танаева B.C., Гордона B.C., Шора Н.З., Куксы А.И., Батищева Д.И. и ряда других), так и зарубежных (Р.Конвей, Б.Джонсон, У.Максвелл, Б.Гиффлер, Ж.Томпсон).

Оптимальное распределение ресурсов – такое распределение ограниченных ресурсов, которое обеспечивает их наилучшее использование с точки зрения заданного критерия оптимальности.

Если задача распределения ресурсов требует оперативного решения, то используют методы комбинаторной оптимизации, а также экстремальные задачи на графах. Так, например, в [1] предлагается использовать метод проекции градиента, источник [2] рекомендует метод ветвей и границ, в работе [3] предлагается решать систему линейных неравенств методом исключения неизвестных, а в [4] предложен алгоритм решения задач распределения ресурсов, сочетающий элементы трех вышеперечисленных методов.

Значительный класс задач распределения ресурсов решается с использованием методов динамического программирования – математического аппарата, позволяющего осуществлять оптимальное планирование управляемых процессов и процессов, зависящих от времени путем разбиения процесса принятия решений на ряд однотипных, но взаимосвязанных этапов (шагов).

Ключевая идея динамического программирования достаточно проста [5]. Для решения основной задачи, необходимо решить отдельные подзадачи, а затем объединить решения подзадач в одно общее решение.

Класс задач распределения ресурсов, решаемых методами динамического программирования, весьма обширен. Классифицируют их по применяемым вычислительным методам, по содержанию, по характеру моделей.

Цель статьи

Цель статьи – подбор методов, которые могут быть применены в процессе online-решения задач распределения ресурсов с учетом требования размещения инструментария для решения задачи на «облачном» сервисе; разработка архитектуры приложения.

Постановка задачи исследования

. Современные научные исследования связаны с проведением сложных расчетов и использованием вычислительных технологий, а эффективность исследований напрямую зависит от вычислительных приложений для решения той или иной задачи. В настоящее время накоплено значительное количество подобных приложений. Отмечены попытки разработки специальных пакетов, ориентированных на решение различных типов задач, в том числе источник [6] представляет пакет для решения некоторых видов задач распределения ресурсов. Однако эти пакеты разрабатывались с конкретной целью, не совпадающей с задачами авторов, а, кроме того, использование существующих программных продуктов имеет ряд недостатков:

затраты пользователем времени на поиск необходимого программного продукта и материальных средств на его приобретение;
пользователю необходимо самостоятельно производить установку и настройку программного пакета и повторять эти действия в случае выхода новой версии.

Поэтому решено разработать программный продукт для решения задач распределения ресурсов в online-режиме с учетом требования размещением инструментария для решения задачи на «облачном» сервисе, который позволит пользователю, минуя поиск необходимого программного обеспечения и процесс инсталляции, получить решение необходимой задачи с описанием этого решения.

При подборе методов, которые следует включить в пакет, следует выполнить постановку задачи исследования. Из-за многообразия задач распределения ресурсов, множества областей их применения, разрабатываемый программный продукт будет иметь сложную структуру и, по мнению авторов, должен содержать:

раздел для решения классических задач распределения ресурсов (задачи распределения ресурсов между предприятиями и задачи управления запасами);
раздел для решения сетевых задач распределения ресурсов (задачи о кратчайшем пути и о максимальном потоке);
контрольный раздел, содержащий методы и алгоритмы (метод условной оптимизации, метод ветвей и границ, алгоритмы прямой и обратной прогонки, алгоритмы Качмажа и Балаша).

В пакет предполагается включить дополнительный режим «интеллектуальный агент», основной задачей которого является оказание помощи пользователю в подборе наиболее эффективного по времени выполнения алгоритма.

Рассмотрим типичную задачу распределения ресурсов, в общем виде предложенную в [7].

Имеется начальное количество средств ζ₀, которое необходимо распределить в течение n лет между s предприятиями. Средства u_ki(k=1, ..., n; i=1, ..., s) выделенные в k-м году i-му предприятию, приносят доход в размере f_ki(u_ki) и к концу года возвращаются в количестве φ_ki(u_ki). В последующем распределении доход может либо участвовать (частично или полностью), либо не участвовать.

Требуется найти способ распределения ресурсов (количество средств, выделяемых каждому предприятию в каждом плановом году), чтобы суммарный доход от s предприятий за n лет был максимальным.

В качестве показателя эффективности процесса распределения ресурсов за n лет принимается суммарный доход, полученный от s предприятий:

Количество ресурсов в начале k-го года характеризует величина ζ_k-1. Управление на k-м шаге состоит в выборе переменных u_k1,u_k2, ..., u_kn, обозначающих ресурсы, выделяемые в k-м году i-му предприятию.

Если предположить, что доход в дальнейшем распределении не участвует, то уравнение состояния процесса имеет вид:

В качестве общей постановки сетевой задачи распределения ресурсов используем постановку, которая с учетом требований оптимальности сформулирована в [8] следующим образом:

где J – критерий качества оптимизационной задачи, l_ij(t), u_ij(t),g_i(t)) – ограничения, y_i⁰ – начальные условия, Т – общее время, необходимое для распределения ресурса, n – число временных интервалов измерений, количество переменных; m – число дуг графа, n – количество его вершин.

Один из способов решения проблемы – применение высокоуровневых сред путем удаленного доступа к вычислительным ресурсам. В последние несколько лет это реализовывается путем переноса приложения в облако.

Облачные технологии – это модель обеспечения удобного сетевого доступа к вычислительным ресурсным пулам, которые могут быть быстро предоставлены или выпущены с минимальными усилиями по управлению и взаимодействию с поставщиком услуг.

Есть множество самых разных облачных сервисов, многие из них существуют и успешно развиваются уже по несколько лет. Это сервисы для хранения файлов, для проигрывания аудио и видео, для редактирования документов, для решения разнообразных задач, например, существует возможность работать с 1С через браузер (модель SaaS). Однако возможность предоставления пользователю услуги по размещению на облаке исполняемого модуля собственной разработки является достаточно новой. Первыми об использовании облачных технологий для улучшения своих продуктов заявили антивирусные компании (Kaspersky Internet Security, Panda Cloud Antivirus), Другим примером использования облаков в программном обеспечении является почтовый шлюз GateWall Antispam. На «облаке» размещен исполняемый модуль программы KinderGate (Родительский контроль). А среди программных калькуляторов, позволяющих выполнять вычисления и проводить научные исследования в on-line режиме с использованием облака, известен Neos solvers – облачный ресурс для решения линейных задач программирования.

Решение задачи и результаты исследований

В результате проведенного исследования для размещения разрабатываемого приложения выбрана облачная платформа Windows Azure – одна из немногих «облачных» платформ, предоставляющую услугу размещения исполняемого пользовательского приложения.

Платформа Windows Azure — это масштабируемая интернет-платформа служб облачных вычислений с широким выбором функций для создания приложений на всех уровнях (от веб-приложений для пользователей до сложных корпоративных систем), размещаемая в центрах обработки данных Microsoft. Инструментарий разработчика позволяет избежать высоких начальных расходов на приобретение средств разработки и помогает решать задачи обработки любого объема документов без увеличения расходов на собственную IT-инфраструктуру.

Актуальная версия Windows Azure поддерживает ряд вычислительных служб, а именно: виртуальные машины, веб-сайты, облачные службы и мобильные службы.

Создание облачного приложения подразумевает работу с облачной службой, которая позволяет создавать и развертывать почти неограниченно масштабируемые приложения практически на любом языке программирования.

Согласно отчету аналитической компании Nasuni, платформа Windows Azure является лидером в тестах производительности при записи и чтении данных из облака, доступности данных и минимальному числу ошибок (0 %).

Примерами уже существующих разработок на базе Windows Azure являются сервис ABBYY Cloud OCR SDK, Quest OnDemand, разработки компании Softline.

На рисунке 1 представлен прототип архитектуры разрабатываемого приложения.

Рисунок 1 – Прототип архитектуры приложения

Приложение имеет трехфреймовую структуру.

Левый фрейм содержит навигационную панель приложения, представленную в виде дерева тем. Выбор соответствующей темы пользователем влияет на содержание двух правых фреймов.

Правый верхний фрейм отражает базовую постановку задачи, что позволяет пользователю быстро сориентироваться во входных данных задачи.

Правый нижний фрейм состоит из трех вкладок. Первая вкладка «Пример решения» позволяет пользователю ввести входные данные, описанные в базовой постановке задачи. Вкладка «Программный код» содержит листинг алгоритма, реализующего решение поставленную задачу. Вкладка «Описание решения» содержит развернутое описание решения задачи с входными данными пользователя.

Приложения облачных служб можно создавать практически на любой популярной платформе разработки, включая .NET, Node.js, PHP, Java, Python и Ruby, что и будет сделано в дальнейшем.

Выводы

Проанализированы методы решения задач распределения ресурсов. Осуществлен выбор методов и алгоритмов для разрабатываемого программного обеспечения. Рассмотрены преимущества «облачных» приложений по сравнению с использованием уже готового программного обеспечения. Разработана архитектура программного обеспечения с учетом особенностей работы с «облачными» технологиями.

Список литературы

1. Пособие по проектированию автоматизации и диспетчеризации систем водоснабжения (к СНиП 2.04.02-84), Надра, 1985.
2. Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации. – К.: Наукова думка, 2003. - 301 с.
3. Остапенко В.В., Финин Г.С. Метод исключения неизвестных для систем линейных неравенств со структурой графа «Кибернетика и системный анализ», № 5, 1999, С. 66-75.
4. Маслова Н.А. Методы теории вычислений в решении задач управления технологическими процессами / Н.А. Маслова // Штучний інтелект. – 2009. – № 3. – С. 165–171.
5. Михалевич В.С., Кукса А.И. Методы последовательной оптимизации в дискретных сетевых задач оптимального распределения ресурсов. - М.: Наука, 1983. – 208 с.
6. Решение задач on-line / Интернет-ресурс. - Режим доступа: www/ URL: http://math.semestr.ru/example.html - Загл. с экрана.
7. Каллихман И.Л., Войтенко М.А. Динамическое программирование в примерах и задачах. М.: Высшая школа, 1979. 124 с.
8. Остапенко В.В., Скопецький В.В, Фінін Г.С. Розподіл ресурсів у просторі та часі. К.: Наукова думка, 2003. - 322 с.