Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://lib.mexmat.ru/books/48451
Дата изменения: Unknown
Дата индексирования: Sun Apr 10 21:34:17 2016
Кодировка: Windows-1251
Электронная библиотека Попечительского совета механико-математического факультета Московского государственного университета
Нашли опечатку? Выделите ее мышкой и нажмите Ctrl+Enter
Название: A branch-and-cut algorithm for scheduling of projects with variable-intensity activities
Автор: Tamas Kis
Аннотация:
In this paper we study a resource constrained project scheduling problem in which the resource usage of each activity may vary over time proportionally to its varying intensity. We formalize the problem by means of a mixed integer-linear program, prove that feasible solution existence is NP-complete in the strong sense and propose a branch-and-cut algorithm for finding optimal solutions. To this end, we provide a complete description of the polytope of feasible intensity assignments to two variable-intensity activities connected by a precedence constraint along with a fast separation algorithm. A computational evaluation confirms the effectiveness of our method on various benchmark instances.