Test Instances: Appendix A

Appendix A
Test Instances
For testing the algorithms developed in this work, we have employed sev-
eral standard project instance sets which have been used in many studies
reported in the literature. Section A.l describes the classical Patterson set of
single-mode project instances. Subsequently, Section A.2 summarizes the so-
called ProGen instance sets, which contain both single-mode and multi-mode
instances.
A.I Patterson Instance Set

For a comparison of algorithms for the RCPSP in 1984, Patterson [162] col-
lected several project instances that had been used for testing procedures
before. This benchmark test set then became known as the Patterson in-
stance set. It contains 110 single-mode instances with up to 51 activities and
up to 3 resources. For all of these test problems, the optimal solutions are
known, see, e.g., Demeulemeester and Herroelen [48].
As it was subsequently used by many researchers in their studies, the Pat-
terson set became a standard for testing both heuristic and exact algorithms
for the RCPSP (cf., e.g., Bell and Han [15], Cho and Kim [30], Demeule-
meester and Herroelen [48, 51], Hartmann [92], Lee and Kim [133], Leon and
Ramamoorthy [134], Klein [115], Kolisch [120, 121], Mingozzi et al. [145],
Ozdamar and Ulusoy [156, 157], Sampson and Weiss [173], and Thomas and
Salhi [201]).
The Patterson instances are available from the internet based project
scheduling problem library PSPLIB at the University of Kiel (Germany).
For further information, we refer to Kolisch and Sprecher [129] and Kolisch
et al. [131].
182 APPENDIX A. TEST INSTANCES
A.2 Instance Sets Generated by ProGen

The Patterson instance set described in the previous section was among the
first of widely used standard test sets to evaluate exact and heuristic al-
gorithms for resource-constrained project scheduling. There were, however,
several points of attack: First, as a collection of instances, the Patterson set
was not systematically generated in terms of adjustable problem parameters.
Hence, it does not allow a detailed investigation of the impact of project
characteristics on the behavior of solution procedures. Second, with contin-
uous progress in project scheduling research as well as in the development of
faster computers, the Patterson instances became too easy to solve for mod-
ern algorithms in the early nineties. Therefore, appropriate computational
tests required more challenging problem instances. Third, the Patterson set
considers only the single-mode RCPSP but not any of its extensions.
To overcome some or all of these shortcomings, several researchers de-
veloped project instan<;e generators which allowed to generate instances on
the basis of controllable problem parameters (cf. Agrawal et al. [1], Demeule-
meester et al. [47], and Kolisch et al. [130)). In this work, we consider the
project instance generator ProGen introduced by Kolisch et al. [130]. We
have selected ProGen because it allows to generate both single- and multi-
mode instances on the basis of parameters which have been shown to have a
high impact on the behavior of solution procedures. Moreover, several sets
of instances have already been generated and used in many previous stud-
ies such that we were able to use existing standard instance sets instead of
generating new ones.
In order to allow a convenient access to ProGen and the standard ProGen
instance sets, the internet based project scheduling problem library PSPLIB
has been set up at the University of Kiel (Germany). For further information
on the instance sets and on recent developments of the project scheduling
problem library PSPLIB, the reader is referred to Kolisch and Sprecher [129]
and Kolisch et al. [131].
Motivated by the broad acceptance of ProGen and the related instance
sets in the project scheduling community, several researchers have extended
ProGen in order to cover further general project scheduling models. A
ProGen based generator for networks with minimal and maximal time-lags
(cf. Subsection 2.2.2) called ProGen/max has been developed by Schwindt
[180]. Drexl et al. [64] introduced ProGen/1Tx which extends ProGen by par-
tially renewable resources (cf. Subsection 2.2.3), the mode identity concept
(cf. Subsection 2.2.1), and some other new modeling features.
The remainder of this section summarizes the main characteristics of those
ProGen instance sets that have been used throughout this work. Subsection
A.2.1 describes the single-mode instances while Subsection A.2.2 reports on
the multi-mode instances.
A.2. INSTANCE SETS GENERATED BY PROGEN 183
A.2.1 Single-Mode Instance Sets

We use three standard ProGen instance sets which have been introduced
in Kolisch et al. [130], Kolisch and Sprecher [129], and Kolisch et al. [131]'
respectively. Each set is characterized by the number of activities within
a project. In the three sets, we have J = 30, J = 60, and J = 120 non-
dummy activities, respectively. As displayed in Table A.l, all instances were
generated with certain fixed parameter ranges, leading to activity durations
between one and ten periods and four renewable resources for each project.
Parameter min max

Pi 1 10
IKPI 4 4
Table A.l: ProGen single-mode instances: Fixed parameter levels
Kolisch et al. [130] identified three parameters which have a strong impact
on the performance of solution procedures, namely the network complexity,
the resource factor, and the resource strength. The network complexity NC
reflects the average number of immediate successors of an activity. The re-
newable resource factor RFP is a measure of the average number of resources
requested per job. The renewable resource strength RSP describes the scarce-
ness of the resource capacities. If the latter is high (Le., close to 1), the
availability is high, which leads to a smaller solution space and hence easier
problems. On the other hand, a low resource strength (Le., close to 0) implies
scarce resources and more difficult instances.
The instance sets with J = 30 and J = 60 were generated by a full facto-
rial design obtained from three network complexity levels, four resource factor
levels, and four resource strength levels. For each of the resulting 3·4·4 = 48
parameter combinations, 10 instance were randomly generated, leading to
480 instances in each of the two sets. The instance set with J = 120 was gen-
erated similarly, with the exception that five levels for the resource strength
were chosen. Again, 10 instances for each parameter combination were ran-
domly constructed, yielding 600 instances. An overview of the systematically
varied parameter settings within the three sets is given in Table A.2.
The set with 30 non-dummy activities currently is the hardest standard
set of RCPSP-instances for which all optimal objective function values are
known (cf. Demeulemeester and Herroelen [51]). For the other two sets,
lower bounds on the project's makespan can be easily derived using forward
recursion (cf. Subsection 2.1.2). Clearly, the earliest precedence feasible start
time ESJ+l of the dummy sink activity is a lower bound on the makespan, the
so-called critical path based lower bound (cf. also Stinson et al. [195]). Further
lower bounds have been developed by, e.g., Baar et al. [8], Brucker and Knust
184 APPENDIX A. TEST INSTANCES
J parameter levels
30 60 RFP 0.25 0.50 0.75 1.00
RSP 0.20 0.50 0.70 1.00
NC 1.50 1.80 2.10
120 RFP 0.25 0.50 0.75 1.00
RSP 0.10 0.20 0.30 0.40 0.50
NC 1.50 1.80 2.10
Table A.2: ProGen single-mode instances: Variable parameter levels
[27], Heilmann and Schwindt [99], Klein and Scholl [117], Mingozzi et al. [145],
and Stinson et al. [195]. The library PSPLIB which is frequently updated
contains the currently best lower and upper bounds for these instances.
Some or all of the three instance sets considered here have been widely
used by researchers, making them a standard for evaluating and comparing
solution algorithms. We refer to the studies of Baar et al. [8], Bouleimen
and Lecocq [25], Brucker et al. [29], Demeulemeester and Herroelen [51],
Hartmann [92], Hartmann and Kolisch [95], Klein [115], Klein and Scholl
[116], Kohlmorgen et al. [118], Kolisch [120, 121, 122], Kolisch and Hartmann
[126], Mingozzi et al. [145], Schirmer [174], Schirmer and Riesenberg [176,
177], and Sprecher [191].
A.2.2 Multi-Mode Instance Sets

We consider six standard ProGen instance sets for the MRCPSP. As for the
single-mode case, each set is characterized by the number of activities within
a project. We have J = 10, J = 12, J = 14, J = 16, J = 18, and J = 20.
Table A.3 shows the fixed parameter ranges which were used to generate all
of these multi-mode instances. We have three modes for each non-dummy
activity and two renewable as well as two nonrenewable resources. Observe
that, for the multi-mode case, the network complexity NC (cf. Subsection
A.2.1) has been fixed to 1.8 arcs per activity.
Parameter min max

Pj 1 10
Mj 3 3
NC 1.8 1.8
IKPI 2 2
IKvl 2 2
Table A.3: ProGen multi-mode instances: Fixed parameter levels

A.2. INSTANCE SETS GENERATED BY PROGEN 185
In order to obtain the multi-mode instance sets including nonrenewable

resources, the following four ProGen parameters were systematically varied:
The resource strengths for the renewable and nonrenewable resources, RSP
and RSI!, were treated separately, as well as the resource factors for the re-
newable and nonrenewable resources, RFP and RFI!. With the two resource
factor levels and the four resource strength levels listed in Table A.4, a full
factorial design with 10 instances for each parameter level resulted in 640
instance for each project size. 1 Those instances for which no feasible solution
exists due to nonrenewable resource restrictions were determined using the
branch-and-bound algorithm of Sprecher and Drexl [192] and removed from
the instance sets. Hence, we have 536 feasible instances with J = 10 activi-
ties, 547 feasible instances with J = 12 activities, 551 feasible instances with
J = 14 activities, 550 feasible instances with J = 16 activities, 552 feasible
instances with J = 18 activities, and 554 feasible instances with J = 20
activities in the library PSPLIB.
J parameter levels
10 RFP 0.50 1.00
RSP 0.20 0.50 0.70 1.00
RFI! 0.50 1.00
RSI! 0.20 0.50 0.70 1.00
12 14 16 18 20 RFP 0.50 1.00
RSP 0.25 0.50 0.75 1.00
RFI! 0.50 1.00
RSI! 0.25 0.50 0.75 1.00
Table A.4: ProGen multi-mode instances: Variable parameter levels
For all of the multi-mode ProGen instances described above, the optimal
objective function values are known (cf. Sprecher and Drexl [192]). These sets
(or at least some ofthem) have been used in several studies, cf. Hartmann [90],
Hartmann and Drexl [93], Kolisch [120], Kolisch and Drexl [125], Ozdamar
[154], Sprecher [190], Sprecher and Drexl [192]' and Sprecher et al. [193].
1 Due to the history of the project scheduling problem library, the resource strength
levels used to generate the instances with 10 non-dummy activities slightly differ from
those that have been used to generate the other problems.
Appendix B
Solving the MRCPSP using

AMPL
In what follows we show how the multi-mode resource-constrained project

scheduling problem (MRCPSP) can be solved using standard software. The
approach described here makes use of the modeling language AMPL (cf. Fou-
rer et al. [78]). The mathematical programming formulation of the MRCPSP
as given by (2.7)-(2.12) can be easily expressed in AMPL. Subsequently,
AMPL employs a mathematical problem solver such as CPLEX (cf. Bixby
and Boyd [18]) to solve a problem instance. The advantage of such an ap-
proach based on standard methods is that one only has to formulate the
problem at hand by means of AMPL but needs no knowledge about the so-
lution methodology. Recall, however, that we have mentioned in Chapter 3
that this mathematical programming approach is not capable of finding op-
timal solutions even for very small test problems in reasonable computation
times.
The AMPL model code for the MRCPSP is given in Section B.I. Section
B.2 then introduces the AMPL data format for an example instance of the
MRCPSP.
B.l AMPL-Formulation of the MRCPSP

This section provides a formulation of the MRCPSP in AMPL. The AMPL
code should be self-explanatory; for AMPL keywords we refer to Fourer
et al. [78]. The names of some of the parameters and variables had to be
adapted; an overview of the symbols is given in Table B.I.
The option at the beginning of the AMPL code selects CPLEX for solving
the problem. After the definition of the parameters, variables, objective
188 APPENDIX B. SOLVING THE MRCPSP USING AMPL
function, and constraints, a reference to the data file containing the project
instance is made. Then the problem is defined and solved. Finally, the
decision variables and the objective function value are displayed.
The makespan minimization objective is that of (2.7). The constraints
correspond to (2.8)-(2.11) while the variable declaration equals (2.12). Ob-
serve that we have used the time window based approach of (2.6) for the
renewable resource constraints in order to save variables and obtain the most
efficient formulation.
MRCPSP symbol symbol in AMPL

