Operations Research

Prof. Dr. Peter Brucker, Silvia Heitmann , Dr. Sigrid Knust

This directory contains the following files with results of algorithms for resource-constrained project scheduling problems (RCPSP, RCPSP/max, MRCPSP/max):

The used data sets are the PROGEN data sets available at PSPLIB Kiel


Lower bound LB2 for RCPSP based on LP of Mingozzi et al. [1998] and immediate selection (Brucker, Knust, Schoo, Thiele [1998]),
calculated with column generation by Baar, Brucker, Knust [1998]:

  • lp.60: Lower bounds for the PROGEN data set with n=60
  • lp.90: Lower bounds for the PROGEN data set with n=90

    Lower bound LB for RCPSP based on constraint propagation (immediate selection) and linear programming published in Brucker, Knust [2000]:

  • lpcp.60: Lower bounds for the PROGEN data set with n=60
  • lpcp.90: Lower bounds for the PROGEN data set with n=90
  • lpcp.120: Lower bounds for the PROGEN data set with n=120


    Lower bound for MRCPSP/max based on constraint propagation and linear programming (Brucker, Knust [2000A]):

  • mrcpspmax.30: Lower bounds for the PROGEN/max data set with n=30
  • mrcpspmax.50: Lower bounds for the PROGEN/max data set with n=50
  • rcpspmax.c: Lower bounds for the PROGEN/max data set C with n=100
  • rcpspmax.d: Lower bounds for the PROGEN/max data set D with n=100


    Tabu-search algorithm based on critical arcs, published in Baar, Brucker, Knust [1998]:

  • tslist.30: Results for the PROGEN data set with n=30
  • tslist.60: Results for the PROGEN data set with n=60
  • tslist.90: Results for the PROGEN data set with n=90


    Tabu-search algorithm based on parallelity, published in Baar, Brucker, Knust [1998]:

  • tspara.30: Results for the PROGEN data set with n=30
  • tspara.60: Results for the PROGEN data set with n=60
  • tspara.90: Results for the PROGEN data set with n=90
    Baar, Brucker, Knust [1998]:
    Tabu-search algorithms and lower bounds for the resource-constrained project scheduling problem,
    in: S.Voss, S.Martello, I.Osman, C.Roucairol (eds.): Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer, 1-18.

    Brucker, Knust, Schoo, Thiele [1998]:
    A Branch-and-bound algorithm for the resource-constrained project scheduling problem,
    European Journal of Operational Research 107, 272-288.

    Brucker, Knust [2000]:
    A linear programming and constraint propagation-based lower bound for the RCPSP,
    European Journal of Operational Research 127, 355-362.

    Brucker, Knust [2000A]:
    Lower Bounds for the MRCPSP/max, MRCPSP and RCPSP/max,
    OSM.

    Mingozzi, Maniezzo, Ricciardelli, Bianco [1998]:
    An exact algorithm for project scheduling with resource constraints based on a new mathematical formulation,
    Management Science 44, 714-729.