Том 12, серия 1, номер 1, 2005 г., Стр. 71-100
УДК 519.854
Р. А. Корякин, С. В. Севастьянов
О стохастической задаче компактного суммирования векторов
Аннотация:
Рассматриваются многостадийные задачи теории расписаний в стохастической постановке, когда все длительности операций заданы в виде независимых одинаково распределeнных случайных величин с заданным распределением. Предлагается новый эффективный алгоритм, который решает такие задачи с существенно лучшими оценками, гарантированными «почти всегда» (т.e. для почти всех примеров при возрастающем числе работ) и для широкого класса распределений. Новый метод основан на приближeнном сведении рассматриваемых задач теории расписаний к задаче компактного суммирования векторов (КСВ), разработанном ранее одним из авторов, а также на новом эффективном алгоритме решения задачи КСВ.
Корякин Р. А. 1
Севастьянов С. В. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: seva@math.nsc.ru
Статья поступила 22 сентября 2004 г.
Исправленный вариант — 23 декабря 2004 г.
