10-08

On Lower and Upper Bounds for the Resource-Constrained Project Scheduling Problem

by E.R. Gafarov, A.A. Lazarev, F. Werner

 

Preprint series: 10-08, Preprints

MSC:
90B35 Scheduling theory, See also {68M20}

 

Abstract; In this paper, we consider the well-known resource-constrained project scheduling problem. We propose some arguments that already a special case of this problem with a single type of resources is not in APX. We prove that there exist instances for which the optimal makespan values for the non-preemptive and the preemptive problems have a ratio $O(log n)$. This means that there exist instances for which the lower bound of Mingozzi 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(\sqrt{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 problem $1|p-batch, b=\infty|C_{max}$.

Keywords: Project scheduling; Makespan; Lower bounds; Upper bounds


The author(s) agree, that this abstract may be stored as full text and distributed as such by abstracting services.

Letzte Änderung: 01.03.2018 - Ansprechpartner: Webmaster