|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Алгоритм для задачи распределения работ, выполняемых в реальном времени при наличии дополнительной информации
Э. Гирлих, М. М. Ковалев, В. М. Котов
Аннотация:
Задача распределения работ в системе с $m$ идентичными параллельными процессорами, при котором минимизируется загруженность максимально загруженного процессора, является NP-трудной проблемой. Для этой задачи разработано много приближенных алгоритмов, но для версии этой задачи, в которой работы поступают и распределяются в реальном времени, нельзя разработать приближенный алгоритм, гарантированная оценка которого меньше $1+1/\sqrt2$ при $m\geq4$ и стремится к $1{,}837$ при $m\to\infty$. В статье исследуется версия задачи, в которой работы поступают одна за другой
и решение о их распределении принимается в реальном времени при дополнительном
условии, что суммарная длительность работ известна. Для такой версии задачи предлагается алгоритм с гарантированной оценкой, равной 5/3.
Статья поступила: 18.01.2001
Образец цитирования:
Э. Гирлих, М. М. Ковалев, В. М. Котов, “Алгоритм для задачи распределения работ, выполняемых в реальном времени при наличии дополнительной информации”, Дискрет. матем., 15:4 (2003), 133–140; Discrete Math. Appl., 13:6 (2003), 619–625
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm222https://doi.org/10.4213/dm222 https://www.mathnet.ru/rus/dm/v15/i4/p133
|
Статистика просмотров: |
Страница аннотации: | 932 | PDF полного текста: | 493 | Список литературы: | 67 | Первая страница: | 1 |
|