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

Автор: Ченцов Александр Георгиевич, Григорьев Алексей Михайлович, Ченцов Алексей Александрович

Журнал: Вестник Южно-Уральского государственного университета. Серия: Математическое моделирование и программирование @vestnik-susu-mmp

Рубрика: Математическое моделирование

Статья в выпуске: 1 т.11, 2018 года.

Бесплатный доступ

Статья посвящена вопросам построения и реализации параллельных алгоритмов для решения прикладных задач. Рассматривается задача маршрутизации перемещений с ограничениями и усложненными функциями стоимости. Предполагается, что объекты посещения - суть мегаполисы (непустые конечные множества), при посещении которых должны выполнятся некоторые работы, именуемые далее внутренними. По постановке задачи имеются ограничения в виде условий предшествования. Стоимости перемещений зависят от списка заданий, которые не выполнены на момент перемещения. Ситуация такого рода возникает, в частности, при аварийных ситуациях, связанных с работой АЭС и подобных происходящим в Чернобыле и Фукусиме. Речь идет об утилизации источников радиоактивного излучения, осуществляемой последовательно во времени; в этом случае исполнитель находится под воздействием источников, которые не были демонтированы на момент соответствующего перемещения. За счет этого в функциях стоимости, оценивающих воздействие радиации на исполнителя, возникает зависимость от списка невыполненных заданий. Последние состоят в том или ином варианте выключения соответствующего источника. В настоящем исследовании излагается подход к решению данной задачи параллельным алгоритмом, реализуемым на суперкомпьютере УРАН. Приведены результаты вычислительного эксперимента.

Еще

Динамическое программирование, маршрут, условия предшествования, параллельный алгоритм

Короткий адрес: https://sciup.org/147159473

IDR: 147159473   |   DOI: 10.14529/mmp180106

Статья научная