PMGT3623 Scheduling Lecture Notes PDF

PMGT3623 Scheduling Week 10: Complex Task Allocation Approach Dr Shahadat Uddin The University of Sydney Page 1 Acknowledgement of Country I would like to acknowledge the Traditional Owners of Australia and recognise their continuing connection to land, water and culture. I am c...

PMGT3623 Scheduling Week 10: Complex Task Allocation Approach Dr Shahadat Uddin The University of Sydney Page 1 Acknowledgement of Country I would like to acknowledge the Traditional Owners of Australia and recognise their continuing connection to land, water and culture. I am currently on the land of the Gadigal people of the Eora Nation and pay my respects to their Elders, past, present and emerging. PMGT3623 Scheduling 2 PMGT3623 Overview Week Topic Week 01 Introduction to Scheduling, Course Resources and Assessment Components Week 02 Define and Sequence Project Tasks Week 03 Project Network Diagram (Discrete Approach) Week 04 Probabilistic Approach to Project Network Diagram – Part I Week 05 Probabilistic Approach to Project Network Diagram – Part II Week 06 Confidence Analysis of Project Network Diagram Week 07 Knowledge Test Week 08 Implementation of Project Network Diagram using Microsoft Project Week 09 Simple Task Allocation Approach Mid-Semester Break Week 10 Complex Task Allocation Approach Week 11 Progress Reporting and Earned Value Analysis Week 12 Group Assignment Presentation Week 13 Review PMGT3623: Scheduling 3 PMGT3623 Assessments No Assessment Name Weight Due date Comment 1 Weekly Participation 10% W2-W6; W9-W10 Best 6 (out of 7) 2 Knowledge Test 20% W7 3 Group Assignment Presentation (Part A) 10% W12 and W13 4 Group Assignment Report Submission (Part B) 20% Friday of W13 By 11:59 pm 5 Final Exam 40% Exam Week PMGT3623 Scheduling 4 Week 10: Complex Task Allocation Approach Topics Covered - Complex Task Allocation o Linear Programming o Demonstration with Excel Solver - Artificial Intelligence (AI) in Scheduling 5 What we learn in the last week? ❖ We learned about several simple task allocation approaches in the last week. They are categorised into three groups: ❖ Resource-centric ❖ Task-centric ❖ Methodology-centric ❖ We also did several exercises on these approaches. ❖ We will concentrate on advanced allocation approaches this week, with relevant examples and exercises. 6 Linear Programming A Brief Intro ❖ Linear Programming (LP) is a mathematical technique used for optimisation, where a linear objective function is maximised or minimised subject to a set of linear constraints. ❖ In scheduling, linear programming can be applied to optimise the allocation of resources, task scheduling, and project timelines to achieve specific goals, such as minimising costs and time or maximising resource utilisation. ❖ Although LP is a mathematical technique, I will try to keep materials related to this as simple as possible. ❖ Linear Programming is also known as Linear Optimisation. ❖ There are several ways to implement LP, including Excel and Programming Language PMGT3623 Scheduling 7 Linear Programming (cont.…) Key components ❖ Objective Function o Which is a linear equation representing the goal of the optimisation o For scheduling, the objective function could aim to optimise project cost or duration ❖ Decision Variables o Variables that represent the decisions to be made, such as the start times of tasks, allocation of resources, or the amount of time allocated to each task. ❖ Constraints o Linear equations that represent the limitations or requirements of the problem, such as resource availability, task dependencies, and deadlines. ❖ Feasible Region o The set of all possible solutions that satisfy the constraints. The optimal solution lies within this region. PMGT3623 Scheduling 8 Linear Programming (cont.…) An example of a Linear Programming application in Scheduling Project: Development of a Software Application List of Tasks 1. Requirements Gathering (2 days) 2. UI/UX Design (5 days) – predecessor 1 3. Front-End Development (10 days) – predecessor 2 4. Back-End Development (10 days) – predecessor 2 5. Integration Testing (5 days) – predecessors 3 and 4 ❖ Objective: Minimise total project duration ❖ Decision Variables 1. x1: Start time of Requirements Gathering 2. x2: Start time of UI/UX Design 3. x3: Start time of Front-End Development 4. x4: Start time of Back-End Development 5. x5: Start time of Integration Testing PMGT3623 Scheduling 9 Linear Programming (cont.…) An example of Linear Programming application in Scheduling (cont.…) Constraints ❖ Task Dependencies o UI/UX Design (x2) starts after Requirements Gathering (x1): 𝑥2 ≥ 𝑥1 + 2 o Front-End Development (x3) starts after UI/UX Design (x2): 𝑥3 ≥ 𝑥2 + 5 o Back-End Development (x4) starts after UI/UX Design (x2): 𝑥4 ≥ 𝑥2 + 5 o Integration Testing (x5) starts after both Front-End (x3) and Back-End Development (x4): 𝑥5 ≥ 𝑥3 + 10 𝑥5 ≥ 𝑥4 + 10 ❖ Non-negativity Constraints o 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0 ❖ Objective Function o Minimise the project completion time: Z = 𝑥5 + 5 (since Integration Testing lasts 5 days) PMGT3623 Scheduling 10 Linear Programming (cont.…) An example of Linear Programming application in Scheduling (cont.…) Formulated Linear Program Minimise Z = 𝑥5 + 5 Subject to 1. x2 ≥ x1 + 2 2. x3 ≥ x2 + 5 3. x4 ≥ x2 + 5 4. x5 ≥ x3 + 10 5. x5 ≥ x4 + 10 6. x1 , x2 , x3 , x4 , x5 ≥ 0 Subject to 1. x2 − x1 ≥ 2 2. x3 − x2 ≥ 5 3. x4 − x2 ≥ 5 4. x5 − x3 ≥ 10 5. x5 − x4 ≥ 10 6. x1 , x2 , x3 , x4 , x5 ≥ 0 PMGT3623 Scheduling 11 Linear Programming (cont.…) An example of Linear Programming application in Scheduling (cont.…) Formulated Linear Program and solution Subject to 1. x2 − x1 ≥ 2 2. x3 − x2 ≥ 5 3. x4 − x2 ≥ 5 4. x5 − x3 ≥ 10 5. x5 − x4 ≥ 10 6. x1 , x2 , x3 , x4 , x5 ≥ 0 Solution x1 x2 x3 x4 x5 Z Solution 0 2 7 7 17 22 Objective coefficient 0 0 0 0 1 LHS RHS Constraint 1 -1 1 2 ≥ 2 Constraint 2 -1 1 5 ≥ 5 Constraint 3 -1 1 5 ≥ 5 Constraint 4 -1 1 10 ≥ 10 Constraint 5 -1 1 10 ≥ 10 The project duration is 22 days PMGT3623 Scheduling 12 Linear Programming (cont.…) An example of Linear Programming application in Scheduling (cont.…) Cross-validation using Network Diagram Solution from Linear Programming x1 x2 x3 x4 x5 Z Solution 0 2 7 7 17 22 Objective coefficient 0 0 0 0 1 LHS RHS Constraint 1 -1 1 2 ≥ 2 Constraint 2 -1 1 5 ≥ 5 Constraint 3 -1 1 5 ≥ 5 Constraint 4 -1 1 10 ≥ 10 Constraint 5 -1 1 10 ≥ 10 Same duration 7 17 x3(10) S0 0 2 2 7 7 17 17 22 x1(2) S0 x2 (5) S0 x5(5) S0 0 2 2 7 7 17 17 22 x4(10) S0 7 17 PMGT3623 Scheduling 13 Linear Programming (cont.…) Advantages ❖ Optimal solution: Linear Programming provides the best solution given the constraints, ensuring the optimal use of resources. ❖ Flexibility: Linear Programming can handle various problems and constraints, making it applicable in various applications and scenarios. ❖ Resource allocation: Linear Programming is particularly effective in optimising resource allocation ❖ Scalability: Linear programming can be applied to small-scale and large-scale problems. ❖ Clarity and Structure: Linear Programming models provide a clear mathematical representation of the problem, making it easier to understand, analyse, and communicate. ❖ Decision Support: Linear Programming helps make informed and objective decisions based on quantitative data, reducing the reliance on intuition or guesswork. ❖ Automation: Linear Programming problems can be solved using various software tools and algorithms, allowing for automation and handling complex calculations efficiently. 14 Linear Programming (cont.…) Limitations ❖ Linearity Assumption: Linear Programming assumes that all relationships between variables are linear, which may not accurately reflect the complexities of real-world problems. ❖ Certainty Assumption: Linear Programming requires that all coefficients in the objective function and constraints be known with certainty. This may be often unrealistic as many real-world parameters are subject to uncertainty and variability. ❖ Integer Constraint: Linear Programming assumes decision variables can take any continuous values. However, in many cases, such variables need to take only integer values. Integer Programming would be a solution to this problem. ❖ Implementation Complexity: Formulating Linear Programming problems can be complex and requires a good understanding of mathematical modeling and optimisation techniques, especially for large-scale complex problems. 15 1. Exercise on Linear Programming A firm manufactures wood screws and metal screws. All the screws have to pass through a threading machine and a slotting machine. A box of wood screws requires 3 minutes on the slotting machine and 2 minutes on the threading machine. A box of metal screws requires 2 minutes on the slotting machine and 8 minutes on the threading machine. In a week, each machine is available for 60 hours. There is a profit of $10 per box of wood screws and $17 per box of metal screws. Formulate this problem as a Linear Programming problem given that the objective is to maximise the profit. Solution: Unknowns: x = the number of boxes for wood screws y = the number of boxes for metal screws Constraints: Slotting machine: 3x + 2y ≤ 3600 Threading machine: 2x + 8y ≤ 3600 Non-negativity: x ≥ 0 and y ≥ 0 Profit: P = 10x + 17y Thus, the formulated LP problem is: maximise P = 10x+17y subject to 3x + 2y ≤ 3600 2x + 8y ≤ 3600 x ≥ 0 and y ≥ 0 PMGT3623 Scheduling 16 Linear Programming and Crashing ❖ Consider a hypothetical project with 7 tasks. We will consider Linear Programming and Crashing (from Week 6) together in this example. ❖ The table below shows the task details (duration is in days) and their crashing information. Normal Crash Normal Crash Crash Cost Task Predecessor Duration Duration Cost Cost per Day A --- 6 5 $60 $90 $30 B --- 7 4 $50 $150 $33 C A 6 4 $100 $160 $30 D A 7 7 $30 $30 NA E B 5 4 $70 $85 $15 F C 9 7 $40 $120 $40 G D, E 7 4 $50 $230 $60 Total cost $400 Network Paths ACF (6 + 6 + 9 = 21) ADG (6 + 7 + 7 = 20) BEG (7 + 5 + 7 = 19) Corresponding Network Diagram Li, K., Shao, B., & Zelbst, P. (2012). Project crashing using Excel solver: a simple AON network approach. International Journal of Management & Information 17 Systems (Online), 16(2), 177. Linear Programming and Crashing (cont.…) Network Paths ACF (6 + 6 + 9 = 21) ADG (6 + 7 + 7 = 20) BEG (7 + 5 + 7 = 19) Corresponding Network Diagram ❖ The project duration is 21 days now. However, the project sponsor wants to reduce its duration to ≤18 days. ❖ At the same time, the management wants to keep the overall cost as minimum as possible. ❖ We will learn how to solve this using the Linear Programming and Crashing approach in the next few slides. 18 Linear Programming and Crashing (cont.…) Problem Statement Minimise the total project cost Subject to Project completion time ≤18 days Number of days crashed for each task ≤ the maximum available crashing available for that task Non-negative decision variables Network Diagram Decision variables: C18:C24 Target variable: total cost (B2) B1 contains the expected project duration threshold 19 Linear Programming and Crashing (cont.…) Corresponding Excel Solver setting 20 Linear Programming and Crashing (cont.…) Solution from Excel Solver 21 Linear Programming – How does it work (Graphical solution)? A farmer has 20 hectares of growing barley and swede. The farmer has to decide how much of each to grow. The cost per hectare for barley is $30 and for swede is $20. The farmer has budgeted $480. Barley requires 1 man-day per hectare, and swede requires 2 man-days per hectare. There are 36 man-days available. The profit on barley is $100 per hectare, and on swede is $120 per hectare. Formulate this problem as a linear programming problem. Find the number of hectares of each crop the farmer should sow to maximise profits using the graphical linear programming approach. Solution: Unknowns: x = number of hectares for barley; and y = number of hectares for swede Constraints: Land: x + y ≤ 20 Cost: 30x + 20y ≤ 480 Manpower: x + 2y ≤ 36 Profit P = 100x + 120y To summarise: Maximise P = 100x + 120y Subject to x + y ≤ 20 30x + 20y ≤ 480 x + 2y ≤ 36 x ≥ 0 and y ≥ 0 PMGT3623 Scheduling 22 Linear Programming – How does it work (Graphical solution)? (cont.…) For x + y = 20: if x = 0, y = 20 (0, 20) if y = 0, x = 20 (20, 0) For 30x + 20y = 480: if x = 0, y = 24 (0, 24) if y = 0, x = 16 (16, 0) For x + 2y = 36: if x = 0, y = 18 (0, 18) Use the P-function for the feasible region, C = 100x + 120y if y = 0, x = 36 (36, 0) PMGT3623 Scheduling 23 Linear Programming – How does it work (Graphical solution)? (cont.…) We have four points in the feasible region. Now, we need to find the point for which we will get the maximum profit (i.e., 100x + 120y) First point: (0, 20) Second point: (4, 16) P = 100*4 + 120*16 = $2,320 Third point: (8, 12) Fourth point: (16, 0) As you can see, C (i.e., P) increases as the line (shown dotted) moves to the right. So, the maximum profit will occur at the intersection of x + 2y = 36 and x + y = 20 x = 20 – y (2nd one); thus, 20 – y + 2y = 36 (first one); eventually, y = 16 and x = 4 (Second point) PMGT3623 Scheduling 24  Artificial Intelligence (AI) in Scheduling Generative AI (Large Language Model) – The Future PMGT3623 Scheduling 25 Review Questions a) What is linear programming? How does it relate to project scheduling? b) Explain the differences between linear programming and integer programming c) What are the advantages and limitations of linear programming? d) What are the key components of linear programming? 26