ИСТИНА |
Войти в систему Регистрация |
|
ИСТИНА ПсковГУ |
||
Рассматривается одноприборная задача теории расписаний с разными продолжительностями обслуживания работ и ограничениями предшествования между работами. Некоторые работы проекта объединены в подпроекты. Стоимость подпроекта зависит от его длительности, т.е. от промежутка времени между началом выполнения первой работы подпроекта и окончанием выполнения последней работы подпроекта. Ставится задача минимизации суммарной стоимости выполнения подпроектов. Показано, что данная задача является NP-трудной. Предлагается метод решения, полиномиально зависящий от количества работ и экспоненциально от количества подпроектов