Разработки СО РАН - каталоги программ и БД

Поиск по каталогам:

2019-03-29

Назначение - распределение объёмов бункерных накопителей в производственной линии.
Область применения - проектирование производственных систем.
Используемый алгоритм - гибрид алгоритма ветвей и границ и генетического алгоритма, особенность которого - использование приближенного решения в качестве начального рекорда на входе алгоритма ветвей и границ. Приближенное решение построено однократным запуском генетического алгоритма.

Результаты алгоритма опубликованы в статье:

Dolgui A., Eremeev A.V., Sigaev V.S. HBBA: hybrid algorithm for buffer allocation in tandem production lines // Journal of Intelligent Manufacturing.–– 2007. –– Vol. 18, no. 3. –– P. 411––420.

Функциональные возможности - распределение объёмов бункерных накопителей между единицами оборудования в производственной линии  для максимизации дохода от использования линии за амортизационный период с учётом её средней производительности, капитальных затрат на установку бункерных устройств и стоимости хранения деталей.

Входные данные - файл с описанием линии

Выходные данные - файл с параметрами найденного решения.

Инструментальные средства создания - Lasarus

2019-03-18

Аннотация: Программа позволяет выполнить нагрузочное тестирование и анализ эффективности системы управления ресурсами (СУР) распределенных вычислительных систем.

Назначение: Программа состоит из двух модулей. Первый используется для создания потока загрузки на функционирующую СУР и запускается для каждого набора политик и алгоритмов планирования PBS Torque. Второй модуль анализирует системные лог файлы и для каждого набора задач рассчитывает показатели, характеризующие эффективность планирования.

Область применения: Высокопроизводительные распределенные вычислительные системы.

Используемые алгоритмы:

На входе программа использует наборы масштабируемых задач, параметры которых соответствуют моделям загрузки промышленных вычислительных систем (Parallel Workload Archive). Набор задач задаётся в XML формате и архивируется с целью экономии места. Файлы с исходными наборами задач могут быть созданы с помощью пакета программ MOJOS. Формат XML:

<JOBSET GUID="1024_bit" CREATIONDATE="date" COUNDJOBS="XXX">

<JOB GUID="1024_bit" ARRIVALTIME="start_time" COUNTREQUESTS="XX">

<REQUEST NODES="XX" TIME="solution_time1" PRIORITY="XX"/>

<REQUEST NODES="YY" TIME="solution_time2" PRIORITY="XX"/>

...

</JOB>

...

</JOBSET>

Показатели эффективности, такие как время решения всех задач набора, среднее время ожидания задач в очереди СУР и % загрузки ресурсов, для всех вариантов настройки СУР и для всех наборов задач на выходе программы сохраняются в таблицу в формате CSV с заголовком:

NODES_COUNT;JOBS_COUNT;RIGID_JOBS_PART;SCHEDULER;POLICY;ALGORITHM;WINDOW;QUEUE_RUN_TIME;AVERAGE_WAIT_TIME;WORKLOAD.

Программа разработана в рамках ГЗ 0306-2016-0018

2018-12-27

Назначение - структурная оптимизация сетей различного назначения с целью повышения надёжности.

Область применения - моделирование и проектирование сетей различного назначения.

Программа позволяет для заданного числа узлов и каналов связи сети находить структуру сети, оптимальную или близкую к оптимальной по критерию надёжности. В качестве показателей надёжности рассматриваются вероятность связности сети и вероятность связности выделенных узлов в сети с ограничением на диаметр. Узлы сети предполагаются абсолютно надёжными, т.е. надёжность узлов предполагается на порядки выше надёжности каналов связи. Для каждого канала связи задаются значения надёжности и стоимости прокладки. Поиск ведётся в условиях наперёд заданных ограничений на общую стоимость прокладки каналов связи и диаметр сети. Подход с использованием кумулятивных оценок позволяет быстрее принимать решение о пригодности (непригодности) получаемых в процессе работы алгоритма вариантов топологии сети.

В отличие от Версии № 1 программы, в данной версии появилась возможность проводить оптимизации сети по критерию другого показателя надёжности - вероятности связности выделенных узлов в сети с ограничением на диаметр.

Используемый алгоритм - генетический алгоритм с использованием кумулятивных оценок верхней и нижней границ надёжности с модификацией операторов ГА (ускоренный отсев непригодных решений за счёт того, что учитывается, является ли решение достаточно надёжным по отношению к заданному порогу надежности). 

Алгоритм основан на результатах, опубликованных в следующих работах:

[1] Denis A. Migov, Kseniya A. Nechunaeva, Sergei N. Nesterov, Alexey S. Rodionov Cumulative Updating of Network Reliability with Diameter Constraint and Network Topology Optimization, COMPUTATIONAL SCIENCE AND ITS APPLICATIONS - ICCSA 2016, PT I. Серия книг: Lecture Notes in Computer Science, Том: 9786,  Стр.: 141-152

[2] Д. А. Мигов, К. А. Нечунаева, А. С. Родионов, Генетический алгоритм структурной оптимизации сетей с применением подхода кумулятивного уточнения границ надёжности. Вестник СибГУТИ, №4, 2015, с. 55-61.

Входные данные программы: количество узлов и каналов связи сети, значения надёжности для всех каналов связи (числа от 0 до 1), значения стоимости прокладки для всех каналов связи, параметры генетического алгоритма (размер популяции, кол-во поколений, размер турнира, вероятность мутации), ограничения на общую стоимость прокладки каналов связи, максимальное значение диаметра графа.

Функциональные возможности - структурная оптимизация сетей с количеством  каналов до 100.

Инструментальные средства создания - Delphi.

Алгоритм разработан в рамках гранта РФФИ № 18-07-00460.

2018-12-27

Система имитационного моделирования ИМОДО, разработанная для решения задач, связанных с транспортной сетью, зарегистрирована в ФАП СО РАН, № PR18002.

В этой программе представлена вторая версия системы ИМОДО, расширенная.

Рассматривалась задача расстановки стационарных устройств мониторинга для оповещения всех участников движения о чрезвычайных ситуациях с учетом дополнительных характеристик.

Учитывается разделение множества узлов на кластеры и другие характеристики.

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

Используемый алгоритм

Поиск оптимальной расстановки стационарных устройств оповещения осуществляется с помощью генетического алгоритма с учетом основных характеристик модели:

– радиус действия каждого устройства оповещения;

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

– скорость движения транспорта, фиксированное значение для проводимого эксперимента;

– узлы, в которых размещены устройства оповещения;

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

В качестве модели транспортной сети рассматривается граф с взвешенными ребрами.

Редактирование графа можно производить непосредственно в системе.

Подложкой является карта, взятая из открытых источников. Алгоритм описан в [1].

[1] TKACHEV K.V., VOLZHANKINA K.A., SOKOLOVA O.D. On a problem of the monitoring device placement on transport networks, Novosibirsk. https://cloud.mail.ru/public/4Tsd/NymmFx5wP

В прилагаемом архиве находится проект для запуска на Visual Studio.

2018-12-26

Назначение - оптимизация сетей различного назначения с целью повышения надёжности.

Область применения - проектирование сетей различного назначения.

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

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

Входные данные программы: структура сети в виде графа, значения надёжности для всех узлов связи (числа от 0 до 1), значения стоимости размещения стока для всех узлов связи, параметры генетического алгоритма (размер популяции, кол-во поколений, размер турнира, вероятность мутации), ограничения на общую стоимость установки, Т - доля узлов сети, которые должны быть связны с каким-либо из стоков.

Инструментальные средства создания - Delphi.

Алгоритм разработан в рамках гранта РФФИ № 18-07-00460.