Resource allocation in project management

GOR ■ Publications

Managing Editor Editors

Kolisch, Rainer Burkard, Rainer E.

Fleischmann, Bernhard

Inderfurth, Karl

Möhring, Rolf H.

Voss, Stefan

Titles in the Series

H.-O. Günther and P. v. Beek (Eds.)

Advanced Planning and Scheduling

Solutions in Process Industry

VI, 426 pages. 2003. ISBN 3-540-00222-7

J. Schönberger

Operational Freight Carrier Planning

IX, 164 pages. 2005. ISBN 3-540-25318-1

Christoph Schwindt

Resource Allocation

in Project Management

With 13 Figures

and 12 Tables

123

Professor Dr. Christoph Schwindt

Institut für Wirtschaftswissenschaft

TU Clausthal

Julius-Albert-Straße 2

38678 Clausthal-Zellerfeld

E-mail: [email protected]

Library of Congress Control Number: 2005926096

ISBN 3-540-25410-2 Springer Berlin Heidelberg New York

This work is subject to copyright.All rights are reserved,whether the whole or part of the material

is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation,

broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Dupli￾cation of this publication or parts thereof is permitted only under the provisions of the German

Copyright Law of September 9, 1965, in its current version, and permission for use must always

be obtained from Springer-Verlag.Violations are liable for prosecution under the German Copy￾right Law.

Springer is a part of Springer Science+Business Media

springeronline.com

© Springer-Verlag Berlin Heidelberg 2005

Printed in Germany

The use of general descriptive names, registered names, trademarks, etc. in this publication does

not imply, even in the absence of a specific statement, that such names are exempt from the

relevant protective laws and regulations and therefore free for general use.

Cover design: Erich Kirchner

Production: Helmut Petri

Printing: Strauss Offsetdruck

SPIN 11409960 Printed on acid-free paper – 42/3153 – 5 4 3 2 1 0

Die Seele jeder Ordnung ist ein grofier Papierkorb.

Kurt Tucholsky, Schnipsel

Preface

This monograph grew out of my research in the ficld of resourcc-constraincd

project scheduling conducted from 1995 to 2004 during my work as teaching

assistant and assistant professor at the Institute for Economic Theory and

Operations Research of thc Univcrsity of Karlsruhe. The aim of the book is

to givc an introduction to quantitative concepts and methods for resource

allocation in project managcmcnt with an cmphasis on an ordcr-theoretic

framework allowing for a unifying treatment of various problem types. In order

to make the work accessible for general readers, the basic concepts nccded arc

rcviewed in introductory scctions of the book.

Many pcople have contributed to the outcome of this research. First and

foremost, I would like to express my deep appreciation to my supervisor Pro￾fessor Klaus Ncumann, who introduced me to the field and the community

of project schcduling. I have greatly benefited from his comprehensive scien￾tific knowlcdgc and expertise, his continuous encouragement, and his support.

During all these years, his departmcnt has bcen a stimulating and attractive

place for doing research and teaching in Operations Rcsearch.

Moreover, I would like to thank my formcr collcagucs for many fruitful

discussions on various research topics and their continuing interest in my

work. A major part of my rcsearch has been done in collaboration with the

colleagues of the Karlsruhe project scheduling group, Birger Franck, Cord￾Ulrich Fundeling, Karsten Gentner, Steffen Hagmaycr, Dr. Thomas Hartung,

Dr. Roland Heilmann, Christoph Mellentien, Dr. Hartwig Nubel, Dr. Thomas

Selle, PD Dr. Norbert Trautmann, and Professor Jiirgcn Zimmcrmann. Our

work has been greatly influenccd by the activities of a research unit on proj￾ect scheduling funded by the Deutsclle Forschungsgemcinschaft and involving

colleagucs from the universities of Bcrlin (Profcssor Rolf Mijhring), Bonn (Pro￾fessor Erwin Pcsch), Karlsruhe (Professor Klaus Ncumann), Kicl (Professor

Andreas Drexl), and Osnabriick (Professor Peter Brucker). Numerous joint

