6283

Автор(ы): 

Автор(ов): 

2

Параметры публикации

Тип публикации: 

Доклад

Название: 

Lower Bounds and Flat Graphs of Precedence Relations for the Resource-Constrained Project Scheduling Problem

Наименование конференции: 

  • IFAC Symposium on Information Control Problems in Manufacturing

Город: 

  • Moscow

Издательство: 

  • -

Год издания: 

2009

Страницы: 

1512-1515
Аннотация
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.

Библиографическая ссылка: 

Лазарев А.А., Гафаров Е.Р. Lower Bounds and Flat Graphs of Precedence Relations for the Resource-Constrained Project Scheduling Problem / . Moscow: -, 2009. С. 1512-1515.