|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Lower Bounds and Flat Graphs of Precedence Relations for the Resource-Constrained Project Scheduling Problemдоклад на конференции
- Авторы: Гафаров Е.Р., Лазарев А.А.
- Конференция (Симпозиум) : IFAC Symposium on Information Control Problems in Manufacturing
- Даты проведения конференции: 2009
- Тип доклада: не указан
- Докладчик: не указан
- Место проведения: Moscow, Россия
-
Аннотация доклада:
We consider some special cases of the NP-hard resource-constrained projectscheduling problem (RCPSP) to minimize the makespan. We show that a well-known lowerbounds for the problem may yield bad approximation ratios or its calculation is an NP-hardproblem too. We conjecture that the ratio of the optimal makespan of RCPSP to that of thepreemptive version of the problem is less than 2. We also provide some new estimates of theoptimal makespan of RCPSP.
- Добавил в систему: Лазарев Александр Алексеевич