workshops on project scheduling and the "cooperative-competitive" spirit in

this group havc been a great incentive to work even harder.

viii Preface

Finally, I grateful acknowledge the help of several peoplc in preparing the

manuscript of this monograph: Klaus Neumann for many valuable comments

on different versions of the manuscript, Gerhard Grill for carefully proof￾reading and improving the English wording of the manuscript, Frederik Stork

for pointing me to state-of-the-art contributions in convex programming, and

Jiirgcn Zimmermann for making experimental results on rcsourcc levelling

problems availablc to me. Of course thc faults and dcficicncics rcmaining are

entircly my own.

Clausthal-Zellerfeld, February 2005 Christoph Schwindt

Contents

Introduction ................................................... 1

1 Models and Basic Concepts ................................ 7

1.1 Tcrnporal Constraints .................................... 7

1.1.1 Time-Feasible Schedules ............................ 7

1.1.2 Project Networks .................................. 9

1.1.3 Temporal Scheduling Computations ................. 11

1.2 Renewablc-Resource Constraints .......................... 16

1.2.1 Rcsourcc-Fcasiblc Schedules ........................ 16

1.2.2 Forbidden Sets and Delaying Alternatives ............ 19

1.2.3 Breaking up Forbidden Sets ........................ 21

1.2.4 Consistency Tests ................................. 23

1.3 Cumulative-Resource Constraints .......................... 28

1.3.1 Resource-Feasible Schedules ........................ 30

1.3.2 Forbidden Sets and Delaying Alternativcs ............ 32

1.3.3 Brcaking up Forbidden Sets ........................ 35

1.3.4 Consistency Tests ................................. 36

2 Relations. Schedules. and Objective Functions ............. 39

2.1 Resource Constraints and Feasible Relations ................ 39

2.1.1 Renewablc-Resource Constraints .................... 40

2.1.2 Cumulative-Resource Constraints .................... 46

2.2 A Classification of Schcdulcs .............................. 52

2.2.1 Global and Local Extreme Points of the Feasible Region 52

2.2.2 Vcrtices of Relation Polytopes ...................... 53

2.3 Objectivc Functions ..................................... 55

2.3.1 Regular and Convexifiable Objective Functions ........ 56

2.3.2 Locally Regular and Locally Concave Objective

Functions ........................................ 60

2.3.3 Preorder-Decreasing Objective Functions ............. 64

x Contents

3 Relaxation-Based Algorithms .............................. 65

3.1 Regular Objcctivc Functions .............................. 66

3.1.1 Enumeration Scheme .............................. 66

3.1.2 Solving the Relaxations ............................ 69

3.1.3 Branch-and-Bound ................................ 72

3.1.4 Additional Notes and References .................... 76

3.2 Corwexifiablc Objective Functions ......................... 82

3.2.1 Enumeration Scheme .............................. 83

3.2.2 Solving thc Rclaxations: Thc Primal Approach ........ 85

3.2.3 Solving the Relaxations: The Dual Approach .......... 94

3.2.4 Branch-and-Bound ................................ 97

3.2.5 Additional Notes and References .................... 99

4 Constructive Algorithms ................................... 107

4.1 Schedule-Generation Schcme .............................. 109

4.2 Local Scarch ............................................ 115

4.3 Additional Notcs and Rcfererlccs .......................... 118

5 Supplements.. ............................................. 123

5.1 Break Calendars ......................................... 124

5.2 Scquencc-Dcpcndent Changeover Times .................... 128

5.3 Alternative Execution Modes for Activities ................. 131

5.4 Continuous Cumulative Resources ......................... 135

6 Applications ............................................... 141

6.1 Make-to-Order Production Scheduling ...................... 142

6.2 Small-Batch Production Planning in Manufacturing Industries 147

6.3 Production Scheduling in thc Proccss Industrics ............. 149

