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. One of the main tasks in project management is the scheduling of the project, that is, the temporal arrangement of activities. 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. To describe these scheduling problems we use mathematical models. The techniques to solve resource constrained project scheduling problems are descriebed with branch and bound methods.
Table of Contents
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
Objectives & Core Topics
This paper examines exact solution methods for the generalized resource-constrained project scheduling problem (GRCPSP). The primary objective is to provide a theoretical basis and a structured overview of the branch and bound meta-strategy as applied to both single-mode and multi-mode scheduling scenarios.
- Fundamental concepts of the branch and bound procedure.
- Modeling and solution algorithms for single-mode GRCPSP.
- Mathematical formulation and branching strategies for multi-mode GRCPSP.
- Implementation of acceleration schemes and logical tests to improve algorithmic performance.
- Critical evaluation of the effectiveness and limitations of exact algorithms in project scheduling.
Excerpt from the Book
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.”
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. 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).
Chapter Summaries
1 Introduction: This chapter contextualizes project management within modern industry and introduces the necessity of exact solution methods for NP-hard scheduling problems.
2 The branch and bound procedure: This chapter outlines the general "divide and conquer" philosophy of the branch and bound meta-strategy and defines the formal steps required for its execution.
3 The single-mode GRCPSP: This chapter details the mathematical modeling and a specific branch and bound algorithm, including branching schemes and search strategies, for projects with fixed durations.
4 The multi-mode GRCPSP: This chapter extends the scheduling problem to scenarios with multiple execution modes per job and introduces specific branching and acceleration techniques.
5 Critical appreciation of branch and bound: This chapter evaluates the strengths and weaknesses of exact algorithms, highlighting the trade-off between optimality and computational effort.
6 Summary and prospect: This chapter concludes the work by reviewing the covered methods and suggesting further reading regarding unified notations and recent developments in the field.
Keywords
Project Scheduling, GRCPSP, Branch and Bound, Resource Constraints, Optimization, Multi-mode, Single-mode, Enumeration Tree, Mathematical Programming, Makespan, Heuristics, Precedence Constraints, Algorithm, NP-hard, Branching Scheme.
Frequently Asked Questions
What is the primary focus of this paper?
The paper focuses on the application of exact solution methods, specifically branch and bound procedures, to solve generalized resource-constrained project scheduling problems (GRCPSP).
What are the core thematic areas discussed?
The central topics include the mathematical modeling of projects, branching strategies for both single-mode and multi-mode scenarios, and performance-enhancing logical tests.
What is the main research goal?
The goal is to provide a theoretical and practical overview of how branch and bound algorithms can be used to find optimal schedules for complex project structures.
Which scientific methodology is primarily employed?
The work utilizes mathematical modeling and the analysis of enumeration procedures, specifically the branch and bound strategy, to address scheduling optimization.
What is the scope of the main chapters?
The main chapters cover the formal description of the branch and bound technique, its adaptation to single-mode and multi-mode problems, and a critical analysis of its limitations.
Which terms characterize this research?
Key terms include GRCPSP, project management, branch and bound, optimization, and resource constraints.
How does the author define the "core time"?
The core time is the interval between the earliest starting time (based on a reduced upper bound) and the earliest finishing time, used in reduction tests to identify unfeasible partial schedules.
Why is the "serial branching scheme" contrasted with the "parallel branching scheme"?
The serial branching scheme constructs the tree by assigning starting times to individual available jobs, whereas the parallel scheme branches based on decision points where multiple jobs may be scheduled.
- Quote paper
- Carsten Heuring (Author), 2002, Exact solution methods of project scheduling problems, Munich, GRIN Verlag, https://www.grin.com/document/60106
