Автор(ы): Гафаров Е. Р. (ИПУ РАН, Лаборатория 68)Лазарев А. А. (ИПУ РАН, Лаборатория 68)Werner F. (?)Автор(ов): 3 Параметры публикацииТип публикации: Статья в журнале/сборникеНазвание: Approximability results for the resource-constrained project scheduling problem with a single type of resourcesНаименование источника: Annals of Operations ResearchОбозначение и номер тома: Vol. 213, Issue 1Город: Heidelberg, GermanyИздательство: SpringerГод издания: 2014Страницы: 115–130 Аннотация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. Библиографическая ссылка: Гафаров Е.Р., Лазарев А.А., Werner F. Approximability results for the resource-constrained project scheduling problem with a single type of resources // Annals of Operations Research. 2014. Vol. 213, Issue 1. С. 115–130.