Dynamic and Stochastic Multi-Project Planning

List of Figures

List of Tables

1 Introduction
     1.1 Background
     1.2 Research Focus
          1.2.1 Order Acceptance and Capacity Planning
          1.2.2 Resource-Constrained Multi-project Scheduling
     1.3 Outline

2 Problem Statements
     2.1 General Assumptions and Notation
          2.1.1 Projects
          2.1.2 Resources
          2.1.3 Project Types
          2.1.4 Objective Functions
     2.2 Dynamic-Stochastic Multi-project Scheduling Problem
          2.2.1 Non-preemptive Scheduling Problem
          2.2.2 Preemptive Scheduling Problem
     2.3 Order Acceptance and Capacity Planning Problem
          2.3.1 Multi-project Environment
          2.3.2 Order Acceptance Decisions
          2.3.3 Resource Allocation Decisions

3 Literature Review
     3.1 Dynamic Programming and Approximate DynamicProgramming
     3.2 Project Scheduling
          3.2.1 Static–Deterministic Project Scheduling
          3.2.2 Dynamic–Deterministic Project Scheduling
          3.2.3 Static–Stochastic Project Scheduling
          3.2.4 Dynamic–Stochastic Project Scheduling
     3.3 Capacity Planning
     3.4 Order Acceptance

4 Continuous-Time Markov Decision Processes
     4.1 General Structure
     4.2 Basic Definitions and Relevant Properties
     4.3 Objective Function
     4.4 Evaluation and Optimality Equations
     4.5 Uniformization
     4.6 General Solution Methodologies
          4.6.1 Value Iteration
          4.6.2 Policy Iteration
     4.7 Implementation
          4.7.1 Generation of the State Space
               4.7.1.1 Data Structures
               4.7.1.2 Generation Procedure
          4.7.2 Solution Methodologies

5 Generation of Problem Instances
     5.1 Generation of Project Networks
     5.2 Generation Procedure
          5.2.1 Step 1: Assignment of Activity Types to Resource Types
          5.2.2 Step 2: Determination of Expected Durations of the Activity Types
          5.2.3 Step 3: Variation Check of the Expected ActivityDurations
          5.2.4 Step 4: Adjustments to Resource Type SpecificUtilizations
          5.2.5 Step 5: Check of Project Type Workloads
          5.2.6 Step 6: Storage of Additional Parameters

6 Scheduling Using Priority Policies
     6.1 Priority Policies
          6.1.1 Computation of Rule Parameters
          6.1.2 Priority Rules
               6.1.2.1 Bottleneck Dynamics Rules
               6.1.2.2 Further Rules
     6.2 Experimental Design
          6.2.1 Preliminaries
          6.2.2 Generation of Problem Instances
               6.2.2.1 System Parameters
               6.2.2.2 Project Type Parameters
          6.2.3 Simulation Set Up
     6.3 Main Effects of Problem Parameters
          6.3.1 Due Date Tightness
          6.3.2 Number of Resources
          6.3.3 Order Strength
          6.3.4 Variation of Expected Activity Durations
          6.3.5 Utilization per Resource
          6.3.6 Observations for Problem Instances with a Single Project Type
     6.4 Detailed Analysis
          6.4.1 Performance for Special Cases
               6.4.1.1 Single Resource
               6.4.1.2 Parallel Networks
          6.4.2 Performance for the Remaining Problem Instances
               6.4.2.1 High Due Date Tightness
               6.4.2.2 Low Due Date Tightness

