Том 12, серия 2, номер 1, 2005 г., Стр. 12-36
УДК 519.85
Ю. А. Кочетов, А. А. Столяр
Новые жадные эвристики для задачи календарного планирования с ограниченными ресурсами
Аннотация:
Для задачи календарного планирования с ограниченными ресурсами разработаны три вероятностных жадных алгоритма, в которых по-разному трактуется понятие «жадный». Согласно первому алгоритму вычисляются временные задержки работ относительно наиболее поздних времен старта в задаче без ресурсных ограничений. Эти задержки используются для ранжирования работ и нахождения приближенного решения по схеме параллельного составления расписаний. Второй алгоритм использует оптимальное решение вспомогательной задачи на узкое место, в которой наряду с временными задержками явным образом учитываются ресурсные ограничения. Идея третьего алгоритма заключается в максимальном использовании выделяемых ресурсов. Для этих целей применяется вспомогательная задача о многомерном рюкзаке. Все алгоритмы являются рандомизированными и используют методы локальной перестройки полученных жадных решений. Приводятся результаты численных экспериментов и сравнение с ранее разработанными алгоритмами.
Кочетов Ю. А. 1
Столяр А. А. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: jkochet@math.nsc.ru, asto@math.nsc.ru
Статья поступила 15 июня 2004 г.
Исправленный вариант — 25 апреля 2005 г.
