Новые жадные эвристики для задачи календарного планирования с ограниченными ресурсами

Для задачи календарного планирования с ограниченными ресурсами разработаны три вероятностных жадных алгоритма, в которых по-разному трактуется понятие “жадный”. Согласно первому алгоритму вычисляются временные задержки работ относительно наиболее поздних времен старта в задаче без ресурсных ограничений. Эти задержки используются для ранжирования работ и нахождения приближенного решения по схеме параллельного составления расписаний. Второй алгоритм использует оптимальное решение вспомогательной задачи на узкое место, в которой наряду с временными задержками явным образом учитываются ресурсные ограничения. Идея третьего алгоритма заключается в максимальном использовании выделяемых ресурсов. Для этих целей применяется вспомогательная задача о многомерном рюкзаке. Все алгоритмы являются рандомизированными и используют методы локальной перестройки полученных жадных решений. Приводятся результаты численных экспериментов и сравнение с ранее разработанными алгоритмами.