7 Optimal and Near Optimal Scheduling Policies
     7.1 Models as a Markov Decision Process
          7.1.1 Non-preemptive Scheduling Problem
               7.1.1.1 Markov Decision Process
               7.1.1.2 Evaluation and Optimality Equations
               7.1.1.3 Elimination of Scheduling Decisions
          7.1.2 Preemptive Scheduling Problem
               7.1.2.1 Extension of the CTMDP for the Non-preemptive Problem
               7.1.2.2 Simplified CTMDP
               7.1.2.3 Efficient Procedure for Determining Optimal Decisions
               7.1.2.4 State Space Cardinality
          7.1.3 Numerical Example
               7.1.3.1 General Observations
               7.1.3.2 Optimal Policy for the Preemptive Scheduling Problem
               7.1.3.3 Optimal Policy for the Non-preemptive Scheduling Problem
               7.1.3.4 Effect of Rejection Cost
     7.2 Optimal Policy for the Single Resource Case Without Preemptions
     7.3 Project State Ordering Policies
          7.3.1 Preemptive Project State Ordering Policies
               7.3.1.1 Definitions and General Structural Results
               7.3.1.2 Project State Ordering Policies and Queueing Networks Representation of the System
          7.3.2 Non-preemptive Project State Ordering Policies
          7.3.3 Project State Ordering Priority Policies
          7.3.4 Numerical Example
     7.4 Scheduling Using Approximate Dynamic Programming
          7.4.1 Basic Idea
          7.4.2 Approximation Based on the Preemptive Problem
          7.4.3 Approximation Using Linear Function Approximation
               7.4.3.1 Selection of Basis Functions
               7.4.3.2 Semi-open System as an Approximation for the Open System
               7.4.3.3 Bellman Error Minimization
               7.4.3.4 Determining Sets of Representative States
          7.4.4 Approximation for the Non-preemptive Problem Based on Linear Function Approximation for the Preemptive Problem
     7.5 Computational Study
          7.5.1 Experimental Design
          7.5.2 Priority Policies
          7.5.3 Simulation Setup
          7.5.4 Results for the Preemptive Problem
               7.5.4.1 State Space Cardinalities
               7.5.4.2 Performance of Optimal Policies
               7.5.4.3 Performance of Project State Ordering Priority Policies
          7.5.5 Results for the Non-preemptive Problem
               7.5.5.1 State Space Cardinalities
               7.5.5.2 Performance of Optimal Policies
               7.5.5.3 Performance of Project State Ordering Priority Policies
               7.5.5.4 Performance of the Value Function Approximation from the Preemptive Problem
          7.5.6 Performance of Linear Function Approximation
               7.5.6.1 Test of the Approximation Architectures and First Computational Insights
               7.5.6.2 Application of Linear Function Approximation to Selected Problem Instances

8 Integrated Dynamic Order Acceptance and Capacity Planning
     8.1 Stochastic Dynamic Programming
          8.1.1 State Variables
          8.1.2 Decision Variables
               8.1.2.1 Order Acceptance Decisions
               8.1.2.2 Capacity Planning Decisions
          8.1.3 Exogenous Information Process
          8.1.4 Transition Function
          8.1.5 Objective Function
     8.2 Solution Methodology
     8.3 Computational Investigation
          8.3.1 Structure of Optimal Policies
               8.3.1.1 Order Acceptance
               8.3.1.2 Scheduling
               8.3.1.3 Usage of Non-regular Capacity
          8.3.2 Benefit of Crashing and Flexible MPP
               8.3.2.1 Benefit of Crashing
               8.3.2.2 Benefit of MPP
               8.3.2.3 Combined Benefit of MPP and Crashing
               8.3.2.4 General Insights

9 Conclusions and Future Work

A Abbreviations

B Symbols
     B.1 General
          B.1.1 System
          B.1.2 Markov Decision Processes
          B.1.3 Projects and Project Types
          B.1.4 Resources and Resource Types
     B.2 Generation of Problem Instances
          B.2.1 Problem Parameters
          B.2.2 Generation Procedure
     B.3 Scheduling
          B.3.1 General
          B.3.2 Scheduling Using Priority Policies
          B.3.3 Markov Decision Process for the Non-preemptiveProblem
          B.3.4 Markov Decision Process for the Preemptive Problem
          B.3.5 Optimal Policy for the Non-preemptive Problem with a Single Resource
          B.3.6 Preemptive Project State Ordering Policies
          B.3.7 Non-preemptive Project State Ordering Policies
          B.3.8 Approximate Dynamic Programming
     B.4 Order Acceptance and Capacity Planning

Bibliography