A. Mingozzi et al., AN EXACT ALGORITHM FOR THE RESOURCE-CONSTRAINED PROJECT SCHEDULING PROBLEM-BASED ON A NEW MATHEMATICAL FORMULATION, Management science, 44(5), 1998, pp. 714-729
Citations number
31
Categorie Soggetti
Management,"Operatione Research & Management Science","Operatione Research & Management Science
In this paper we consider the Project Scheduling Problem with resource
constraints, where the objective is to minimize the project makespan.
We present a new 0-1 linear programming formulation of the problem th
at requires an exponential number of variables, corresponding to all f
easible subsets of activities that can be simultaneously executed with
out violating resource or precedence constraints. Different relaxation
s of the above formulation are used to derive new lower bounds, which
dominate the value of the longest path on the precedence graph and are
tighter than the bound proposed by Stinson et al. (1978). A tree sear
ch algorithm, based on the above formulation, that uses new lower boun
ds and dominance criteria is also presented. Computational results ind
icate that the exact algorithm can solve hard instances that cannot be
solved by the best algorithms reported in the literature.