6.4 Evaluation of Investment Projects ......................... 155

6.5 Coping with Uncertainty ................................. 160

Conclusions .................................................... 165

References ..................................................... 167

List of Symbols ................................................ 181

Index .......................................................... 185

Introduction

Project management and resource allocation. A project is a major

one-time undertaking dedicated to some well-defined objective and involving

considerable money, personnel, and equipment. It is usually initiated cithcr by

some need of the parent organization or by a customer request. The life cycle

of a project can bc structurcd into five consecutivc phases involving specific

managerial tasks (cf. Klcin 2000, Section 1.2). Starting with some proposal,

sevcral preliminary studies such as a feasibility study, an economic analysis, or

a risk analysis are conducted in the project conception phase in order to decide

whcthcr or not a corresponding project will be performed. In the project defi￾nition phase, the objectives of the project are formulated, the type of project

organization is selected, resourccs are assigned to the project, and different

tasks with associated milestones are identified. Subsequently, the project plan￾ning phase at first decomposes each task into precedence-relatcd activities by

means of a structural analysis of the project. The time and resource estima￾tions then provide the duration and resource requirements for each activity as

well as temporal constraints between activities that are connected by prece￾dence relationships. The result of the structural analysis and the time and

resource estimations is the representation of the project as a network mod￾elling the activitics and thc prescribed prccedence relationships among them.

Next, the temporal scheduling of the project provides the earliest and latest

start times as well as thc slack times of the activitics, limitations with respect

to resourcc availability yet being disregarded. The last and most complcx is￾sue of project planning consists in allocating the scarcc resources over time

to the execution of the activities. During the project execution phase, the im￾plementation of the project is controlled by monitoring the project progress

against the schedule which has been established in thc projcct planning phase.

In case of significant deviations from schedulc, the resource allocation has to

be performed again. Thc final project termination phase evaluates and docu￾ments the project after its complction to facilitate thc managcment of futurc

projects.

Introduction

Each phase in the project Ufe cycle requires specific project management

techniques. Several recent textbooks on project management are devoted to

the managerial and behavioral aspects of project conception, project defini￾tion, project planning, project execution, and project termination (see, e.g.,

Lewis 1998, Pinto 1998, Turner 1999, Keeling 2000, Meredith and Mantel

2002, or Kerzner 2003). This book is concerned with quantitative methods

for the project planning phase and, more specifically, with the problem of

optimally allocating resources over time.

Project planning within the life cycle of a project

The complexity of resource allocation arises from the interaction between

the activities of a project by explicit and implicit dependencies, which may

be subject to some degree of uncertainty. Explicit dependencies are given by

the precedence relationships between activities emanating from technological

or organizational requirements. In the course of time estimation, those de￾pendencies are transformed into temporal constraints between activities. The

scarcity of the resources used establishes an implicit dependency between ac￾tivities, which can be formulated as resource constraints referring to sets of

activities competing for the same resources or in terms of an objective function

penalizing excessive resource requirements. The resource allocation problem

consists in assigning time intervals to the execution of the activities while tak￾ing into account the prescribed temporal constraints and resource scarcity. If

Introduction 3

resource constraints are given, we also speak of a resource-constrained proj￾ect scheduling problem. We distinguish bctwcen two subproblems: sequenczng

and tzme-constramed project schedulzng. The limited availability of resources

necessitates the definition of additional preccdence relationships between ac￾tivitics when performing tlie resource allocation task. Again, those prcccdence

relationships can be expressed in tlie form of temporal constraints. In contrast

to the structural analysis, howevcr, the precedence relationships to bc intro￾duccd arc subjcct to decision. This sequencing problem forms the core problem

of project planning. Time-constraincd project schcduling is concerned with

computing the project schedule such that all temporal constraints - prcde￾tcrmined by the structural analysis or arising from sequencing - are observed

arid some objective function reflecting the managerial goal of the project is

optimized. In the resource allocation methods developed in this book, scquenc￾ing and time-constrained project scheduling will be performed jointly in an

iterative manner.

If activitics can be performed in altcrnative exccution modes that differ in

durations and rcsourcc rcquircments, the selcction of an appropriate execution

mode for each activity may be included into the resource allocation problem.

In that case, the time and resource estimations providc thc scts of alternative

cxecution modes, and solving the mode assignment problem constitutes the

first stcp of resource allocation. Depending on whcthcr thc sets of execution

modes are countable or uncountable, we speak of a discrete or a continuous

mode assignment problem. A resource allocation problem that comprises a

modc assignment problcm is termed a multi-mode rcsourcc allocation prob￾lem.

Historical perspective and state of the art. Algorithms for resource

allocation in project management date back to the 1960s, see Davis (1966),

Laue (1968), Herroelen (1972), and Davis (1973) for ovcrvicws. The early work

was concerned with three types of resource allocation problcms: the time-cost

tradeoff problem, the projcct duration problem, and the resource lcvelling

problem. For all threc problem typcs it is assumed that a strict order in the

set of activitics specifies completion-to-start prcccdencc constraints among

activitics. The tzme-cost tradeoff problem is a multi-mode resource allocation

problcm which arises when certain activity durations can be reduced at the ex￾pense of higher direct cost. The project budget is then regarded as the resource

to bc allocated. If for each activity the cost incurred is a convex function in

the activity duration, thc continuous mode assignmcnt problcm that consists

in computing all combinations of project duration and corresponding least￾cost schcdule can be determined by applying network flow techniqucs (see

Kelley 1961). A survey of multi-modc resource allocation problcms including

diffcrcnt types of tradeoffs between the durations, resource requirements, and

direct costs of activity exccution modes can bc found in Domschkc and Drcxl

(1991). The project duratzon problem consists in schcduling the activities of

a project subject to the limited availability of renewable resources like man￾power or machinery such that all activities are completed within a mininium

4 Introduction

amount of time. Early approaches to solving thc project duration problem in￾cludc mixed-integer linear programming formulations (see, c.g., Wicst 1963)

and priority-rule methods (cf. Kelley 1963, Vcrhincs 1963, and Moder and

Phillips 1964). The objective when dealing with a resource leuellzng problem

is to "smooth" the utilization of renewable rcsources over timc as much as

possible, within a prcscribcd maximum projcct duration. In some cases, a de￾sired threshold limit on thc rcsourcc availability is given, and resources are to

bc lcvcllcd around this targct. In other cases, one strives at minimizing the

variancc of resource utilization over time or minimizing the absolute magni￾tudc of fluctuation in the resource profiles. The first proccdurcs for resource

levelling offered by Burgcss and Killebrew (1962) and Levy et al. (1963) wcrc

bascd on sequentially moving in tirnc slack activities.

In the following years, a great deal of effort has bccn dcvotcd to heuristic

and exact algorithms for thc projcct duration problem. In the 1990s, projcct

planning methods gained increasing importance from their applicability to

schcduling problems arising beyond thc area of proper projcct management,

for cxample, in production planning, time-tabling, or investment scheduling.

Diffcrcnt gencralizations of the basic resource allocation problems have re￾ceived growing attention in recent years. Those expansions include a varicty

of objectives as well as the presence of different kinds of resources, general

temporal constraints given by prescribed minimum and maximum time lags

between the start times of activities, and uncertainty with rcspcct to activity

durations. For a review of solution procedures, we refer to the survey papers by

Icmcli ct al. (1993), Elmaghraby (1995), 0zdamar and Ulusoy (l995), Tavares

(1995), Herroelen et al. (1998), Brucker et al. (1999), Kolisch and Padman

(2001), arid Kolisch (2001~). A comprehensive state-of-the-art overview of the

field is given by the handbook of Demeulemeester and Herroelen (2002), with

an emphasis on algorithrris for project scheduling problems with prcccdcnce

