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.
Inhaltsverzeichnis (Table of Contents)
- Notations
- Introduction
- The branch and bound procedure
- The technique
- A formal description
- The single-mode GRCPSP
- The model
- Problem description
- Mathematical programming formulation
- A branch and bound algorithm
- Basic terms
- The branching scheme
- The search strategy LLBM
- Logical tests
- The model
- The multi-mode GRCPSP
- The model
- Problem description
- Mathematical programming formulation
- A branch and bound algorithm
- Basic terms
- The precedence tree
- Priority rules and heuristic search strategies
- Acceleration scheme
- Critical appreciation of branch and bound
- The model
Zielsetzung und Themenschwerpunkte (Objectives and Key Themes)
This seminar paper explores the use of branch and bound algorithms to solve project scheduling problems. The focus is on the Generalized Resource-Constrained Project Scheduling Problem (GRCPSP) with both single and multi-mode job execution options. The aim is to delve into the techniques and theoretical concepts of branch and bound algorithms within the context of project scheduling.
- Branch and Bound Algorithms for Project Scheduling
- The Generalized Resource-Constrained Project Scheduling Problem (GRCPSP)
- Single-Mode and Multi-Mode Job Execution
- Mathematical Programming Formulation
- Heuristic Search Strategies and Acceleration Schemes
Zusammenfassung der Kapitel (Chapter Summaries)
- Notations: This chapter introduces the general notation used throughout the paper. It defines key terms and symbols for representing project scheduling concepts.
- Introduction: This chapter provides a brief overview of project scheduling problems and the role of branch and bound algorithms in solving them. It sets the stage for the subsequent chapters.
- The branch and bound procedure: This chapter introduces the branch and bound technique as a method for solving project scheduling problems. It explains the general concept and its applicability.
- The single-mode GRCPSP: This chapter focuses on the single-mode version of the GRCPSP. It outlines the model, including the problem description and mathematical programming formulation, and presents a specific branch and bound algorithm for solving this problem.
- The multi-mode GRCPSP: This chapter examines the multi-mode GRCPSP. It describes the model, introduces a branch and bound algorithm for multi-mode problems, and discusses priority rules and heuristic search strategies for improving the efficiency of the algorithm.
Schlüsselwörter (Keywords)
The primary keywords and focus topics of this paper include branch and bound algorithms, project scheduling, Generalized Resource-Constrained Project Scheduling Problem (GRCPSP), single-mode and multi-mode job execution, mathematical programming formulation, precedence tree, priority rules, heuristic search strategies, and acceleration schemes.
- Citation du texte
- Carsten Heuring (Auteur), 2002, Exact solution methods of project scheduling problems, Munich, GRIN Verlag, https://www.grin.com/document/60106
