Excerpt

## Contents

Notations

1 Introduction

2 The branch and bound procedure

2.1 The technique

2.2 A formal description

3 The single-mode GRCPSP

3.1 The model

3.1.1 Problem description

3.1.2 Mathematical programming formulation

3.2 A branch and bound algorithm

3.2.1 Basic terms

3.2.2 The branching scheme

3.2.2 The search strategy LLBM

3.2.3 Logical tests

4 The multi-mode GRCPSP

4.1 The model

4.1.1 Problem description

4.1.2 Mathematical programming formulation

4.2 A branch and bound algorithm

4.2.1 Basic terms

4.2.2 The precedence tree

4.2.3 Priority rules and heuristic search strategies

4.3.1 Acceleration scheme

5 Critical appreciation of branch and bound

6 Summary and prospect

Appendix – Tables

Bibliography

## Notations

**General notations:**

illustration not visible in this excerpt

Notations for chapter 3

illustration not visible in this excerpt

Notations for chapter 4

illustration not visible in this excerpt

## 1 Introduction

“The use of project management is continuously growing in industrial and public organizations providing an efficient instrument for mastering the challenges caused by steadily shortening product life cycles, decreasing profit margins, and global markets.”^{[1]} “One of the main tasks in project management is the scheduling of the project, that is, the temporal arrangement of activities.”^{[2]} Here, the consideration of resources is in the centre of attention.

Resources are required to perform activities and are available with limited capacities. Therefore, within the project management the activities are to be scheduled subject to precendence and resource constraints. In practice, different types of resources may occur. Renewable resources (e.g. machines) are available at each point in time. Nonrenewable resources (e.g. money) are depleted by use. These resources only affect the scheduling of activities if activities can be carried out in alternative modes which differ, for example, in duration and amount of resources needed. In this case we are speaking of multi-mode scheduling problems in contrast to single-mode scheduling problems.^{[3]} To describe these scheduling problems we use mathematical models. This work is founded on the single-mode GRCPSP^{[4]} and an extention of it, the multi-mode GRCPSP (both NP-hard^{[5]} ). The different models are presented in the chapters 3.1 and 4.1 by problem description and explicit mathematical programming formulations. Therefore, solution methods become mathematically complex in solving them.

In general, the techniques applied within exact procedures for solving resource constrained project scheduling problems belong to one of the following basic categories: integer programming, dynamic programming, or branch and bound methods.^{[6]} “Almost all exact algorithms are branch-and-bound procedures”^{[7]}. Therefore, we have a look at this meta strategy.

Because of a large number of different procedures caused by the branch and bound system it is not possible to present all of them. So, a theoretical basis to apply the branch and bound algorithm in the presented exact solution methods are given in chapter 2. In the following, exact procedures for solving the single mode GRCPSP, presented by Klein (2000), and the multi mode GRCPSP, presented by Sprecher (1994), are given in chapters 3.2 and 4.2.^{[8]} Finally, this work is concluded by a critical appreciation of branch and bound algorithms in chapter 5 and a summary and prospect (chapter 6).

## 2 The branch and bound procedure

### 2.1 The technique

An original problem is given which is too difficult to be solved directly. Therefore, it is natural to consider the use of an enumeration procedure for finding an optimal solution. “The basic concept underlying the branch-and-bound technique is to divide and conquer.”^{[9]}

Here, we assume that a given objective function has to be minimized. Furthermore, an upper bound UB on the optimal objective function value is feasible. Normally, UB is the objective function value of the optimal permissible solution which can be calculated. First, the initial subproblem as well as the subproblems are subdivided into further subproblems. For this purpose, a lower bound LB on the objective function value for every subproblem has to be calculated. Subproblems are dismissed from further considerations if fathoming tests have positively indicated. After fathoming subproblems, the remaining ones which have the smallest lower bound are branched into new subproblems. This procedure is repeated as often as any permissible solution which has an objective function value that is not larger than a lower bound of each remaining subproblem is found.^{[10]} As result, we obtain a multi-level enumeration tree which includes the optimal solution. For other comprehension descriptions, it is refered to Scholl et al. (1997) and Domschke and Drexl (1998).

### 2.2 A formal description

The aim is to give a (theoratical) basis for the exact solution methods presented in the following chapters. Now we can describe a step by step procedure (which is based on Hillier and Lieberman (1997)) to perform a branch and bound algorithm.

**[...]**

^{[1]} Klein and Scholl (1999, p. 1)

^{[2]} Hartmann (1999, p. 1)

^{[3]} cf. Neumann et al. (2001, p. 21)

^{[4]} The GRCPSP model is used because of its high practical relevance. (cf. Klein (2000, S. 90))

^{[5]} „The problem class NP-hard consists of those problems for which no polynomial time algorithm determining an optimal solution has been developed yet.“ (Klein (2000, p. 95))

^{[6]} cf. Klein (2000, p. 213)

^{[7]} Neumann et al. (2001, p. 22)

^{[8]} Caused by different algorithms, assumptions used by diverse authors we will have a variety of symbols in the models and branch and bound algorithms. Therefore and in addition to the fact that this work could not be considered isolated (with regard to extensions), the notations of Sprecher and Klein are adopted.

^{[9]} cf. Hillier and Lieberman (1995, p. 515)

^{[10]} According to: Hillier and Lieberman (1997, pp. 388 p.).

- Quote paper
- Carsten Heuring (Author), 2002, Exact solution methods of project scheduling problems, Munich, GRIN Verlag, https://www.grin.com/document/60106

Publish now - it's free

Comments