constraints among activities instead of temporal constraints. A detailed treat￾ment of specific project scheduling problems of the lattcr type can bc found in

thc monographs by Kolisch (1995), Schirmer (1998), Hartmann (1999a), Klein

(2000), and Kimms (2001~). Thc book by Hajdu (1997) is mainly concerned

with several types of time-cost tradeoff problems. Solution procedures for sev￾eral project scheduling problcms with general temporal constraints have been

discussed by De Reyck (1998), Dc Reyck et al. (1999), Neumann and Zim￾niermarin (l999a), Zimrnermann (2001 a), and Neumann et al. (2003 6). Models

and algorithms for project scheduling with stochastic activity durations arc

studicd in the doctoral dissertations of Stork (2001) and Uetz (2002). A review

of models and algorithms for projccts with stochastic evolution structurc can

bc found in Neumann (1999b).

Contribution. In this monograph we discuss structural issues, efficient

solution methods, and applications for various types of determznzstzc resource

alloratzon problems including gcncral tcmporal constraints, different typcs of

resource requirements, and several classes of objcctive functions. The divcr￾sity of the niodels dealt with permits us to cover many featurcs that arise in

Introduction 5

industrial scheduling problems. Each resourcc allocation problem gives rise to

a corresponding projcct scheduling model, which provides a formal statement

of the resource allocation task as an optimization problem. This model may or

may not include explicit resource constraints. In the latter case, limitations on

the availability of resources are taken into account by the objective function.

Our main focus in this book is on devcloping a unifying algorithmic framcwork

within which the different kinds of project scheduling models can be treated.

This framework is bascd on the seminal work by research groups around Rolf

Mohring and Franz-Josef Radermacher, who have proposed an order-thcoretic

approach to stochastic and dctcrministic resource-constrained project sched￾uling (see, e.g., Radermacher 1978, Mohring 1984, Radermacher 1985, or Bar￾tusch et al. 1988). We cxtend the order-theoretic approach to resource al￾location problems involving so-called cumulative resources, which represent

a generalization of both rcncwable and nonrenewable resources known thus

far. Based on the results of a structural analysis of resourcc constraints and

objective functions, we discuss two general types of resource allocation pro￾ccdures. By enhancing the basic modcls trcatcd with supplemcntal kinds of

constraints we bridge thc gap between issues of greatly academic interest and

requirements cmcrging in industrial contexts.

Synopsis. The book is divided into six chapters. Chapter 1 provides an

introduction to three basic project scheduling models. First we address proj￾cct scheduling subject to temporal constraints and review how the temporal

scheduling calculations for a project can be performed efficiently by calculating

longest path lengths in project networks. We then discuss rcsource constraints

which arise from the scarcity of renewable resourccs requircd. If the availabil￾ity of a resourcc at some point in time depends on all previous requirements,

wc spcak of a cumulative resource. We consider the case whcre cumulative

resourccs arc depleted and replenished discontinuously at certain points in

time. The available project funds, depleted by disbursements and replenished

by progress payments, or the rcsidual storage space for intermediate products

are examplcs of cumulative resources. For both kinds of resourcc constraints,

we explain how to observe the limited resource availability by introducing

precedcncc rclatioriships between activities.

In Chapter 2 we discuss a relation-based characterization of fcasible sched￾ules, which is bascd on diffcrent types of relations in the set of activities.

Each relation defincs a set of precedence constraints between activities. This

charactcrization provides two representations of thc feasible region of project

scheduling problems as unions of finitely many relation-induced convex sets.

Whcreas the first reprcsentation refcrs to a covering of the feasible region by

relation-induced polytopes, the second rcprcscntation arises from partitioning

the feasible region into sets of feasible schedules for which the samc prccedence

constraints are satisfied. Those two representations are the starting point for

a classification of schcdules as characteristic points likc minimal or extreme

points of certain relation-induced subsets of thc fcasible region. For differ-