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

Cite: Демаков А.В. , Кононов А.В.
Приближенный алгоритм распределения заданий по неоднородным процессорам с задержками при передаче данных
Дискретный анализ и исследование операций. 2025. Т.32. №4. С.118–137. DOI: 10.33048/daio.2025.32.816

Dates:

Submitted:	Oct 22, 2024
Accepted:	Sep 22, 2025
Published print:	Jun 4, 2026
Published online:	Jun 4, 2026

Identifiers: No identifiers

Altmetrics: