Задача календарного планирования проектов с ограниченными ресурсами

Задачи календарного планирования проектов возникают в различных сферах деятельности, в том числе при проектировании новых изделий и запуске их в производство, планировании графиков выпуска и доставки продукции и т.д. Разнообразие приложений делает это направление весьма актуальным в области математических моделей и методов оптимизации. Под проектом будем понимать множество взаимосвязанных работ, выполнение которых направлено на достижение определенной цели. Взаимосвязь между работами задается технологией выполнения проекта. Каждая работа характеризуется длительностью и некоторыми ресурсными требованиями. Необходимо, с учетом ограничений на ресурсы, определить сроки выполнения работ проекта, при которых значение целевой функции оптимально. В данной работе исследована сложность задач со складируемыми ресурсами и критериями средневзвешенного времени завершения работ и чистой приведенной прибыли. Разработаны псевдополиномиальные алгоритмы решения рассматриваемых задач. Построены вполне полиномиальные аппроксимационные схемы для задач календарного планирования с возобновимыми ресурсами и критериями минимизации общего времени завершения всех работ и среднего времени завершения работ.