Optimization of Temporal Networks under Uncertainty
Advances in Computational Management Science
1st Edition
Published on 4. January 2012
XII, 160 pages
978-3-642-23427-9 (ISBN)
Description
Many decision problems in Operations Research are defined on temporal networks, that is, workflows of time-consuming tasks whose processing order is constrained by precedence relations. For example, temporal networks are used to model projects, computer applications, digital circuits and production processes. Optimization problems arise in temporal networks when a decision maker wishes to determine a temporal arrangement of the tasks and/or a resource assignment that optimizes some network characteristic (e.g. the time required to complete all tasks). The parameters of these optimization problems (e.g. the task durations) are typically unknown at the time the decision problem arises. This monograph investigates solution techniques for optimization problems in temporal networks that explicitly account for this parameter uncertainty. We study several formulations, each of which requires different information about the uncertain problem parameters.
More details
Other editions
Additional editions
Wolfram Wiesemann
Optimization of Temporal Networks under Uncertainty
Book
02/2014
Springer
€106.99
Shipment within 7-9 days
Wolfram Wiesemann
Optimization of Temporal Networks under Uncertainty
Book
01/2012
Springer
€106.99
Shipment within 7-9 days
Content
- Intro
- Optimization of Temporal Networks under Uncertainty
- Preface
- Contents
- List of Figures
- List of Tables
- Chapter 1 Introduction
- 1.1 Motivation
- 1.2 Book Outline
- 1.3 Notation
- Chapter 2 Background Theory
- 2.1 Temporal Networks
- 2.2 Optimization Under Uncertainty
- 2.2.1 Stochastic Programming
- 2.2.2 Robust Optimization
- 2.2.3 Stochastic Dynamic Programming
- 2.3 Optimization of Temporal Networks under Uncertainty
- Chapter 3 Maximization of the Net Present Value
- 3.1 Introduction
- 3.2 Literature Review
- 3.3 Problem Formulation
- 3.4 Solution Procedure
- 3.4.1 Efficient Nodal Bounds
- 3.4.2 Warm-Start Technique
- 3.5 Numerical Results
- 3.5.1 TPT Policies and Alternative Problem Formulations
- 3.5.2 Performance of the Branch-and-Bound Procedure
- 3.6 Conclusion
- Chapter 4 Multi-Objective Optimization via ConditionalValue-at-Risk
- 4.1 Introduction
- 4.2 Literature Review
- 4.3 The Service Composition Problem
- 4.4 Mathematical Programming Formulation
- 4.5 Case Study
- 4.6 Scalability
- 4.7 Conclusion
- Chapter 5 Minimization of Makespan Quantiles
- 5.1 Introduction
- 5.2 Deterministic Resource Allocation
- 5.3 Resource Allocation Under Uncertainty
- 5.4 Numerical Results
- 5.5 Extensions
- 5.5.1 Moment Ambiguity
- 5.5.2 Iterative Path Selection Procedure
- 5.6 Conclusion
- Chapter 6 Minimization of the Worst-Case Makespan
- 6.1 Introduction
- 6.2 Robust Resource Allocations
- 6.2.1 The Robust Resource Allocation Problem
- 6.2.2 Decision Rule Approximations
- 6.2.3 Complexity Analysis
- 6.3 Path-Wise Problem Formulation
- 6.4 Lower Bounds
- 6.5 Upper Bounds
- 6.6 Numerical Results for Random Test Instances
- 6.7 Case Study: VLSI Design
- 6.8 Conclusion
- References
- Index
