# Project Management Problem Solution ## Given Data | Activity | Predecessor | Duration (weeks) | Speed-up Cost ($/week) | |----------|-------------|------------------|------------------------| | A | - | 6 | 80 | | B | - | 5 | 60 | | C | A | 3 | 30 | | D | C | 2 | 60 | | E | A, D | 3 | 40 | | F | B | 2 | 30 | | G | E | 4 | 20 | | H | G, F | 2 | - | --- ## (a) Project Diagram, Critical Paths, and Float Calculation ### 1. **Activity Network Diagram** ``` 6 3 2 3 4 2 A ----> C ----> D ----> E ----> G ----> H \ / \ / \ / \ / \ / \ / 5 2 / B -----> F -------------------/ ``` #### Precedence: - A → C → D → E → G → H - B → F → H ### 2. **Paths and Durations** - **Path 1:** A (6) → C (3) → D (2) → E (3) → G (4) → H (2) = **20 weeks** - **Path 2:** B (5) → F (2) → H (2) = **9 weeks** ### 3. **Critical Path** - **Longest path:** Path 1 (20 weeks) is the critical path. - **Critical Activities:** A, C, D, E, G, H ### 4. **Total and Free Float** - **Total Float:** Maximum time an activity can be delayed without delaying the project. - **Free Float:** Maximum time an activity can be delayed without delaying the earliest start of its successor. **Non-critical activities:** B, F - **Earliest Start (ES) and Latest Start (LS):** - B: ES = , LS = (since F is not on critical path, float = difference in path lengths: 20 - 9 = 11) - F: Can start after B finishes at week 5, but H only starts after G and F finish, and G finishes at week 18 (A→C→D→E→G). So, F can finish as late as week 18, thus float = 18 - 7 = 11. --- ## (b) LP to Determine the Critical Path Let \( x_i \) be the start time of activity \( i \). **Objective:** Maximize \( x_H \) **Constraints:** - \( x_A \geq \), \( x_B \geq \) - \( x_C \geq x_A + 6 \) - \( x_D \geq x_C + 3 \) - \( x_E \geq \max(x_A + 6, x_D + 2) \) - \( x_F \geq x_B + 5 \) - \( x_G \geq x_E + 3 \) - \( x_H \geq \max(x_G + 4, x_F + 2) \) **LP Formulation:** \[ \text{Maximize} \quad x_H \] \[ \begin{align*} x_A &\geq \\ x_B &\geq \\ x_C &\geq x_A + 6 \\ x_D &\geq x_C + 3 \\ x_E &\geq x_A + 6 \\ x_E &\geq x_D + 2 \\ x_F &\geq x_B + 5 \\ x_G &\geq x_E + 3 \\ x_H &\geq x_G + 4 \\ x_H &\geq x_F + 2 \\ \end{align*} \] --- ## (c) Minimum Cost Network Flow Problem Formulation Let \( y_i \) be the duration reduction (crash) for activity \( i \), \( \leq y_i \leq 2 \). - **Objective:** Minimize \( \sum \text{(Speed-up cost for i)} \times y_i \) - **Subject to:** Project duration ≤ 12 weeks For each activity: \[ \text{Minimize:}\; 80y_A + 60y_B + 30y_C + 60y_D + 40y_E + 30y_F + 20y_G \] **Subject to:** \[ (A + C + D + E + G + H) - (y_A + y_C + y_D + y_E + y_G) \leq 12 \] Where: - A=6, C=3, D=2, E=3, G=4, H=2 \[ 6 + 3 + 2 + 3 + 4 + 2 - (y_A + y_C + y_D + y_E + y_G) \leq 12 \] \[ 20 - (y_A + y_C + y_D + y_E + y_G) \leq 12 \] \[ y_A + y_C + y_D + y_E + y_G \geq 8 \] And, \( \leq y_i \leq 2 \) for each \( i \). --- ## (d) LP Model for Reducing Duration to 12 Weeks **Formulation:** \[ \text{Minimize:}\; 80y_A + 30y_C + 60y_D + 40y_E + 20y_G \] \[ \text{Subject to:} \] \[ y_A + y_C + y_D + y_E + y_G \geq 8 \] \[ \leq y_A, y_C, y_D, y_E, y_G \leq 2 \] --- ## **Final Summary** - **Critical Path:** A → C → D → E → G → H, duration = 20 weeks. - **Total reduction needed:** 8 weeks (to achieve 12 weeks). - **LP Model:** Minimize the cost of crashing while reducing the critical path by 8 weeks, within activity speed-up cost and maximum reduction limits. - **Key insight:** Use LP to allocate reductions to the cheapest activities on the critical path, observing all logical and cost constraints. **Note:** This approach gives you the mathematical framework and logic. Actual numerical optimization (e.g., which activities to crash specifically) would typically be performed using an LP solver.

# Project Management Problem Summary ## (a) Project Diagram, Critical Paths, and Float Calculation The project consists of two paths, with the critical path being A → C → D → E → G → H, totaling 20 weeks. Non-critical activities B and F have a float of 11 weeks, allowing for some flexibility in scheduling. ## (b) LP to Determine the Critical Path The linear programming (LP) formulation aims to maximize the completion time of the project, specifically the end time of activity H. Constraints include the sequential dependencies of activities A through H. ## (c) Minimum Cost Network Flow Problem Formulation The objective is to minimize the total speed-up costs associated with crashing the project duration from 20 weeks to 12 weeks. This requires reducing the durations of critical activities while respecting their maximum allowable reductions. ## (d) LP Model for Reducing Duration to 12 Weeks The LP model focuses on minimizing the costs of crashing selected activities to achieve the desired project duration of 12 weeks. It incorporates constraints on the minimum reduction required and the maximum possible reductions for each activity.