|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Approximability results for the resource-constrained project scheduling problem with a single type of resourcesстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 2 мая 2014 г.
- Авторы: Gafarov E.R., Lazarev A.A., Werner F.
- Журнал: Annals of Operations Research
- Том: 213
- Номер: 1
- Год издания: 2014
- Издательство: Springer Nature
- Местоположение издательства: Switzerland
- Первая страница: 115
- Последняя страница: 130
- DOI: 10.1007/s10479-012-1106-5
- Аннотация: In this paper, we consider the well-known resource-constrained project scheduling problem. We give some arguments that already a special case of this problem with a single type of resources is not approximable in polynomial time with an approximation ratio bounded by a constant. We prove that there exist instances for which the optimal makespan values for the non-preemptive and the preemptive problems have a ratio of O(log n), where n is the number of jobs. This means that there exist instances for which the lower bound of Mingozzi et al. has a bad relative error of O(log n), and the calculation of this bound is an NP-hard problem. In addition, we give a proof that there exists a type of instances for which known approximation algorithms with polynomial time complexity have an approximation ratio of at least equal to O( √ n), and known lower bounds have a relative error of at least equal to O(log n). This type of instances corresponds to the single machine parallel-batch scheduling problem 1|p − batch, b=∞|Cmax.
- Добавил в систему: Лазарев Александр Алексеевич