T T
J J
Mj M[j]
Pjm p[j ,m]
Pj P[j]
JeP' KR
Jev KN
rjmk r[j ,m,k]
R~ RR[k]
Rk RN[k]
EFj EF[j]
LFj LF[j]
Xjmt x[j,m,t]
Table B.1: MRCPSP symbols in AMPL formulation
# OPTIONS
option solver cplex;
# PARAMETERS
param T integer;
param J integer;
param M {0 .. J+1} integer;
param p {j in 0 .. J+1, 1 .. M[j]} integer;
set P {0 .. J+1} within {O .. J};
set KR;
set KN;
param r {j in 0 .. J+1, 1 .. M[j], KR union KN} integer;
B.i. AMPL-FORMULATION OF THE MRCPSP 189
param RR {KR} integer;

param RN {KN} integer;
param EF {O .. J+l} integer;

param LF {O .. J+l} integer;
# VARIABLES
var x {j in O.. J+l, 1 .. M[j], EF[j] .. LF[j]} binary;
# MODEL
minimize Makespan:
sum {t in EF[J+l] .. LF[J+l]} t * x[J+l,l,t];
subject to JobModeCompletion {j in O.. J+l}:

sum {m in 1 .. M[j]} sum {t in EF[j] .. LF[j]} x[j,m,t] = 1;
subject to PrecedenceRelations {j in 1 .. J+l, h in prj]}:
sum {m in 1 .. M[h]} sum {t in EF[h] .. LF[h]} t * x[h,m,t] <=
sum {m in 1. .M[j]} sum {t in EF[j] .. LF[j]} (t-p[j,mJ) * x[j,m,t];
subject to RenewableResources {k in KR, t in 1 .. T}:

sum {j in 1 .. J} sum {m in 1 .. M[j]} r[j,m,k] *
sum {q in max(t,EF[j]) .. min(t+p[j,m]-l, LF[j]) } x[j,m,q]
<= RR[k];
subject to NonrenewableResources {k in KN}:

sum {j in 1 .. J} sum {m in 1 .. M[j]} r[j,m,k] *
sum {t in EF[j] .. LF[j]} x[j ,m,t] <= RN[k];
# READ DATA FROM FILE
data instance.dat;
# SOLVE PROBLEM
problem MRCPSP:
x,
190 APPENDIX B. SOLVING THE MRCPSP USING AMPL
Makespan,
JobModeCompletion,
PrecedenceRelations,
ReneyableResources,
NonreneyableResources;
solve MRCPSP;
display x;
display Makespan;
B.2 AMPL-Data File for the MRCPSP

This section describes the data file that is read by the AMPL-file of the
previous section. As example, we have used the project instance of Figure 7.1.
Note that Bounding RUle 3.3 has been executed before setting up the data
file. Clearly, the preprocessing steps may reduce the number of constraints
and variables. In our case, the second mode of activity 5 could be deleted
because it is non-executable with respect to the nonrenewable resource.
param T := 22;
param J := 6;
param M :=
[0] 1
[1] 2
[2] 2
[3] 2
[4] 2
[5] 1
[6] 2
[7] 1;
param p :=
[0,1] 0
[1,1] 3 [1,2] 4
[2,1] 2 [2,2] 4
[3,1] 2 [3,2] 3
[4,1] 2 [4,2] 2
[5,1] 3
[6,1] 4 [6,2] 6
[7,1] 0
set P [0] :=
set P [1] .= 0;
B.2. AMPL-DATA FILE FOR THE MRCPSP 191
set P [2] := 0;
set P [3] := 1;
set P [4] := 2;
set P [5] := 3;
set P [6] := 4;
set P [7] .= 5 6;
set KR .= 1;
set KN := 2·,
param r :=
[0,1,1] 0 [0,1,2] 0
[1,1,1] 2 [1,1,2] 5 [1,2,1] 1 [1,2,2] 1
[2,1,1] 3 [2,1,2] 6 [2,2,1] 3 [2,2,2] 2
[3,1,1] 4 [3,1,2] 2 [3,2,1] 2 [3,2,2] 2
[4,1,1] 3 [4,1,2] 6 [4,2,1] 4 [4,2,2] 4
[5,1,1] 3 [5,1,2] 1
[6,1,1] 2 [6,1,2] 1 [6,2,1] 1 [6,2,2] 1
[7,1,1] 0 [7,1,2] 0
param RR :=
[1] 4·,
param RN :=
[2] 15;
param EF :=
[0] 0
[1] 3
[2] 2
[3] 5
[4] 4
[5] 8
[6] 8
[7] 8;
param LF .-
[0] 14
[1] 17
[2] 16
[3] 19
[4] 18
[5] 22
[6] 22
[7] 22
Bibliography
[1) M. K. Agrawal, S. E. Elmaghraby, and W. S. Herroelen. DAGEN: A generator

of testsets for project activity nets. European Journal of Operational Research,
90:376-382, 1996.
[2) T. Ahn and S. S. Erenguc. The resource-constrained project scheduling prob-
lem with multiple crashable modes - An exact solution method. Technical
Report #95-101, University of Florida, Gainesville, 1995.
[3) T. Ahn and S. S. Erenguc. The resource-constrained project scheduling prob-
lem with multiple crashable modes - A heuristic procedure. European Journal
of Operational Research, 107:250-259, 1998.
[4) C. Akkan. Two heuristics based on a graph induction method for the dis-
crete time-cost tradeoff problem. Technical report, Koc University, Istanbul,
Turkey, 1997.
[5) R. Alvarez-Valdes and J. M. Tamarit. Algoritmos heurfsticos deterministas
y aleatorios en secuenciac6n de proyectos con recursos limitados. Questiio,
13:173-191, 1989.
[6) R. Alvarez-Valdes and J. M. Tamarit. Heuristic algorithms for resource-
constrained project scheduling: A review and an empirical analysis. In Slowin-
ski and Weglarz [187), pages 113-134.
[7) J. M. Anthonisse, K. M. van Hee, and J. K. Lenstra. Resource-constrained
project scheduling: An international exercise in DSS development. Decision
Support Systems, pages 249-254, 1988.
[8) T. Baar, P. Brucker, and S. Knust. Tabu-search algorithms and lower
bounds for the resource-constrained project scheduling problem. In S. Voss,
S. Martello, I. Osman, and C. Roucairol, editors, Meta-heuristics: Advances
and trends in local search paradigms for optimization, pages 1-8. Kluwer,
Boston, Massachusetts, 1998.
[9) A. J. G. Babu and N. Suresh. Project management with time, cost, and
quality considerations. European Journal of Operational Research, 88:320-
327, 1996.
[10) K. Backhaus, B. Erichson, W. Plinke, and R. Weiber. Multivariate Anal-
ysemethoden: Eine anwendungsorientierte Einfuhrung. Springer, Berlin, Ger-
many, 1996.
194 BIBLIOGRAPHY
[11] A. B. Badiru. Project Management in Manufacturing and High Technology

Operations. Wiley, New York, 1988.
[12] M. Bartusch, R. H. Mohring, and F. J. Radermacher. Scheduling project
networks with resource constraints and time windows. Annals of Operations
Research, 16:201-240, 1988.
[13] J. C. Bean. Genetic algorithms and random keys for sequencing and opti-
mization. ORSA Journal on Computing, 6:154-160, 1994.
[14] U. Belhe and A. Kusiak. Resource-constrained scheduling of hierarchically
structured design activity networks. IEEE Transactions on Engineering Man-
agement, 52:150-158, 1995.
[15] C. E. Bell and J. Han. A new heuristic solution method in resource-
constrained project scheduling. Naval Research Logistics, 38:315-331, 1991.
[16] R. B. Bey, R. H. Doersch, and J. H. Patterson. The net present value criterion:
Its impact on project scheduling. Project Management Quarterly, 12:35-45,
1981.
[17] L. Bianco, P. Dell'Olmo, and M. G. Speranza. Heuristics for multimode
scheduling problems with dedicated resources. European Journal of Opera-
tional Research, 107:260-271, 1998.
[18] N. Bixby and E. Boyd. Using the CPLEX callable library. CPLEX Optimiza-
tion Inc., Houston, Texas, 1996.
[19] J. Blazewicz, J. K. Lenstra, and A. H. G. Rinnooy Kan. Scheduling sub-
ject to resource constraints: Classification and complexity. Discrete Applied
Mathematics, 5:11-24, 1983.
[20] F. F. Boctor. Some efficient multi-heuristic procedures for resource-
constrained project scheduling. European Journal of Operational Resear'ch,
49:3-13, 1990.
[21] F. F. Boctor. Heuristics for scheduling projects with resource restrictions
and several resource-duration modes. International Journal of Production
Research, 31:2547-2558, 1993.
[22] F. F. Boctor. An adaptation of the simulated annealing algorithm for solving
resource-constrained project scheduling problems. International Journal of
Production Research, 34:2335-2351, 1996.
[23] F. F. Boctor. A new and efficient heuristic for scheduling projects with re-
source restrictions and multiple execution modes. European Journal of Op-
erational Research, 90:349-361, 1996.
[24] J. Bottcher, A. Drexl, R. Kolisch, and F. Salewski. Project scheduling under
partially renewable resource constraints. Management Science, 45:543-559,
1999.
[25] K. Bouleimen and H. Lecocq. A new efficient simulated annealing algorithm
for the resource-constrained project scheduling problem. Technical report,
Universite de Liege, Belgium, 1998.
BIBLIOGRAPHY 195
[26] P. Brucker, A. Drexl, R. Mohring, K. Neumann, and E. Pesch. Resource-

constrained project scheduling: Notation, classification, models, and meth-
ods. European Journal of Operational Research, 112:3~41, 1999.
[27] P. Brucker and S. Knust. A linear programming and constraint propagation-
based lower bound for the RCPSP. Technical report, Universitat Osnabruck,
Germany, 1998.
[28] P. Brucker and S. Knust. Solving large-sized resource-constrained project
scheduling problems. In Weglarz [207], pages 27~51.
[29] P. Brucker, S. Knust, A. Schoo, and O. Thiele. A branch-and-bound algorithm
for the resource-constrained project scheduling problem. European Journal
of Operational Research, 107:272~288, 1998.
[30] J. H. Cho and Y. D. Kim. A simulated annealing algorithm for resource-
constrained project scheduling problems. Journal of the Operational Research
Society, 48:736~744, 1997.
[31] N. Christofides, R. Alvarez-Valdes, and J. M. Tamarit. Project scheduling
with resource constraints: A branch and bound approach. European Journal
of Operational Research, 29:262~273, 1987.
[32] P. C. Chu and J. E. Beasley. A genetic algorithm for the multidimensional
knapsack problem. Technical report, The Management School, Imperial Col-
lege, London, England, 1997.
[33] D. 1. Cleland and W. R. King. Systems analysis and project management.
McGraw-Hill, New York, 1983.
[34] R. W. Conway, W. L. Maxwell, and L. W. Miller. Theory of scheduling.
Addison-Wesley, Reading, Massachusetts, 1967.
[35] D. F. Cooper. Heuristics for scheduling resource-constrained projects: An
experimental investigation. Management Science, 22:1186~1194, 1976.
[36] D. F. Cooper. A note on serial and parallel heuristics for resource-constrained
project scheduling. Foundations of Control Engineering, 2:131~133, 1977.
[37] E. M. Davies. An experimental investigation of resource allocation in muli-
tactivity projects. Operations Research Quarterly, 24:587~591, 1973.
[38] E. W. Davis and J. H. Patterson. A comparison of heuristic and optimum
solutions in resource-constrained project scheduling. Management Science,
21:944~955, 1975.
[39] N. Dayanand and R. Padman. On modelling payments in projects. Journal

of the Operational Research Society, 48:906~918, 1997.
[40] P. De, J. Dunne, J. B. Ghosh, and C. E. Wells. Complexity of the discrete
time-cost tradeoff problem for project networks. Operations Research, 45:302~
306, 1997.
[41] B. de Reyck, E. L. Demeulemeester, and W. S. Herroelen. Local search
methods for the discrete time/resource trade-off problem in project networks.
Naval Research Logistics, 45:533~578, 1998.
196 BIBLIOGRAPHY
[42] B. de Reyck and W. S. Herroelen. Assembly line balancing by resource-

constrained project scheduling - A critical appraisal. Technical Report 9505,
Katholieke Universiteit Leuven, Belgium, 1995.
[43] B. de Reyck and W. S. Herroelen. A branch-and-bound procedure for the
resource-constrained project scheduling problem with generalized precedence
relations. European Journal of Operational Research, 111:157-174, 1998.
[44] F. Della Croce. Generalized pairwise interchanges and machine scheduling.
European Journal of Operational Research, 83:310-319, 1995.
[45] E. L. Demeulemeester. Minimizing resource-availability costs in time-limited
project networks. Management Science, 41:1590-1598, 1995.
[46] E. L. Demeulemeester, B. de Reyck, and W. S. Herroelen. The discrete
time/resource trade-off problem in project networks - a branch-and-bound
approach. Technical Report 9717, Katholieke Universiteit Leuven, Belgium,
1997.
[47] E. L. Demeulemeester, B. Dodin, and W. S. Herroelen. A random network
activity generator. Operations Research, 41:972-980, 1993.
[48] E. L. Demeulemeester and W. S. Herroelen. A branch-and-bound procedure
for the multiple resource-constrained project scheduling problem. Manage-
ment Science, 38:1803-1818, 1992.
[49] E. L. Demeulemeester and W. S. Herroelen. Modelling setup times, process
batches and transfer batches using activity network logic. European Journal
[50] E. L. Demeulemeester and W. S. Herroelen. A branch-and-bound procedure
for the generalized resource-constrained project scheduling problem. Opera-
tions Research, 45:201-212, 1997.
[51] E. L. Demeulemeester and W. S. Herroelen. New benchmark results for
the resource-constrained project scheduling problem. Management Science,
43:1485-1492, 1997.
[52] E. L. Demeulemeester, W. S. Herroelen, and S. E. Elmaghraby. Optimal
procedures for the discrete time/cost trade-off problem in project networks.
[53] E. L. Demeulemeester, W. S. Herroelen, W. P. Simpson, S. Baroum, J. H.
Patterson, and K.-K. Yang. On a paper by Christofides et al. for solving the
multiple-resource constrained single project scheduling problem. European
Journal of Operational Research, 76:218-228, 1994.
[54] R. H. Doersch and J. H. Patterson. Scheduling a project to maximize its
present value: A zero-one programming approach. Management Science,
23:882-889, 1977.
[55] W. Domschke and A. Drexl. Einfiihrung in Operations Research. Springer,
Berlin, Germany, 1990.
[56] M. Dorigo, V. Maniezzo, and A. Colorni. The ant system: Optimization by
a colony of cooperating agents. IEEE Transactions on Systems, Man, and
Cybernetics, 26:1-13, 1996.
BIBLIOGRAPHY 197
[57] U. Dorndorf and E. Pesch. Evolution based learning in a job shop scheduling
environment. Computers fj Operations Research, 22:25-40, 1995.
[58] U. Dorndorf, E. Pesch, and T. Phan Huy. A time-oriented branch-and-bound
algorithm for resource-constrained project scheduling with generalized prece-
dence constraints. Technical report, Universitat Bonn, Germany, 1998.
[59] A. Drexl. Scheduling of project networks by job assignment. Management
Science, 37:1590-1602, 1991.
[60] A. Drexl, ·W. Eversheim, R. Grempe, and H. Esser. elM im Werkzeug-
maschinenbau: Der PRISMA-Montageleitstand. Zeitschrift fur betriebswirl-
schaftliche Forschung, 46:279-295, 1994.
[61] A. Drexl and J. Griinewald. Nonpreemptive multi-mode resource-constrained
project scheduling. lIE Transactions, 25:74-81, 1993.
[62] A. Drexl, J. Juretzka, F. Salewski, and A. Schirmer. New modelling concepts
and their impact on resource-constrained project scheduling. In Weglarz [207],
pages 413-432.
[63] A. Drexl and R. Kolisch. Assembly management in machine tool manufac-
turing and the PRISMA-Leitstand. Production and Inventory Management
Journal, 37( 4}:55-57, 1996.
[64] A. Drexl, R. Nissen, J. H. Patterson, and F. Salewski. ProGen/1l"x - An
instance generator for resource-constrained project scheduling problems with
partially renewable resources and further extensions. Technical report, Uni-
versitat Kiel, Germany, 1997.
[65] A. Drexl and F. Salewski. Distribution requirements and compactness con-
straints in school timetabling. European Journal of Operational Research,
102:193-214, 1997.
[66] G. Dueck. New optimization heuristics: The great deluge algorithm and the
record-to-record travel. Journal of Computational Physics, 104:86-92, 1993.
[67] G. Dueck and T. Scheuer. Threshold accepting: A general purpose opti-
mization algorithm appearing superior to simulated annealing. Journal of
Computational Physics, 90:161-175, 1990.
[68] H. Dyckhoff. A typology of cutting and packing problems. European Journal
[69] H. Dyckhoff and U. Finke. Cutting and packing in production and distribution.
Physica, Heidelberg, Germany, 1992.
[70] A. E. Eiben, E. H. L. Aarts, and K. M. van Hee. Global convergence of genetic
algorithms: A markov chain analysis. Lecture Notes in Computer Science,
496:4-12, 1990.
[71] S. E. Elmaghraby. An algebra for the analysis of generalized networks. Man-
agement Science, 10:419-514, 1964.
[72] S. E. Elmaghraby. Activity networks: Project planning and control by network
models. Wiley, New York, 1977.
198 BIBLIOGRAPHY
[73] S. E. Elmaghraby. Resource allocation via dynamic programming in activity

networks. European Journal of Operational Research, 64:199-215, 1993.
[74] E. A. Elsayed. Algorithms for project scheduling with resource constraints.
International Journal of Production Research, 20:95-103, 1982.
[75] H. Exeler. Das homogene Packproblem in der betriebswirtschaftlichen Logis-
tik. Physica, Heidelberg, Germany, 1988.
[76] F. Farid and S. Manoharan. Comparative analysis of resource allocation
capabilities of project management software packages. Project Management
Journal, 24:35-44, 1996.
[77] T. Fitting. Bedeutung der intrazellulii.ren S-Adenosylmethionindecarboxy-
lase-Aktivitat fUr die Regulation des Polyaminstoffwechsels wahrend des
Camostat-stimulierten Pankreaswachstums von Ratten. MD Dissertation,
1998. Universitat Kiel, Germany.
[78] R. Fourer, D. M. Gay, and B. W. Kernighan. AMPL - A modeling language
fOT mathematical programming. Boyd & Fraser Publishing Company, Danvers,
Massachusetts, 1993.
[79] B. Franck and K. Neumann. Resource-constrained project scheduling with
time windows: Structural questions and priority rule methods. Technical
Report WIOR-492, Universitat Karlsruhe, Germany, 1997.
[80] B. Franck and C. Schwindt. Different resource-constrained project scheduling
models with minimal and maximal time-lags. Technical Report WIOR-450,
Universitat Karlsruhe, Germany, 1995.
[81] B. Franck and J. Zimmermann. Meta-Heuristiken. Technical Report WIOR-
496, Universitat Karlsruhe, Germany, 1997.
[82] S. French. Sequencing and scheduling: An introduction to the mathematics of
the job-shop. Wiley, New York, 1982.
[83] M. R. Garey, R. L. Graham, D. S. Johnson, and A. C.-C. Yao. Resource
constrained scheduling as generalized bin packing. Journal of Combinatorial
Theory, 21:257-298, 1976.
[84] M. R. Garey and D. S. Johnson. Computers and intractability: A guide to
the theory of NP-completeness. Freeman, San Francisco, California, 1979.
[85] F. Glover. Tabu search - Part I. ORSA Journal on Computing, 1:190-206,
1989.
[86] F. Glover. Tabu search - Part II. ORSA Journal on Computing, 2:4-32, 1989.
[87] F. Glover and H. J. Greenberg. New approaches for heuristic search: A
bilateral linkage with artificial intelligence. European Journal of Operational
Research, 39:119-130, 1989.
[88] D. E. Goldberg. Genetic algorithms in search, optimization, and machine
learning. Addison-Wesley, Reading, Massachusetts, 1989.
[89] M. Hapke, A. Jaszkiewicz, and R. Slowinski. Interactive analysis of multiple-
criteria project scheduling problems. European Journal of Operational Re-
search, 107:315-324, 1998.
BIBLIOGRAPHY 199
(90) S. Hartmann. Project scheduling with multiple modes: A genetic algorithm.

Manuskripte aus den Instituten fiir Betriebswirtschaftslehre 435, Universitiit
Kiel, Germany, 1997.
(91) S. Hartmann. Scheduling medical research experiments - An application
of project scheduling methods. Manuskripte aus den Instituten fiir Betrieb-
swirtschaftslehre 452, Universitiit Kiel, Germany, 1997.
(92) S. Hartmann. A competitive genetic algorithm for resource-constrained
project scheduling. Naval Research Logistics, 45:733-750, 1998.
(93) S. Hartmann and A. Drexl. Project scheduling with multiple modes: A
comparison of exact algorithms. Networks, 32:283-297, 1998.
(94) S. Hartmann, J. Frahm, and F. Salewski. Planning attractive travel routes
- Model, methods, and applications. Technical report, Universitiit Kiel,
Germany. In preparation.
(95) S. Hartmann and R. Kolisch. Experimental investigation of state-of-the-art
heuristics for the reso,Urce-constrained project scheduling problem. European
Journal of Operational Research. Forthcoming.
(96) S. Hartmann and A. Sprecher. A note on "Hierarchical models for multi-
project planning and scheduling". European Journal of Operational Research,
94:377-383, 1996.
(97) A. C. Hax and D. Candea. Production and inventory management. Prentice-
Hall, New Jersey, 1984.
(98) R. Heilmann. A branch-and-bound procedure for MRCPSP /max. Technical
Report WIOR-512, Universitiit Karlsruhe, Germany, 1998.
(99) R. Heilmann and C. Schwindt. Lower bounds for RCPSP /max. Technical
Report WIOR-511, Universitiit Karlsruhe, Germany, 1997.
(100) J. W. Herrmann, C.-Y. Lee, and J. Hinchman. Global job shop scheduling
with a genetic algorithm. Production and Operations Management, 4:30-45,
1995.
(101) W. S. Herroelen, E. L. Demeulemeester, and B. de Reyck. A classification
scheme for project scheduling. In Weglarz (207), pages 1-26.
(102) W. S. Herroelen, P. van Dommelen, and E. L. Demeulemeester. Project
network models with discounted cash flows: A guided tour through recent
developments. European Journal of Operational Research, 100:97-121, 1997.
(103) H. J. Holland. Adaptation in natural and artificial systems. University of
Michigan Press, Ann Arbor, 1975.
(104) J. J. Hopfield and D. W. Tank. Neural computation of decisions in optimiza-
tion problems. Biological Cybernetics, 52:141-152, 1985.
(105) O. Icmeli and S. S. Erenguc. A branch and bound procedure for the resource
constrained project scheduling problem with discounted cash-flows. Manage-
ment Science, 42:1395-1408, 1996.
200 BIBLIOGRAPHY
[106] O. Icmeli, S. S. Erenguc, and C. J. Zappe. Project scheduling problems:

A survey. International Journal of Operations fj Production Management,
13:80-91, 1993.
[107] O. Icmeli-Thkel and W. O. Rom. Ensuring quality in resource constrained
project scheduling. European Journal of Operational Research, 103:483-496,
1997.
[108] C. Jordan. Batching and scheduling - Models and methods for several prob-
lem classes. Number 437 in Lecture Notes in Economics and Mathematical
Systems. Springer, Berlin, Germany, 1996.
[109] T. T. Kapuscinska, T. E. Morton, and P. Ramnath. High-intensity heuristics
to minimize weighted tardiness in resource-constrained multiple dependent
project scheduling. Technical report, Carnegie Mellon University, Pittsburgh,
Pennsylvania, 1998.
[110] J. E. Kelley, Jr. Critical-path planning and scheduling: Mathematical basis.
Operations Research, 9:296-320, 1961.
[Ill] J. E. Kelley, Jr. The critical path method: Resources planning and scheduling.
In J. F. Muth and G. L. Thompson, editors, Industrial scheduling, pages 347-
365. Prentice-Hall, New Jersey, 1963.
[112] Y.-D. Kim. A backward approach in list scheduling algorithms for multi-
machine tardiness problems. Computers fj Operations Research, 22:307-319,
1995.
[113] A. Kimms. Optimization guided lower and upper bounds for the resource
investment problem. Manuskripte aus den Instituten fur Betriebswirtschaft-
slehre 481, Universitat Kiel, Germany, 1998.
[114] S. Kirkpatrick, C. D. Gelatt, Jr., and M. P. Vecchi. Optimization by simulated
annealing. Science, 220:671-680, 1983.
[115] R. Klein. Bidirectional planning - Improving priority rule based heuris-
tics for scheduling resource-constrained projects. Schriften zur Quantitativen
Betriebswirtschaftslehre 10/98, Technische Universitat Darmstadt, Germany,
1998.
[116] R. Klein and A. Scholl. Scattered branch and bound - An adaptive search
strategy applied to resource-constrained project scheduling. Schriften zur
Quantitativen Betriebswirtschaftslehre 6/98, Technische Universitat Darm-
stadt, Germany, 1998.
[117] R. Klein and A. Scholl. Computing lower bounds by destructive improve-
ment - An application to resource-constrained project scheduling. European
[118] U. Kohlmorgen, H. Schmeck, and K. Haase. Experiences with fine-grained
parallel genetic algorithms. Annals of Operations Research. Forthcoming.
[119] R. Kolisch. Resource allocation capabilities of commercial project manage-
ment systems - Resource management boosts up the German stock ex-
change. Interfaces. Forthcoming.
BmLIOGRAPHY 201
[120] R. Kolisch. Project scheduling under resource constraints - Efficient heuristics

for several problem classes. Physica, Heidelberg, Germany, 1995.
[121] R. Kolisch. Efficient priority rules for the resource-constrained project
scheduling problem. Journal of Operations Management, 14:179-192, 1996.
[122] R. Kolisch. Serial and parallel resource-constrained project scheduling meth-
ods revisited: Theory and computation. European Journal of Operational
Research, 90:320-333, 1996.
[123] R. Kolisch. Planungsfunktionen von Projektmanagementsystemen. Markt-
forschung fj Management, 41:234-239, 1997.
[124] R. Kolisch and A. Drexl. Adaptive search for solving hard project scheduling
problems. Naval Research Logistics, 43:23-40, 1996.
[125] R. Kolisch and A. Drexl. Local search for nonpreemptive multi-mode resource-
constrained project scheduling. IIE Transactions, 29:987-999, 1997.
[126] R. Kolisch and S. Hartmann. Heuristic algorithms for solving the resource-
constrained project scheduling problem: Classification and computational
analysis. In Weglarz [207], pages 147-178.
[127] R. Kolisch and K. Hempel. Entscheidungstheoretisch fundierte Bewertung
von Standardsoftware fUr das Projektmanagement. Wirtschaftsinformatik,
38:399-410, 1996.
[128] R. Kolisch and R. Padman. An integrated survey of project scheduling.
Manuskripte aus den Instituten fiir Betriebswirtschaftslehre 463, Universitat
[129] R. Kolisch and A. Sprecher. PSPLIB - a project scheduling problem library.
[130] R. Kolisch, A. Sprecher, and A. Drexl. Characterization and generation of a
general class of resource-constrained project scheduling problems. Manage-
ment Science, 41:1693-1703, 1995.
[131] R. Kolisch, A. Sprecher, and C. Schwindt. Benchmark instances for project
scheduling problems. In Weglarz [207], pages 197-212.
[132] S. R. Lawrence. Resource constrained project scheduling - A computational
comparison of heuristic scheduling techniques. Technical report, Carnegie
Mellon University, Pittsburgh, Pennsylvania, 1985.
[133] J.-K. Lee and Y.-D. Kim. Search heuristics for resource-constrained project
scheduling. Journal of the Operational Research Society, 47:678-689, 1996.
[134] V. J. Leon and B. Ramamoorthy. Strength and adaptability of problem-
space based neighborhoods for resource-constrained scheduling. OR Spek-
trum, 17:173-182, 1995.
[135] K. Y. Li and R. J. Willis. An iterative scheduling technique for resource-
constrained project scheduling. European Journal of Operational Research,
56:370-379, 1992.
202 BIBLIOGRAPHY
[136] F.-H. F. Liu and C.-J. Hsiao. A three-dimensional pallet loading method for
single-size boxes. Journal of the Operational Research Society, 48:726-735,
1997.
[137] C. Loser, T. Fitting, and U. R. FOlsch. Importance of intracellular s-adenosyl-
methionine decarboxylase activity for the regulation of camostate-induced
pancreatic polyamine metabolism and growth: In vivo effect of two novel
s-adenosylmethionine decarboxylase inhibitors. Digestion, 58:258-265, 1997.
[138] C. Loser, U. R. Folsch, C. Paprotny, and W. Creutzfeld. Polyamines in
colorectal cancer: Evaluation of polyamine concentrations in colon tissue,
serum, and urine of 50 patients with colorectal cancer. Cancer, 65:958-966,
1990.
[139] D. G. Malcolm, J. H. Roseboom, C. E. Clark, and W. Fazar. Applications
of a technique for research and development program evaluation. Operations
Research, 7:646-669, 1959.
[140] L. J. Marton and A., E. Pegg. Polyamines as targets for therapeutic interven-
tion, Annual Review of Pharmacology and Toxicology, 35:55-91, 1995.
[141] D. C. Mattfeld. Evolutionary search and the job shop. Physica, Heidelberg,
Germany, 1996,
[142] H. E. Mausser and S. R. Lawrence, Exploiting block structure to improve
resource-constrained project schedules. Technical report, Graduate School of
Business Administration, University of Colorado, 1995.
[143] W, S, McCulloch and W. Pitts, A logical calculus of the ideas immanent in
nervous activity, Bulletin of Mathematical Biophysics, 5:115-133, 1943.
[144] Z. Michalewicz. Heuristic methods for evolutionary computation techniques.
Journal of Heuristics, 1:177-206, 1995.
[145] A. Mingozzi, V, Maniezzo, S, Ricciardelli, and L. Bianco. An exact algo-
rithm for the resource-constrained project scheduling problem based on a
new mathematical formulation. Management Science, 44:714-729, 1998,
[146] J. J, Moder, C, R. Phillips, and E. W, Davis, Project Management with
CPM, PERT and precedence diagramming, Van Nostrand Reinhold, New
York,1983,
[147] R. H. Mohring, F, Stork, and M, Uetz. Resource-constrained project schedul-
ing with time windows: A branching scheme based on dynamic release
dates. Technical Report 596, Fachbereich Mathematik, Technische Univer-
sitat Berlin, Germany, 1998.
[148] R. Morabito and S. Morales. A simple and effective recursive procedure for the
manufacturer's pallet loading problem. Journal of the Operational Research
Society, 49:819-828, 1998.
[149] M. Mori and C. C. Tseng. A genetic algorithm for the multi-mode resource-
constrained project scheduling problem. European Journal of Operational
Research, 100:134-141, 1997.
BIBLIOGRAPHY 203
[150] K. S. Naphade, S. D. Wu, and R. H. Storer. Problem space search algorithms

for resource-constrained project scheduling. Annals of Operations Research,
70:307-326, 1997.
[151] K. Neumann. Stochastic project ne~works: Temporal analysis, scheduling and
cost minimization. Number 344 in Lecture Notes in Economics and Mathe-
matical Systems. Springer, Berlin, Germany, 1990.
[152] M. J. Norusis. The SPSS guide to data analysis. SPSS Inc., Chicago, illinois,
1990.
[153] O. Oguz and H. Bala. A comparative study of computational procedures for
the resource constrained project scheduling problem. European Journal of
Operational Research, 72:406-416, 1994.
[154] L. Ozdamar. A genetic algorithm approach to a general category project
scheduling problem. IEEE 7hmsactions on Systems, Man, and Cybernetics.
Forthcoming.
[155] L. Ozdamar and G: Ulusoy. A local constraint based analysis approach to
project scheduling under general resource constraints. European Journal of
Operational Research, 79:287-298, 1994.
[156] L. Ozdamar and G. Ulusoy. A survey on the resource-constrained project
scheduling problem. lIE 7ransactions, 27:574-586, 1995.
[157] L. Ozdamar and G. Ulusoy. An iterative local constraint based analysis for
solving the resource-constrained project scheduling problem. Journal of Op-
erations Management, 14:193-208, 1996.
[158] L. Ozdamar and G. Ulusoy. A note on an iterative forward/backward schedul-
ing technique with reference to a procedure by Li and Willis. European Jour-
nal of Operational Research, 89:400-407, 1996.
[159] R. Padman, D. E. Smith-Daniels, and V. L. Smith-Daniels. Heuristic schedul-
ing ofresource-constrained projects with cash flows. Naval Research Logistics,
44:364-381, 1997.
[160] J. H. Patterson. Alternate methods of project scheduling with limited re-
sources. Naval Research Logistics Quarterly, 20:767-784, 1973.
[161] J. H. Patterson. Project scheduling: The effects of problem structure on
heuristic performance. Naval Research Logistics Quarterly, 23:95-123, 1976.
[162] J. H. Patterson. A comparison of exact approaches for solving the multi-
ple constrained resource, project scheduling problem. Management Science,
30:854-867, 1984.
[163] J. H. Patterson, R. Slowinski, F. B. Talbot, and J. Weglarz. An algorithm for
a general class of precedence and resource constrained scheduling problems.
In Slowinski and Weglarz [187], pages 3-28.
[164] S. Philips, Jr. Project management duration/resource tradeoff analysis: An
application of the cut search approach. Journal of the Operational Research
Society, 47:697-701, 1996.
204 BIBLIOGRAPHY
[165] E. Pinson, C. Prins, and F. Rullier. Using tabu search for solving the resource-
constrained project scheduling problem. In Proceedings of the fourth inter-
national workshop on project management and scheduling, pages 102-106.
Leuven, Belgium, 1994.
[166] M. Pirlot. General local search methods. European Journal of Operational
Research, 92:493-511, 1996.
[167] B. Pollack-Johnson. Hybrid structures and improving forecasting and schedul-
ing in project management. Journal of Operations Management, 12:101-117,
1995.
[168] A. A. B. Pritsker and W. W. Happ. GERT: Graphical evaluation and re-
view technique - Part I: Fundamentals. Journal of Industrial Engineering,
17:267-274, 1966.
[169) A. A. B. Pritsker, L. J. Watters, and P. M. Wolfe. Multiproject scheduling
with limited resources: A zero-one programming approach. Management
Science, 16:93-107, 1969.
[170] F. J. Radermacher. Scheduling of project networks. Annals of Operations
Research, 4:227-252, 1985.
[171) C. R. Reeves. Genetic algorithms and combinatorial optimization. In V. J.
Rayward-Smith, editor, Applications of modem heuristic methods, pages 111-
125. Alfred Waller Ltd., Henley-on-Thames, 1995.
[172) F. Salewski, A. Schirmer, and A. Drexl. Project scheduling under resource
and mode identity constraints: Model, complexity, methods, and application.
[173) S. E. Sampson and E. N. Weiss. Local search techniques for the generalized
resource-constrained project scheduling problem. Naval Research Logistics,
40:665-675, 1993.
[174) A. Schirmer. Case-based reasoning and improved adaptive search for project
scheduling. Manuskripte aus den Instituten fUr Betriebswirtschaftslehre 472,
Universitat Kiel, Germany, 1998.
[175] A. Schirmer and A. Drexl. Allocation of partially renewable resources -
Concepts, models, and applications. Manuskripte aus den Instituten fUr Be-
triebswirtschaftslehre 455, Universitat Kiel, Germany, 1997.
[176] A. Schirmer and S. Riesenberg. Parameterized heuristics for project schedul-
ing - Biased random sampling methods. Manuskripte aus den Instituten fiir
Betriebswirtschaftslehre 456, Universitat Kiel, Germany, 1997.
[177] A. Schirmer and S. Riesenberg. Class-based control schemes for parame-
terized project scheduling heuristics. Manuskripte aus den Instituten fUr
Betriebswirtschaftslehre 471, Universitat Kiel, Germany, 1998.
[178] L. Schrage. Solving resource-constrained network problems by implicit enu-
meration - Nonpreemptive case. Operations Research, 18:263-278, 1970.
[179) J. M. J. Schutten. List scheduling revisited. Operations Research Letters,
18:167-170, 1996.
BIBLIOGRAPHY 205
[180) C. Schwindt. ProGen/max: A new problem generator for different resource-

constrained project scheduling problems with minimal and maximal time lags.
Technical Report \VIOR-449, Universitiit Karlsruhe, Germany, 1995.
[181) C. Schwindt. Verfahren zur Losung des ressourcenbeschriinkten Projektdauer-
minimierungsproblems mit planungsabhiingigen Zeitfens tern. Shaker, Aachen,
Germany, 1998.
[182) L. R. Shaffer, J. B. Ritter, and W. L. Meyer. The critical-path method.
McGraw-Hill, New York, 1965.
[183) A. Shtub, L. J. LeBlanc, and Z. Cai. Scheduling programs with repetitive
projects: A comparison of a simulated annealing, a genetic and a pair-wise
swap algorithm. European Journal of Operational Research, 88:124-138, 1996.
[184) R. Slowinski. Two approaches to problems of resource allocation among
project activities: A comparative study. Journal of the Operational Research
Society, 31:711-723, 1980.
[185) R. Slowinski. Multiobjective network scheduling with efficient use of renew-
able and nonrenewable resources. European Journal of Operational Research,
7:265-273, 198!.
[186) R. Slowinski, B. Soniewicki, and J. Weglarz. DSS for multiobjective project
scheduling subject to multiple-category resource constraints. European Jour-
nal of Operational Research, 79:220-229, 1994.
[187) R. Slowinski and J. Weglarz, editors. Advances in project scheduling. Elsevier,
Amsterdam, the Netherlands, 1989.
[188) M. G. Speranza and C. Vercellis. Hierarchical models for multi-project plan-
ning and scheduling. European Journal of Operational Research, 64:312-325,
1993.
[189) A. Sprecher. A competitive exact algorithm for assembly line balancing.
International Journal of Production Research. Forthcoming.
[190) A. Sprecher. Resource-constrained project scheduling: Exact methods for the
multi-mode case. Number 409 in Lecture Notes in Economics and Mathemat-
ical Systems. Springer, Berlin, Germany, 1994.
[191) A. Sprecher. Solving the RCPSP efficiently at modest memory requirements.
Manuskripte aus den Instituten fUr Betriebswirtschaftslehre 425, Universitiit
[192) A. Sprecher and A. Drexl. Multi-mode resource-constrained project schedul-
ing by a simple, general and powerful sequencing algorithm. European Journal
[193) A. Sprecher, S. Hartmann, and A. Drexl. An exact algorithm for project
scheduling with multiple modes. OR Spektrum, 19:195-203, 1997.
[194) A. Sprecher, R. Kolisch, and A. Drexl. Semi-active, active and non-delay
schedules for the resource-constrained project scheduling problem. European
206 BIBLIOGRAPHY
[195] J. P. Stinson, E. W. Davis, and B. M. Khumawala. Multiple resource-

constrained scheduling using branch and bound. AIlE Transactions, 10:252-
259, 1978.
[196] R. H. Storer, S. D. Wu, and V. Vaccari. New search spaces for sequenc-
ing problems with application to job shop scheduling. Management Science,
38:1495-1509, 1992.
[197] F. B. Talbot. Resource-constrained project scheduling with time-resource
tradeoffs: The nonpreemptive case. Management Science, 28:1197-1210,
1982.
[198] F. B. Talbot and J. H. Patterson. An efficient integer programming algo-
rithm with network cuts for solving resource-constrained project scheduling
problems. Management Science, 24:1163-1174, 1978.
[199] A. Thesen. Heuristic scheduling of activities under resource and precedence
restrictions. Management Science, 23:412-422, 1976.
[200] P. R. Thomas and S. Salhi. An investigation into the relationship of heuristic
performance with network-resource characteristics. Journal of the Opera-
tional Research Society, 48:34-43, 1997.
[201] P. R. Thomas and S. Salhi. A tabu search approach for the resource con-
strained project scheduling problem. Journal of Heuristics, 4:123-139, 1998.
[202] G. Ulusoy and L. Ozdamar. Heuristic performance and network/resource
characteristics in resource-constrained project scheduling. Journal of the Op-
erational Research Society, 40:1145-1152, 1989.
[203] G. Ulusoy and L. Ozdamar. A constraint-based perspective in resource-
constrained project scheduling. International Journal of Production Research,
32:693-705, 1994.
[204] V. Valls, M. A. Perez, and M. S. Quintanilla. Heuristic performance in
large resource-constrained projects. Technical Report 92-2, Departament
D'Estadistica I Invecigacio Operativa, Universitat de Valencia, Spain, 1992.
[205] J. Weglarz. On certain models of resource allocation problems. Kybernetics,
9:61-66, 198!.
[206] J. Weglarz. Project scheduling with continuously divisible, doubly-con-
strained resources. Management Science, 27:1040-1057, 198!.
[207] J. Weglarz, editor. Project scheduling: Recent models, algorithms and appli-
cations. Kluwer, Amsterdam, the Netherlands, 1999.
[208] J. Weglarz, J. Blazewicz, W. Cellary, and R. Slowinski. Algorithm 520: An
automatic revised simplex method for constrained resource network schedul-
ing. ACM Transactions on Mathematical Software, 3:295-300, 1977.
[209] G. E. Whitehouse and J. R. Brown. GENRES: An extension of Brooks algo-
rithm for project scheduling with resource constraints. Computers f1 Indus-
trial Engineering, 3:261-268, 1979.
[210] D. Whitley, V. S. Gordon, and K. Mathias. Lamarckian evolution, the Bald-
win effect and function optimization. In Proceedings of the parallel problem
solving from nature, pages 6-15. Springer, Berlin, Germany, 1994.
BIBLIOGRAPHY 207
[211] T. Williams. A classified bibliography of recent research relating to project

risk management. European Journal of Operational Research, 85:18-38, 1995.
[212] M. Wottawa. PACKLIB: Ein ASCII-Datenformat fur Packungsprobleme.
Technical Report 96-216, Universitat Koln, Germany, 1996.
[213] J. Zimmermann. Heuristics for resource-levelling problems in project schedul-
ing with minimum and maximum time lags. Technical Report WIOR-491,
Universitat Karlsruhe, Germany, 1997.
List of Abbreviations
B&B branch-and-bound
BFS best fit strategy
BRS biased random sampling
cf. confer
CPU central processing unit
e.g. for example
FFS first fit strategy
GA genetic algorithm
GRPW greatest rank positional weight (priority rule)
i.e. that is
LCBA local constraint based analysis (priority rule)

LFT latest finish time (priority rule)
LST latest start time (priority rule)
MIRCPSP mode identity resource-constrained project scheduling prob-

lem
MRBRS modified regret based biased random sampling
MRCPSP multi-mode resource-constrained project scheduling prob-
lem
MSLK minimum slack (priority rule)
MTS most total successors (priority rule)
NBRS normalized biased random sampling

NPV net present value
RAND random (priority rule)

RBRS regret based biased random sampling
210 LIST OF ABBREVIATIONS
RCPSP resource-constrained project scheduling problem

RCPSP/n resource-constrained project scheduling problem with par-
tially renewable resources
RCPSP/r resource-constrained project scheduling problem with time-
dependent resource parameters
RS random sampling
SA simulated annealing
sec seconds
SGS schedule generation scheme
TS tabu search
vs. versus
WCS worst case slack (priority rule)

w.l.o.g. without loss of generality
w.r.t. with respect to
WRUP weighted resource utilization and precedence (priority rule)
List of Basic Notation
CHI children produced in a genetic algorithm
df. S minimal time lag between the finish time of activity i and
'J
the start time of activity j
minimal time lag between the start time of activity i and
the start time of activity j
delay alternative at level 9
release date of activity j
deadline of activity j
extension alternative at level 9

precedence based earliest finish time of activity j
set of eligible activities at level 9
precedence based earliest start time of activity j
f(·) fitness function

fj finish time of activity j
FJg set of activities finished at or before the decision point at
level 9
9 level in branch-and-bound algorithm or schedule generation

scheme
G generation in genetic algorithm
GEN number of generations in a genetic algorithm
I individual in genetic algorithm

ISL number of islands in extended genetic algorithm paradigm
J number of non-dummy activities

j=O dummy source activity
j = J +1 dummy sink activity
.:J set of non-dummy activities
212 LIST OF BASIC NOTATION
set of activities including summy source and sink

set of activities in process at level 9
set of renewable resources

set of nonrenewable resources
set of partially renewable resources
nonrenewable resource units exceeding the capacities in

mode assignment J.L
leftover capacity of nonrenewable resource k in mode assign-
ment J.L
precedence based latest finish time of activity j
precedence based latest start time of activity j
activity list
number ,of modes of activity j

set of modes of activity j
mode alternative at level 9
mode assignment function
Pj processing time of activity j

Pjm processing time of activity j if performed in mode m
p(j) selection probability of activity j in sampling methods
Pdeath (A) probability to die for individual A
Pmigration migration probability for island model
Pmutation mutation probability
Pj set of immediate predecessors of activity j
POP number of individuals in the population of a genetic algo-
rithm
POP population of genetic algorithm (list of individuals)
PS partial schedule
priority rule list (representation)
priority rule for the i-th scheduling decision
q position in one-point crossover

Ql, Q2 positions in two-point crossover
constant per-period-request of activity j for resource k

request of activity j for resource k in the t-th period of its
duration
request of activity j performed in mode m for resource k
constant per-period-availability of renewable resource k
availability of renewable resource k in period t
LIST OF BASIC NOTATION 213
R Vk availability of nonrenewable resource k

R'f,(PS) leftover capacity of nonrenewable resource k in partial sched-
ule PS
RFP resource factor of the renewable resources
RFv resource factor of the nonrenewable resources
RSP resource strength of the renewable resources
RSv resource strength of the nonrenewable resources
P random key array
Pj random key of activity j
Sj start time of activity j

prec
Sj earliest precedence feasible start time of activity j
S schedule
Sj set of immediate successors of activity j
5j set of all successors of activity j
SJg set of scheduled activities at level 9
SGSserial gene in extended genetic representation indicating the de-
coding procedure to be used
SO£A g set of extension alternatives at level 9
SODA g set of delay alternatives at level 9
SOMA g set of mode alternatives at level 9
(5 shift vector
(5j shift of activity j for shift vector representation
decision point at level 9 (time instant)

planning horizon (number of periods)
set of time instants
set of periods
v(j) priority value of activity j, computed by a priority rule
Xjt binary decision variable which indicates whether activity j

finishes at time t or not
Xjmt binary decision variable which indicates whether activity j
is performed in mode m and finishes at time t or not
~i i-th random number in sequence for uniform crossover
z makespan (objective function value)

List of Tables
2.1 Time windows for example instance . . . . . . . . . . . 9

2.2 Packing problems as special cases of project scheduling. 31
3.1 Accelerated variants of the algorithms to be tested 56

3.2 Average computation times .. . . . . . . . . . 58
3.3 Maximal computation times . . . . . . . . . . . 58
3.4 Average computation times for resource classes 58
3.5 Distribution of the computation times 58
4.1 Example for serial SGS. . 63

4.2 Example for parallel SGS 65
4.3 Priority Rules . . . . . . . 67
4.4 Selection probabilities for different sampling methods. 70
4.5 Survey of priority rule based heuristics for the RCPSP 71
4.6 Survey of metaheuristic approaches for the RCPSP 78
5.1 Alternative genetic operators - activity list GA 96

5.2 Impact of population size - activity list GA 96
5.3 Impact of initial population - activity list GA 97
5.4 Comparison of genetic algorithms . . 97
5.5 Average deviations w.r.t. time limit. . . . . 98
5.6 Average deviations from lower bound. . . . 98
5.7 Average deviations from best upper bound. 99
5.8 Impact of genetic operators . . . . . . . . . 100
5.9 Average percentage of the serial SGS in the initial population 104
6.1 Average deviations from optimal solution - J = 30 . 119

6.2 Average deviations from best solution - J = 60 119
6.3 Average deviations from best solution - J = 120 . . 120
6.4 Average deviations from critical path lower bound - J = 60 120
6.5 Average deviations from critical path lower bound - J = 120 121
6.6 Comparison of heuristics - Patterson instance set 121
6.7 Average deviations from optimal solution w.r.t. RSP . . . .. 125
216 LIST OF TABLES
6.8 Average deviations from optimal solution w.r.t. RFP 125

6.9 Average computation times of GAs w.r.t. project size. 126
7.1 Impact of local search improvement. . . . . . . . . . . 140

7.2 Impact of local search improvement - intermediate results 141
7.3 Average number of clusters w.r.t. generation number 143
7.4 New GA vs. two other heuristics . . . . . . . . 145
7.5 New GA vs. truncated B&B w.r.t. project size . . . 146
7.6 New GA vs. truncated B&B w.r.t. time limit . . . . 147
7.7 New GA vs. truncated B&B w.r.t. resource strength 147
8.1 Experiments and repetitions. . . . . . . . . . . . . 153

8.2 Calendar - working and examination days . . . . 153
8.3 Transforming experiment repetitions into activities 155
8.4 Makespan w.r.t. computation time . . . . . . . . . 156
8.5 Varying the maximal number of repetitions in process 160
8.6 Impact of calendar changes .. . . . 161
8.7 Changing the temporal arrangement . . . . . . . . . . 161
A.1 ProGen single-mode instances: Fixed parameter levels 183

A.2 ProGen single-mode instances: Variable parameter levels. 184
A.3 ProGen multi-mode instances: Fixed parameter levels 184
A.4 ProGen multi-mode instances: Variable parameter levels 185
B.1 MRCPSP symbols in AMPL formulation. . . . . . . . . 188

List of Figures
2.1 Project instance . . . . . . . . . . . . . . . . . . . . . . 7

2.2 Example schedule. . . . . . . . . . . . . . . . . . . . . . 7
2.3 Transforming the two-dimensional bin packing problem 27
2.4 Two-dimensional bin packing problem - rotating boxes 27
3.1 Project Instance . . . . . . . . . 49

3.2 Schedules of the Project Instance 49
5.1 Illustration of conditions for equal neighbor schedules 109
7.1 Project instance . . . . . . . . . . . . . . . . 130

7.2 Schedule of example individual [M . . . . . . 133
7.3 Improved schedule of example individual [M 137
8.1 Schedules for the RCPSP /T example instance 158

8.2 Modeling approach based on new precedence relations 162
8.3 Activity network of the interview project. . . . . . . . 170
Index
active schedule, 63, 102, 123, 138 doubly constrained resource, 12,
activity, 5 17,19
activity list, 63, 73, 86, 126, 131 due date, 17, 20, 22
activity-on-arc, 17 duration, 6
activity-on-node, 6, 17
adaptive method, 69,104,116,123 extension alternative, 39, 65
ant system, 72
field work, 164
aspiration criterion, 72
first fit strategy, 71, 133
assembly line balancing, 24
fitness, 85, 86, 132
forbidden set, 80
backward recursion, 8, 41, 133
forward recursion, 8, 76
best fit strategy, 72
forward-backward scheduling, 68,
bin packing problem, 25
145
bounding rule, 41
branch-and-bound, 34, 80, 145 GA, see genetic algorithm
genetic algorithm, 72, 83, 118, 122,
cash flow, 21 126, 129
computational results, 55, 94, 115, genotype, 84, 86, 138
138 global optimum, 71, 144
continuously divisible resource, 19 great deluge algorithm, 71
crashable modes, 15
crossover, 72, 85, 87, 92, 94, 105, hill climbing, 106
134
immediate selection, 46
one-point, 87
individual, 84, 85
two-point, 88
integer programming, 9, 13, 34, 81
uniform, 89
interview, 164
cutset, 45
interviewer, 163
cutting problem, 22
island, 100
deadline, 16, 20, 22, 29, 174 job,5
decision point, 37, 39, 64 job shop problem, 24
dedicated resource, 19 just-in-time, 20
delay alternative, 38
disjunctive arcs, 80 knapsack packing problem, 28
220 INDEX
knapsack problem, 29 objective, 6, 20, 152, 156, 168, 173

ontogenetic learning, 84, 138
Lamarckian evolution, 84, 138, 144 order swap, 44
latest finish time, 8, 66, 87, 133 order-monotonous schedule, 44
learning effects, 22
local left shift, 43, 51 packing problem, 22
local optimum, 71, 144 pallet loading problem, 28
local search, 72, 105, 122,133, 135, parallel schedule generation
141 scheme, 64, 123
logical nodes, 17 Pareto-optimal, 22
partially renewable resource, 18,
makespan, 6, 11,20, 156, 173 171
market research, 163 Patterson instances, 117, 118, 181,
maximal time lag, 16 182
medical research project, 149 phenotype, 84, 86, 138
metaheuristics, 70, 118; 122 phylogenetic learning, 84
migration, 84, 101 population, 72, 85
minimal time lag, 15 precedence relation, 6, 15, 169
mode, see multiple modes start-start, 16, 162, 169
mode alternative, 37, 39 precedence tree, 35, 47, 59
mode identity, 14, 168 predecessor, 6
mode reduction, 44 preemption, 6, 11, 19
mode-minimal schedule, 43 preprocessing, 42, 130
MRCPSP, see multiple modes priority rule, 66, 87, 93, 103, 122
multi pass, 67, 137, 139 problem-space representation, 75,
multi priority rule methods, 67 116
multi-mode left shift, 43, 136 processing time, 6
multiple modes, 11, 33, 129, 168 ProGen instances, 55, 95, 116, 138,
multiple projects, 22 145, 146, 182
mutation, 72, 85, 90, 92, 94, 105,
135 quality, 21
neighborhood, 71, 72, 107 random key, 74, 91

net present value, 21 random sampling, 68, 86, 116
network, 6, 169 ready time, 16
network complexity, 183 real-world application, 149
neural network, 72 record-to-record travel, 71
non-delay schedule, 65, 102, 123 regret based biased random sam-
nonrenewable resource, 12, 14, 17, pling, 69
43, 131, 171, 172 release date, 16, 174
NP-complete, 14, 131 renewable resource, 6, 19
NP-hard, 10, 14, 33 representation, 73
NPV, see net present value resource factor, 57, 123, 124, 183
INDEX 221
resource investment, 20
resource strength, 57, 123, 124,
146, 183
resource-resource tradeoff, 11
SA, see simulated annealing

sampling, 68, 99, 122
schedule generation scheme, 62,
102, 103, 123
schedule scheme representation,
77,116
selection, 72, 84, 85, 90
proportional, 90
ranking, 90
tournament, 90
self-adaptation, 102, 103, 1'22, 124
semi-active schedule, 43, 51
serial schedule generation scheme,
62, 86, 91, 93, 123, 131
SGS, see schedule generation
scheme
shift vector, 76
simulated annealing, 70, 72, 116
single pass, 67, 122, 136, 139
steepest descent/mildest ascent,
72
stochastic networks, 17
strip packing problem, 30
successor, 6
tabu search, 72, 116

threshold accepting, 71
tight schedule, 43, 137
time window, 7, 10,41, 112
time-cost tradeoff problem, 15
time-resource tradeoff, 11
time-resource tradeoff problem, 14
tracking study, 174
truncated branch-and-bound, 80,
145
TS, see tabu search
weighted tardiness, 20
Lecture Notes in Economics
and Mathematical Systems
For information about Vols. 1-290
please contact your bookseller or Springer-Verlag
Vol. 291: N. Takahashi, Design of Adaptive Organizations. Vol. 310: J. Kacprzyk, M. Fedrizzi (Eds.), Combining Fuzzy
VI, 140 pages. 1987. Imprecision with Probabilistic Uncertainty in Decision
Vol. 292: I. Tchijov, L. Tomaszewicz (Eds.), Input-Output Making. IX, 399 pages. 1988.
Modeling. Proceedings, 1985. VI, 195 pages. 1987. Vol. 311: R. Fare, Fundamentals of Production Theory. IX,
Vol. 293: D. Batten, J. Casti, B. Johansson (Eds.), Economic 163 pages. 1988.
Evolution and Structural Adjustment. Proceedings, 1985. VI, Vol. 312: J. Krishnakumar, Estimation of Simultaneous
382 pages. Equation Models with Error Components Structure. X, 357
Vol. 294: J. Jahn, W. Knabs (Eds.), Recent Advances and pages. 1988.
Historical Development of Vector Optinrization. VII, 405 Vol. 313: W. Jammernegg, Sequential Binary Investment
pages. 1987. Decisions. VI, 156 pages. 1988.
Vol. 295. H. Meister, The Purification Problem for Vol. 314: R. Tietz, W. Albers, R. Selten (Eds.), Bounded
Constrained Games with Incomplete Information. X, 127 Rational Behavior in Experimental Games and Markets. VI,
pages. 1987. 368 pages. 1988.
Vol. 296: A. Borsch-Supan, Econometric Analysis of Vol. 315: I. Orishimo, GJ.D. Hewings, P. Nijkamp (Eds),
Discrete Choice. VIIl, 211 pages. 1987. Information Technology: Social and Spatial Perspectives.
Vol. 297: V. Fedorov, H. Lauter (Eds.), Model-Oriented Data Proceedings 1986. VI, 268 pages. 1988.
Analysis. Proceedings, 1987. VI, 239 pages. 1988. Vol. 316: R.L. Basmann, OJ. Slottje, K. Hayes, J.D. Johnson,
Vol. 298: S.H. Chew, Q. Zheng, Integral Global OJ. Molina, The Generalized Fechner-Thurstone Direct
Optimization. VII. 179 pages. 1988. Utility Function and Some of its Uses. VIII. 159 pages. 1988.
Vol. 299: K. Marti, Descent Directions and Efficient Vol. 317: L. Bianco, A. La Bella (Eds.). Freight Transport
Solutions in Discretely Distributed Stochastic Programs. Planning and Logistics. Proceedings, 1987. X. 568 pages.
X IV, 178 pages. 1988. 1988.
Vol. 300: U. Derigs. Programming in Networks and Graphs. Vol. 318: T. Doup, Simplicial Algorithms on the Simplotope.
XI, 315 pages. 1988. VIII, 262 pages. 1988.
Vol. 301: J. Kacprzyk, M. Roubens (Eds.), Non-Conventional Vol. 319: D.T. Luc, Theory of Vector Optimization. VIII,
Preference Relations in Decision Making. VII, 155 pages. 173 pages. 1989.
1988. Vol. 320: D. van der Wijst, Financial Structure in Small
Vol. 302: H.A. Eiselt, G. Pederzoli (Eds.), Advances in Business. VII, 181 pages. 1989.
Optimization and Control. Proceedings, 1986. VIII, 372 Vol. 321: M. Di Matteo, R.M. Goodwin, A. Vercelli (Eds.),
pages. 1988. Technological and Social Factors in Long Term Fluctuations.
Vol. 303: F.X. Diebold, Empirical Modeling of Exchange Proceedings. IX, 442 pages. 1989.
Rate Dynamics. VII, 143 pages. 1988. Vol. 322: T. Kollintzas (Ed.), The Rational Expectations
Vol. 304: A. Kurzhanski, K. Neumann, D. Pallaschke (Eds.), Equilibrium Inventory Model. XI, 269 pages. 1989.
Optimization, Parallel Processing and Applications. Vol. 323: M.B.M. de Koster, Capacity Oriented Analysis
Proceedings, 1987. VI, 292 pages. 1988. and Design of Production Systems. XII, 245 pages. 1989.
Vol. 305: G.-J.C.Th. van Schijndel, Dynamic Firm and In- Vol. 324: I.M. Bomze, B.M. Ptitscher, Game Theoretical
vestor Behaviour under Progressive Personal Taxation. X, Foundations of Evolutionary Stability. VI, 145 pages. 1989.
215 pages.1988. Vol. 325: P. Ferri, E. Greenberg, The Labor Market and
Vol. 306: Ch. Klein, A Static Microeconomic Model of Pure Business Cycle Theories. X, 183 pages. 1989.
Competition. VIII, 139 pages. 1988. Vol. 326: Ch. Sauer, Alternative Theories of Output, Unem-
Vol. 307: T.K. Dijkstra (Ed.), On Model Uncertainty and its ployment, and Intlation in Germany: 1960-1985. XIII, 206
Statistical Implications. VII, 138 pages. 1988. pages. 1989.
Vol. 308: J.R. Daduna, A. Wren (Eds.), Computer-Aided Vol. 327: M. Tawada, Production Structure and Internatio-
Transit Scheduling. VIII, 339 pages. 1988. nal Trade. V, 132 pages. 1989.
Vol. 309: G. Ricci, K. Velupillai (Eds.), Growth Cycles and Vol. 328: W. GOth, B. Knlkofen. Unique Solutions for
Multisectoral Economics: The Goodwin Tradition. III, 126 Strategic Games. VII, 200 pages. 1989.
pages. 1988.
Vol. 329: G. Tillmann, Equity, Incentives, and Taxation. VI, Xli, 229 pages. 1991.
132 pages. 1989. Vol. 353: G. Ricci (Ed.), Decision Processes in Economics.
Vol. 330: P.M. Kort, Optimal Dynamic Investment Policies Proceedings, 1989. lll, 209 pages 1991.
ofa Value Maximizing Finn. VII, 185 pages. 1989. Vol. 354: M. Ivaldi, A Structural Analysis of Expectation
Vol. 331: A. Lewandowski, A.P. Wierzbicki (Eds.), Aspira- Fonnation. X[[, 230 pages. 1991.
tion Based Decision Support Systems. X, 400 pages. 1989. Vol. 355: M. Salomon. Deterministic Lotsizing Models for
Vol. 332: T.R. Gulledge, Jr., L.A. Litteral (Eds.), Cost Ana- Production Planning. Vll, 158 pages. 1991.
lysis Applications of Economics and Operations Research. Vol. 356: P. Korhonen, A. Lewandowski, J . Wallenius
Proceedings. VII, 422 pages. 1989. (Eds.), Multiple Criteria Decision Support. Proceedings,
Vol. 333: N. Dellaert, Production to Order. VII, 158 pages. 1989. XII, 393 pages. 1991.
1989. Vol. 357: P. Zornig, Degeneracy Graphs and Simplex
Vol. 334: H.-W. Lorenz, Nonlinear Dynamical Economics Cycling. XV, 194 pages. 1991.
and Chaotic Motion. XI, 248 pages. 1989. Vol. 358: P. Knottnerus, Linear Models with Correlated Dis-
Vol. 335: A.G. Lockett, G. Islei (Eds.), Improving Decision turbances. VIII, 196 pages. ] 991.
Making in Organisations. Proceedings. IX, 606 pages. 1989. Vol. 359: E. deJong, Exchange Rate Determination andOp-
Vol. 336: T. Puu, Nonlinear Economic Dynamics. VII, 119 timal Economic Policy Under Various Exchange Rate Re-
pages. 1989. gimes. VII, 270 pages. 1991.
Vol. 337: A. Lewandowski, I. Stanchev (Eds.), Methodology Vol. 360: P. Stalder, Regime Translations, Spillovers and
and Software for Interactive Decision Support. VIII, 309 Buffer Stocks. VI, 193 pages. 1991.
pages. 1989. Vol. 361: C. F. Daganzo, Logistics Systems Analysis. X,
Vol. 338: J.K. Ho, R.P. Sundarraj, DECOMP: An Imple- 32] pages. 1991.
mentation of Dantzig-Wolfe Decomposition for Linear Vol. 362: F. Gehrels, Essays in Macroeconomics of an
Programming. VI, 206 pages. Open Economy. VII, 183 pages. ] 991.
Vol. 339: J. Terceiro Lomba, Estimation of Dynamic Vol. 363: C. Puppe, Distorted Probabilities and Choice under
Econometric Models with Errors in Variables. VIII, 116 Risk. VIII, 100 pages. 1991
pages. 1990.
Vol. 364: B. Horvath, Are Policy Variables Exogenous? XII,
Vol. 340: T. Vasko, R. Ayres, L. Fontvieille (Eds.), Life 162 pages. 1991.
Cycles and Long Waves. XIV, 293 pages. 1990.
Vol. 365: G. A. Heuer, U. Leopold-Wildburger. Balanced
Vol. 341: G.R. Uhlich, Descriptive Theories of Bargaining. Silverman Games on General Discrete Sets. V, 140 pages.
IX, 165 pages. 1990. 1991.
Vol. 342: K. Okuguchi, F. Szidarovszky, The Theory of Vol. 366: J. Gruber (Ed.), Econometric Decision Models.
Oligopoly with Multi-Product Firms. V, 167 pages. 1990. Proceedings, 1989. VllI, 636 pages. 199].
Vol. 343: C. Chiarella, The Elements of a Nonlinear Theory Vol. 367: M. Grauer, D. B. Pressmar (Eds.), Paralle]
of Economic Dynamics. IX, 149 pages. 1990. Computing and Mathematical Optimization. Proceedings. V,
Vol. 344: K. Neumann, Stochastic Project Networks. XI, 208 pages. 1991.
237 pages. 1990. Vol. 368: M. Fedrizzi, J. Kacprzyk, M. Raubens (Eds.),
Vol. 345: A. Cambini, E. Castagnoli, L. Martein, P Interactive Fuzzy Optimization. VII, 216 pages. 1991.
Mazzoleni, S. Schaible (Eds.), Generalized Convexity and Vol. 369: R. Koblo, The Visible Hand. VIII, 131 pages. 1991.
Fractional Programming with Economic Applications.
Proceedings, 1988. V[[, 361 pages. 1990. Vol. 370: M. J. Beckmann, M. N. Gopalan, R. Subramanian
(Eds.), Stochastic Processes and their Applications.
Vol. 346: R. von Randow (Ed.), Integer Programming and Proceedings, 1990. XLI, 292 pages. 1991.
Related Areas. A Classified Bibliography 1984-1987. XIII,
514 pages. 1990. Vol. 371: A. Schmutzler, Flexibility and Adjustment to In-
formation in Sequential Decision Problems. VllI, 198 pages.
Vol. 347: D. Rios Insua, Sensitivity Analysis in Multi- 1991.
objective Decision Making. XI, 193 pages. 1990.
Vol. 372: J. Esteban, The Social Viability of Money. X, 202
Vol. 348: H. Stormer, Binary Functions and their pages. ] 991.
Applications. VIII, 151 pages. 1990.
Vol. 373: A. Billot, Economic Theory of Fuzzy Equilibria.
Vol. 349: G.A. Prann, Dynamic Modelling of Stochastic XIII, 164 pages. 1992.
Demand for Manufacturing Employment. VI, 158 pages.
1990. Vol. 374: G. Pflug, U. Dieter (Eds.), Simulation and Optimi-
zation. Proceedings, 1990. X, 162 pages. 1992.
Vol. 350: W.-B. Zhang, Economic Dynamics. X, 232 pages.
1990. Vol. 375: S.-J. Chen, Ch.-L. Hwang, Fuzzy Multiple Attri-
bute Decision Making. XII, 536 pages. 1992.
Vol. 351: A. Lewandowski, V. Volkovich (Eds.),
Multiobjective Problems of Mathematical Programming. Vol. 376: K.-H. Hickel, G. Rothe, W. Sendler (Eds.),
Proceedings, 1988. V[[, 315 pages. 1991. Bootstrapping and Related Techniques. Proceedings, 1990.
VIII, 247 pages. 1992.
Vol. 352: O. van Hilten, Optimal Firm Behaviour in the
Context of Technological Progress and a Business Cycle.
Vol. 377: A. Villar, Operator Theorems with Applications Vol. 401: K. Mosler, M. Scarsini. Stochastic Orders and
to Distributive Problems and Equilibrium Models. XVI, 160 Applications. V. 379 pages. 1993.
pages. 1992. Vol. 402: A. van den Elzen, Adjustment Processes for Ex-
Vol. 378: W. Krabs, J. Zowe (Eds.), Modern Methods of change Economies and Noncooperative Games. VII, 146
Optimization. Proceedings, 1990. VIII, 348 pages. 1992. pages. 1993.
Vol. 379: K. Marti (Ed.), Stochastic Optimization. Vol. 403: G. Brennscheidt, Predictive Behavior. VI, 227
Proceedings, 1990. VII, 182 pages. 1992. pages. 1993.
Vol. 380: J. Odelstad, Invariance and Structural Dependence. Vol. 404: Y.-J. Lai. Ch.-L. Hwang. Fuzzy Multiple Objective
XII, 245 pages. 1992. Decision Making. XIV, 475 pages. 1994.
Vol. 381: C. Giannini, Topics in Structural VAR Vol. 405: S. Komlasi. T. Rapcsak, S. Schaible (Eds.).
Econometrics. XI, 131 pages. 1992. Generalized Convexity. Proceedings. 1992. VIIl. 404 pages.
Vol. 382: W. Oettli, D. Pallaschke (Eds.), Advances in 1994.
Optimization. Proceedings, 1991. X, 527 pages. 1992. Vol. 406: N. M. Hung, N. Y. Quyen, Dynamic Timing
Vol. 383: J. Vartiainen, Capital Accumulation in a Decisions Under Uncertainty. X, 194 pages. 1994.
Corporatist Economy. VII, 177 pages. 1992. Vol. 407: M. Ooms, Empirical Vector Autoregressive
Vol. 384: A. Martina, Lectures on the Economic Theory of Modeling. XIII, 380 pages. 1994.
Taxation. XII, 313 pages. 1992. Vol. 408: K. Haase, LOlsizing and Scheduling for Production
Vol. 385: J. Gardeazabal, M. Regulez, The Monetary Model Planning. VIII, 118 pages. 1994.
of Exchange Rates and Cointegration. X, 194 pages. 1992. Vol. 409: A. Sprecher. Resource-Constrained Project
Vol. 386: M. Desrochers, J.-M. Rousseau (Eds.), Compu- Scheduling. XlI. 142 pages. 1994.
ter-Aided Transit Scheduling. Proceedings, 1990. XIII, 432 Vol. 410: R. Winkelmann. Count Data Models. XI, 213
pages. 1992. pages. 1994.
Vol. 387: W. Gaertner, M. Klemisch-Ahlert, Social Choice Vol. 411: S. Dauzere-Peres, J.-B. Lasserre, An Integrated
and Bargaining Perspectives on Distributive Justice. VlII, Approach in Production Planning and Scheduling. XVI, 137
131 pages. 1992. pages. I 994.
Vol. 388: D. Bartmann, M. J. Beckmann, Inventory Control. Vol. 412: B. Kuon. Two-Person Bargaining Experiments
XV, 252 pages. 1992. with Incomplete Information. IX, 293 pages. 1994.
Vol. 389: B. Dutta. D. Mookherjee, T. Parthasarathy, T. Vol. 413: R. Fiorito (Ed.), Inventory, Business Cycles and
Raghavan, D. Ray, S. Tijs (Eds.), Game Theory and Monetary Transmission. VI. 287 pages. 1994.
Economic Applications. Proceedings, 1990. IX, 454 pages. Vol. 414: Y. Crama, A. Oerlemans, F. Spieksma, Production
1992. Planning in Automated Manufacturing. X, 210 pages. 1994.
Vol. 390: G. Sorger, Minimum Impatience Theorem for Vol. 415: P. C. Nicola, Imperfect General Equilibrium. XI,
Recursive Economic Models. X, 162 pages. 1992. 167 pages. 1994.
Vol. 391: C. Keser, Experimental Duopoly Markets with Vol. 416: H. S. J. Cesar, Control and Game Models of the
Demand Inertia. X, ISO pages. 1992. Greenhouse Effect. Xl, 225 pages. 1994.
Vol. 392: K. Frauendorfer, Stochastic Two-Stage Vol. 417: B. Ran, D. E. Boyce, Dynamic Urban Transpor-
Programming. VIII, 228 pages. 1992. tation Network Models. XV, 391 pages. 1994.
Vol. 393: B. Lucke, Price Stabilization on World Agricultural Vol. 418: P. Bogetoft, Non-Cooperative Planning Theory.
Markets. XI, 274 pages. 1992. XI, 309 pages. 1994.
Vol. 394: Y.-J. Lai, c.-L. Hwang, Fuzzy Mathematical Vol. 419: T. Maruyama, W. Takahashi (Eds.), Nonlinear and
Programming. XlII, 301 pages. 1992. Convex Analysis in Economic Theory. VIII. 306 pages. 1995.
Vol. 395: G. Haag, U. Mueller, K. G. Troitzsch (Eds.), Vol. 420: M. Peeters, Time-To-Build. Interrelated Invest-
Economic Evolution and Demographic Change. XVI, 409 ment and Labour Demand Modelling. With Applications to
pages. 1992. Six OECD Countries. IX, 204 pages. 1995.
Vol. 396: R. V. V. Vidal (Ed.). Applied Simulated Annealing. Vol. 421: C. Dang, Triangulations and Simplicial Methods.
VIII. 358 pages. 1992. IX, 196 pages. 1995.
Vol. 397: J. Wessels. A. P. Wierzbicki (Eds.), User-Oriented Vol. 422: D. S. Bridges. G. B. Mehta, Representations of
Methodology and Techniques of Decision Analysis and Sup- Preference Orderings. X, 165 pages. 1995.
port. Proceedi ngs, 1991. XII, 295 pages. 1993.
Vol. 423: K. Marti. P. Kall (Eds.), Stochastic Programming.
Vol. 398: J.-P. Urbain, Exogeneity in Error Correction Mo- Numerical Techniques and Engineering Applications. VIII,
dels. XI, 189 pages. 1993. 351 pages. 1995.
Vol. 399: F. Gori, L. Geronazzo, M. Galeotti (Eds.). Non- Vol. 424: G. A. Heuer, U. Leopold-Wildburger. Silverman's
linear Dynamics in Economics and Social Sciences. Game. X, 283 pages. 1995.
Proceedings, 1991. VIII, 367 pages. 1993.
Vol. 425: 1. Kohlas, P.-A. Monney, A Mathematical Theory
Vol. 400: H. Tanizaki, Nonlinear Filters. XII, 203 pages. of Hints. XlII, 419 pages, 1995.
1993.
Vol. 426: B. Finkenstadt, Nonlinear Dynamics in Eco-
nomics. IX. 156 pages. 1995.
VoL 427: F. W. van Tongeren, Microsimulation Modelling Vol. 454: H.-M. Krolzig. Markov-Switching Vector Auto-
of the Corporate Finn. XVII, 275 pages. 1995. regressions. XIV, 358 pages. 1997.
VoL 428: A. A. Powell, Ch. W. Murphy, Inside a Modern Vol. 455: R. Caballero, F. Ruiz, R. E. Steuer (Eds.), Advances
Macroeconometric Model. XVIII, 424 pages. 1995. in Multiple Objective and Goal Programming. VIII, 391
VoL 429: R. Durier, C. Michelot, Recent Developments in pages. 1997.
Optimization. VIII, 356 pages. 1995. Vol. 456: R. Conte, R. Hegselmann, P. Terna (Eds.). Simu-
VoL 430: J. R. Daduna, I. Branco, J. M. Pinto Paixao (Eds.), lating Social Phenomena. VIII, 536 pages. 1997.
Computer-Aided Transit Scheduling. XIV, 374 pages. 1995. Vol. 457: C. Hsu, Volume and the Nonlinear Dynamics of
VoL 431: A. Aulin, Causal and Stochastic Elements in Busi- Stock Returns. Vlll, 133 pages. 1998.
ness Cycles. XI, 116 pages. 1996. Vol. 458: K. Marti, P. Kall (Eds.). Stochastic Programming
VoL 432: M. Tamiz (Ed.), Multi-Objective Programming Methods and Technical Applications. X. 437 pages. 1998.
and Goal Programming. VI, 359 pages. 1996. VoL 459: H. K. Ryu, D. J. Slot0e, Measuring Trends in U.S.
VoL 433: J. Menon, Exchange Rates and Prices. XIV, 313 Income Inequality. XI, 195 pages. 1998.
pages. 1996. Vol. 460: B. Fleischmann, J. A. E. E. van Nunen. M. G.
Vol. 434: M. W. J. Blok, Dynamic Models afthe Firm. VII, Speranza, P. Stahly, Advances in Distribution Logistic. XI,
193 pages. 1996. 535 pages. 1998.
Vol. 435: L. Chen, Interest Rate Dynamics, Derivatives Vol. 461: U. Schmidt, Axiomatic Utility Theory under Risk.
Pricing, and Risk Management. XII, 149 pages. 1996. XV, 201 pages. 1998.
Vol. 436: M. Klemisch-Ahlert, Bargaining in Economic and Vol. 462: L. von Auer, Dynamic Preferences, Choice
Ethical Environments. IX, 155 pages. 1996. Mechanisms, and Welfare. XII, 226 pages. 1998.
Vol. 437: C. Jordan, Batching and Scheduling. IX, 178 pages. Vol. 463: G. Abraham-Frois (Ed.), Non-Linear Dynamics
1996. and Endogenous Cycles. VI, 204 pages. 1998.
VoL 438: A. Villar, General Equilibrium with Increasing Vol. 464: A. Aulin, The Impact of Science on Economic
Returns. XIII, 164 pages. 1996. Growth and its Cycles. IX, 204 pages. 1998.
VoL 439: M. Zenner, Learning to Become Rational. VII, Vol. 465: T. J. Stewart, R. C. vall den Honert (Eds. 1. Trends
20 I pages. 1996. in Multicriteria Decision Making. X. 448 pages. 1998.
VoL 440: W. Ryll,Litigation and Settlement in a Game with Vol. 466: A. Sadrieh, The Alternating Double Auction
Incomplete Information. VIII, 174 pages. 1996. Market. VII, 350 pages. 1998.
Vol. 441: H. Dawid, Adaptive Learning by Genetic Vol. 467: H. Hennig-Schmidt. Bargaining in a Video Ex-
Algorithms. IX, 166 pages. I 996. periment. Determinants of Boundedly Rational Behavior.
XII, 221 pages. 1999.
Vol. 442: L. Corchon, Theories of Imperfectly Competitive
Markets. XIII, 163 pages. 1996. Vol. 468: A. Ziegler, A Game Theory Analysis of Options.
XIV, 145 pages. 1999.
Vol. 443: G. Lang, On Overlapping Generations Models with
Productive Capital. X, 98 pages. 1996. Vol. 469: M. P. Vogel, Environmental Kuznets Curves. XIII,
197 pages. 1999.
Vol. 444: S. J0rgensen, G. Zaccour (Eds.), Dynamic
Competitive Analysis in Marketing. X, 285 pages. 1996. Vol. 470: M. Ammann, Pricing Derivative Credit Risk. XII,
228 pages. 1999.
Vol. 445: A. H. Christer, S. Osaki, L. C. Thomas (Eds.),
Stochastic Modelling in Innovative Manufactoring. X, 361 Vol. 471: N. H. M. Wilson (Ed.), Computer-Aided Transit
pages. 1997. Scheduling. XI, 444 pages. 1999.
Vol. 446: G. Dhaene, Encompassing. X. 160 pages. 1997. Vol. 472: J.-R. Tyran, Money Illusion and Strategic
Complementarity as Causes of Monetary Non-Neutrality.
Vol. 447: A. Artale, Rings in Auctions. X, 172 pages. 1997. X, 228 pages. 1999.
Vol. 448: G. Fandel, T. Gal (Eds.), Multiple Criteria Decision Vol. 473: S. Helber, Performance Analysis of Flow Lines
Making. XII, 678 pages. 1997. with Non-Linear Flow of Material. IX. 280 pages. 1999.
Vol. 449: F. Fang, M. Sanglier (Eds.), Complexity and Self- Vol. 474: U. Schwalbe, The Core of Economies with
Organization in Social and Economic Systems. IX, 317 Asymmetric Information. IX, 141 pages. 1999.
pages, 1997.
Vol. 475: L. Kaas, Dynamic Macroelectronics with Imperfect
Vol. 450: P. M. Pardalos, D. W. Hearn, W. W. Hager, (Eds.), Competition. XI, 155 pages. 1999.
Network Optimization. VIII, 485 pages, 1997.
Vol. 476: R. Demel, Fiscal Policy, Public Debt and the
Vol. 451: M. Salge, Rational Bubbles. Theoretical Basis, Term Structure of Interest Rates. X, 279 pages. 1999.
Economic Relevance, and Empirical Evidence with a Special
Emphasis on the German Stock Market.lX, 265 pages. 1997. Vol. 477: M. Thera, R. Tichatschke (Eds.), Ill-posed
Variational Problems and Regularization Techniques. VIII,
Vol. 452: P. Gritzmann, R. Horst, E. Sachs, R. Tichatschke 274 pages. 1999.
(Eds.), Recent Advances in Optimization. VIII, 379 pages.
1997. Vol. 478: S. Hartmann, Project Scheduling under Limited
Resources. XII, 221 pages. 1999.
Vol. 453: A. S. Tangian, J. Gruber (Eds.), Constructing
Scalar-Valued Objective Functions. VIJI, 298 pages. 1997. Vol. 479: L. v. Thadden, Money, Inflation, and Capital
Formation. IX, 192 pages. 1999.

Test Instances: Appendix A

Uploaded by

Copyright:

Available Formats

Test Instances: Appendix A

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Test Instances: Appendix A

Uploaded by

Copyright:

Available Formats

Appendix A

A.I Patterson Instance Set

A.2 Instance Sets Generated by ProGen

A.2.1 Single-Mode Instance Sets

Parameter min max

Table A.l: ProGen single-mode instances: Fixed parameter levels

Table A.2: ProGen single-mode instances: Variable parameter levels

A.2.2 Multi-Mode Instance Sets

Parameter min max

Table A.3: ProGen multi-mode instances: Fixed parameter levels

In order to obtain the multi-mode instance sets including nonrenewable

Table A.4: ProGen multi-mode instances: Variable parameter levels

Solving the MRCPSP using

In what follows we show how the multi-mode resource-constrained project

B.l AMPL-Formulation of the MRCPSP

MRCPSP symbol symbol in AMPL

Table B.1: MRCPSP symbols in AMPL formulation

option solver cplex;

param RR {KR} integer;

param EF {O .. J+l} integer;

var x {j in O.. J+l, 1 .. M[j], EF[j] .. LF[j]} binary;

subject to JobModeCompletion {j in O.. J+l}:

subject to RenewableResources {k in KR, t in 1 .. T}:

subject to NonrenewableResources {k in KN}:

# READ DATA FROM FILE

B.2 AMPL-Data File for the MRCPSP

[1) M. K. Agrawal, S. E. Elmaghraby, and W. S. Herroelen. DAGEN: A generator

[11] A. B. Badiru. Project Management in Manufacturing and High Technology

[26] P. Brucker, A. Drexl, R. Mohring, K. Neumann, and E. Pesch. Resource-

[39] N. Dayanand and R. Padman. On modelling payments in projects. Journal

[42] B. de Reyck and W. S. Herroelen. Assembly line balancing by resource-

[73] S. E. Elmaghraby. Resource allocation via dynamic programming in activity

(90) S. Hartmann. Project scheduling with multiple modes: A genetic algorithm.

[106] O. Icmeli, S. S. Erenguc, and C. J. Zappe. Project scheduling problems:

[120] R. Kolisch. Project scheduling under resource constraints - Efficient heuristics

[150] K. S. Naphade, S. D. Wu, and R. H. Storer. Problem space search algorithms

[180) C. Schwindt. ProGen/max: A new problem generator for different resource-

[195] J. P. Stinson, E. W. Davis, and B. M. Khumawala. Multiple resource-

[211] T. Williams. A classified bibliography of recent research relating to project

e.g. for example

FFS first fit strategy

LCBA local constraint based analysis (priority rule)

MIRCPSP mode identity resource-constrained project scheduling prob-

NBRS normalized biased random sampling

RAND random (priority rule)

RCPSP resource-constrained project scheduling problem

WCS worst case slack (priority rule)

CHI children produced in a genetic algorithm

extension alternative at level 9

f(·) fitness function

9 level in branch-and-bound algorithm or schedule generation

I individual in genetic algorithm

J number of non-dummy activities

set of activities including summy source and sink

set of renewable resources

nonrenewable resource units exceeding the capacities in

number ,of modes of activity j

Pj processing time of activity j