Description
The objective of this assignment was to identify any real world problem in the industry you are working and try to solve it using OR.
OPERATIONAL RESEARCH (OR)
ASSIGNMENT XLRI-PGCBM-18
Table of Contents
1. PROBLEM: ............................................................................................................................................................1 2. SOLUTION:............................................................................................................................................................2 2.1 MANUAL APPROACH...............................................................................................................................................2 2.2 LINEAR PROGRAMMING APPROACH.............................................................................................................................2 2.2.1 Decision Variables:....................................................................................................................................3 2.2.2 Objective Function:....................................................................................................................................3 2.2.3 Constraints:................................................................................................................................................3 2.3 EXCEL SOLUTION....................................................................................................................................................6 2.3.1 Excel Solution Embedded: .....................................................................................................................7 3. ANALYSIS:.............................................................................................................................................................7 3.1 SENSITIVITY ANALYSIS: OBJECTIVE FUNCTION ...........................................................................................................7 3.2 SENSITIVITY ANALYSIS: RIGHT HAND SIDE OF THE CONSTRAINTS..................................................................................7
1.
Problem:
Mr. Ramesh Chandra is a Software Development Project Manager in one of the renowned Indian Software Services Company, namely “ABC Technologies”. The company’s business division has recently won a project from a major European telecom company. This Project is very important for the “ABC Technologies” as it is first time the company is entering in the telecom sector for the software services. The “ABC Technologies” has been given whole end to end responsibility for this software package from Requirement Analysis till final Deployment. Customer has communicated recently to the business director of “ABC Technologies” that they would like to see the final Project Plan with a Breakdown of the tasks, Total Cost of the Project and Total duration of the Project by end of next week. “ABC Technologies” management has decided to assign Ramesh Chandra as the Project Manager for this Project and has been told to come up with the Project Plan so that they can share it with the Customer by end of next week. Ramesh has already been provided with all the required inputs so that he can be prepared for the plan. Mr. Ramesh worked very hard and came up with the following plan.
Table-1: Initial Plan Durations and Effort are here in Person Days (pdays). AS per this plan, Activities/Tasks A-B-C-D-E-F-H-I-L-M are on Critical Path and the Project duration comes to 64 days. The Total Cost of the Project comes to $20,000. During the plan discussion with the customer, customer commented that the duration of 64 days for this project is not acceptable to them and they would like the project duration be reduced by at least 20 days with a very minimal extra cost impact. Ramesh agreed during the meeting that he would try to reduce the duration and will come up with the new plan in a couple of days.
2.
Solution:
Being a Project Manager, Ramesh knows that Project time cam be reduced by a technique called Crashing which takes care to reduce the duration on a minimal extra cost. To start the Crashing, Ramesh needs to know how much time each activity can be crashed to and how much it will cost. He starts this activity and comes with the following analysis for each activity. Durations and Effort are here in Person Days (pdays).
Table-2: Plan with Crash Time and Crash Cost against each activity. There are two approaches to the problem:
2.1
Manual Approach
For crashing project time, the first task is to identify the normal critical path and the critical activities. Then it is required to determine the crash cost per time period (cost-time slopes) for various activities. The cost-time slopes can be computed using the following formula: Slope = Crash Cost – Normal Cost -------------------------------------Normal Time –Crash Time
The next step is to identify the activity on the critical path with the smallest crash cost per time period. This activity will be crashed to the maximum possible extent or to the point at which management’s desired deadline has been reached. Then it should be checked that the critical path that were being crashed is still critical. If the path is still critical then crash the activity that has second lowest cost-time slopes and continue this process until the goal has been reached. If, a reduction in a critical activity time causes a non-critical path or paths to become critical, then the crash will be continued along with the new critical path based on the lowest cost time slopes of the new path.
2.2
Linear programming approach
The linear programming is a tool for decision making under certain situation. So, the basic assumption of this approach is that to know some relevant data with certainty. The basic data requirements are as follows: 1) To know the project network with activity time, and their precedence sequence. 2) To what extent an activity can be crashed. 3) The crash cost associated with per unit of time for all activities. These requirements are identified in Table-2. Now let’s define the variable of the problem.
2.2.1 Decision Variables: Ti = Time at each activity “i”, starts. Ci = Number of periods (days in this case) by which an activity “i”, is crashed. 2.2.2 Objective Function:
The objective function here is to minimize the total cost of crashing the project down to 47 (64-20 = 44) days. Using the crash cost per week computed in Table-2. The Crash Cost per week per activity is computed using following formula: Crash Cost – Normal Cost -------------------------------Normal Time –Crash Time So the objective function can be expressed as follows. For each activity “i”, following two variables can be defined.
MIN (Z) = $0Ca+ $500Cb +$222Cc +$500Cd +$545Ce +$500Cf +$500Cg +$500Ch +667Ci+250Cj+ $286Ck + $400Cl +$667Cm 2.2.3 Constraints:
This objective function is subject to some constraints. These constraints can be classified in to three categories.
1) Precedence Constraints:
These set of constraints describe the structure of the network. As we know, the activities of a project are interrelated, the starting of some activities is dependent upon the completion of some other activities; we must have to establish work sequence of the activities through constraints. For this problem the precedence constraints are defined as below: The precedence for each activity is given in below Table-3 in column “Predecessors”
Table-3: Precedence Relationship of the Activities
Fig-1: Project Network Diagram
A->B B->C C->D C->K C->J D->E E->F E->K E->G E->J F->H H->I G->I I->L J->L K->L L->M Tb >= Ta + 4-Ca Tc >= Tb + 8Cb Td>= Tc+9Cc Tk >= Tc+9Cc Tj >= Tc+9Cc Te >=Td+6Cd Tf >= Te+11Ce Tk >= Te+11Ce Tg>= Te+11Ce Tj >= Te+11Ce Th >= Tf + 4Cf Ti >= Th + 8Ch Ti >= Tg + 4Cg Tl >= Ti + 6Ci Tl >= Tj + 16Cj Tl >= Tk + 14-Ck Tm >= Tl + 5-Cl written as Tb-Ta+ Ca >=4. i.e . i.e . i.e . i.e . i.e . i.e . i.e . i.e . i.e . i.e . i.e . i.e . i.e . i.e . i.e . i.e . i.e . Tb-Ta+ Ca >=4 Tc-Tb+ Cb >=8 Td - Tc + Cc >=9 Tk - Tc + Cc>=9 Tj – Tc + Cc>=9 Te – Td + Cd>=6 Tf - Te + Ce >=11 Tk – Te + Ce >=11 Tg - Te + Ce >=11 Tj – Te + Ce >=11 Th - Tf + Cf >= 4 Ti – Th + Ch >=8 Ti - Tg + Cg >=4 Tl – Ti + Ci >=6 Tl – Tj + Cj >=16 Tl – Tk + Ck>=14 Tm - Tl + Cl >=5
Table-4: Precedence Constraints For e.g. consider the precedence relationship between activities A and B. Activity A starts at time Ta and its duration is (4-Ca) days where Ca is the duration activity A can be crashed. Hence activity A finishes at time (Ta+4Ca).This implies that activity B start time (Tb) can be no earlier than (Ta+4Ca). It can be expressed mathematically as: Tb >= Ta + 4-Ca , it can also be
In a similar fashion, precedence relationship of all other activities are expressed in Table-4
2) Crash Time Constraints:
We can reduce the time to complete an activity by simply increasing the resources or by improving the productivity which also require the commitment of additional resources. But it is not possible to reduce the time required to complete an activity after a certain threshold limit. Strive for such intention will result in superfluous resources employment which will be an inefficient approach. That is why the allowable time to crash an activity has a limit. We need a second set of constraints to restrict the number of periods by which an activity can be crashed using the crash time limits given in Table-2. We can write these constraints as: Ca <= 0 Cb <= 4 Cc <= 4.5 Cd <= 4 Ce < = 5.5 Cf <= 2 Cg <= 2 Ch <= 4 Ci <= 3 Cj <= 8 Ck <= 7 Cl <= 2.5 Cm <= 1.5 Table-4: Crash Time Constraints
3) Project Completion Constraints:
This constraint will recognize that the last event (completion of last activities) must take place before the project deadline date. In this case, Activity M, the last activity in the project starts at Tm. The normal duration for activity M is 3 days, and Cm denotes the number of days by which its duration can be crashed. Hence, the actual duration of activity M is (3-Cm), and its completion time is (Tm+3-Cm). This constraint can be written as:
Tm+3-Cm <= 44 i.e. Tm-Cm <= 41
[64 is normal project duration. As per customer it should be reduced by 20 days, hence the last activity M completion time should be <= 64-20 = 44 days.]
4) Non-Negativity Constraints:
All Ti and Ci >= 0
2.3
Excel Solution.
Tale-5: Excel Solution So, the activity B, C, D, F and K are required to be crashed by 4.0, 4.5, 4.0, 0.5 and 7.0 days respectively to complete the total project within stipulated 41 days. The total cost for crashing will be $7252.
2.3.1 Excel Solution Embedded:
D : \ X LR I - P G C B M \ O R \ P r o j e ct \ P ro je c t _ v 4 . x ls
3.
3.1
Analysis:
Sensitivity Analysis: Objective Function
As the solution provide us the starting time of the activities, this can be used for monitoring the project. The sensitivity analysis generated from model solution also provide us the upper limit and lower limit of the variable coefficient of the objective function within which solution would remain optimum. In this example, the final value of variable Cb in the objective function is 4.0. The current coefficient of the variable is 500, allowable increase is 0 and allowable decrease is Infinity. It indicates that current solution would remain optimum if crash cost per unit of time for activity B varies from 500 to Infinity. The reduced cost of the non-basic variables (the variables whose value is zero in the optimum solution) provide us the information about how much objective coefficients of these variables should be reduced to have a positive value of those variables in the optimum solution. In this example, reduced cost of a current non-basic variable Ce is 45. It means the current coefficient of this variable which is now 545 must reduce 45 (that means the coefficient would be 45 or below) to get a basic (positive) value of this variable in the optimum solution (see embedded excel sheet).
3.2
Sensitivity Analysis: Right Hand Side of the constraints
Right hand sensitivity of the constraints provides us information regarding the status of the constraints; which of these constraints are binding (fully utilized) or non-binding. Binding constraints having a value in the shadow price column (see embedded excel sheet) other than zero, means how much contribution these binding constraints will provide individually in the objective function, if the value of the right hand side of these constraints are increased by 1 unit.
For e.g. In this problem, for the precedence constraint A?B, if the duration of the activity A is increased by one unit (1 day) from 4 to 5 days, the overall cost of the project will increase by $500. The value is valid for an increase of up to 1.5 days and decrease by 0.5 days. In contrast, for the Crash constant for activity C (Cc), an increase in duration of this crash time by one unit (1 day) from 4.5 to 5.5 days will cause overall cost of the project to be reduced by $277.8. The value is valid for an increase of up to 0.5 days and decrease by 1.5 days. So, this concludes that liner programming model will help Project Manger to reach the optimality where as sensitivity analysis would provide some flexibility in the model.
doc_323247455.rtf
The objective of this assignment was to identify any real world problem in the industry you are working and try to solve it using OR.
OPERATIONAL RESEARCH (OR)
ASSIGNMENT XLRI-PGCBM-18
Table of Contents
1. PROBLEM: ............................................................................................................................................................1 2. SOLUTION:............................................................................................................................................................2 2.1 MANUAL APPROACH...............................................................................................................................................2 2.2 LINEAR PROGRAMMING APPROACH.............................................................................................................................2 2.2.1 Decision Variables:....................................................................................................................................3 2.2.2 Objective Function:....................................................................................................................................3 2.2.3 Constraints:................................................................................................................................................3 2.3 EXCEL SOLUTION....................................................................................................................................................6 2.3.1 Excel Solution Embedded: .....................................................................................................................7 3. ANALYSIS:.............................................................................................................................................................7 3.1 SENSITIVITY ANALYSIS: OBJECTIVE FUNCTION ...........................................................................................................7 3.2 SENSITIVITY ANALYSIS: RIGHT HAND SIDE OF THE CONSTRAINTS..................................................................................7
1.
Problem:
Mr. Ramesh Chandra is a Software Development Project Manager in one of the renowned Indian Software Services Company, namely “ABC Technologies”. The company’s business division has recently won a project from a major European telecom company. This Project is very important for the “ABC Technologies” as it is first time the company is entering in the telecom sector for the software services. The “ABC Technologies” has been given whole end to end responsibility for this software package from Requirement Analysis till final Deployment. Customer has communicated recently to the business director of “ABC Technologies” that they would like to see the final Project Plan with a Breakdown of the tasks, Total Cost of the Project and Total duration of the Project by end of next week. “ABC Technologies” management has decided to assign Ramesh Chandra as the Project Manager for this Project and has been told to come up with the Project Plan so that they can share it with the Customer by end of next week. Ramesh has already been provided with all the required inputs so that he can be prepared for the plan. Mr. Ramesh worked very hard and came up with the following plan.
Table-1: Initial Plan Durations and Effort are here in Person Days (pdays). AS per this plan, Activities/Tasks A-B-C-D-E-F-H-I-L-M are on Critical Path and the Project duration comes to 64 days. The Total Cost of the Project comes to $20,000. During the plan discussion with the customer, customer commented that the duration of 64 days for this project is not acceptable to them and they would like the project duration be reduced by at least 20 days with a very minimal extra cost impact. Ramesh agreed during the meeting that he would try to reduce the duration and will come up with the new plan in a couple of days.
2.
Solution:
Being a Project Manager, Ramesh knows that Project time cam be reduced by a technique called Crashing which takes care to reduce the duration on a minimal extra cost. To start the Crashing, Ramesh needs to know how much time each activity can be crashed to and how much it will cost. He starts this activity and comes with the following analysis for each activity. Durations and Effort are here in Person Days (pdays).
Table-2: Plan with Crash Time and Crash Cost against each activity. There are two approaches to the problem:
2.1
Manual Approach
For crashing project time, the first task is to identify the normal critical path and the critical activities. Then it is required to determine the crash cost per time period (cost-time slopes) for various activities. The cost-time slopes can be computed using the following formula: Slope = Crash Cost – Normal Cost -------------------------------------Normal Time –Crash Time
The next step is to identify the activity on the critical path with the smallest crash cost per time period. This activity will be crashed to the maximum possible extent or to the point at which management’s desired deadline has been reached. Then it should be checked that the critical path that were being crashed is still critical. If the path is still critical then crash the activity that has second lowest cost-time slopes and continue this process until the goal has been reached. If, a reduction in a critical activity time causes a non-critical path or paths to become critical, then the crash will be continued along with the new critical path based on the lowest cost time slopes of the new path.
2.2
Linear programming approach
The linear programming is a tool for decision making under certain situation. So, the basic assumption of this approach is that to know some relevant data with certainty. The basic data requirements are as follows: 1) To know the project network with activity time, and their precedence sequence. 2) To what extent an activity can be crashed. 3) The crash cost associated with per unit of time for all activities. These requirements are identified in Table-2. Now let’s define the variable of the problem.
2.2.1 Decision Variables: Ti = Time at each activity “i”, starts. Ci = Number of periods (days in this case) by which an activity “i”, is crashed. 2.2.2 Objective Function:
The objective function here is to minimize the total cost of crashing the project down to 47 (64-20 = 44) days. Using the crash cost per week computed in Table-2. The Crash Cost per week per activity is computed using following formula: Crash Cost – Normal Cost -------------------------------Normal Time –Crash Time So the objective function can be expressed as follows. For each activity “i”, following two variables can be defined.
MIN (Z) = $0Ca+ $500Cb +$222Cc +$500Cd +$545Ce +$500Cf +$500Cg +$500Ch +667Ci+250Cj+ $286Ck + $400Cl +$667Cm 2.2.3 Constraints:
This objective function is subject to some constraints. These constraints can be classified in to three categories.
1) Precedence Constraints:
These set of constraints describe the structure of the network. As we know, the activities of a project are interrelated, the starting of some activities is dependent upon the completion of some other activities; we must have to establish work sequence of the activities through constraints. For this problem the precedence constraints are defined as below: The precedence for each activity is given in below Table-3 in column “Predecessors”
Table-3: Precedence Relationship of the Activities
Fig-1: Project Network Diagram
A->B B->C C->D C->K C->J D->E E->F E->K E->G E->J F->H H->I G->I I->L J->L K->L L->M Tb >= Ta + 4-Ca Tc >= Tb + 8Cb Td>= Tc+9Cc Tk >= Tc+9Cc Tj >= Tc+9Cc Te >=Td+6Cd Tf >= Te+11Ce Tk >= Te+11Ce Tg>= Te+11Ce Tj >= Te+11Ce Th >= Tf + 4Cf Ti >= Th + 8Ch Ti >= Tg + 4Cg Tl >= Ti + 6Ci Tl >= Tj + 16Cj Tl >= Tk + 14-Ck Tm >= Tl + 5-Cl written as Tb-Ta+ Ca >=4. i.e . i.e . i.e . i.e . i.e . i.e . i.e . i.e . i.e . i.e . i.e . i.e . i.e . i.e . i.e . i.e . i.e . Tb-Ta+ Ca >=4 Tc-Tb+ Cb >=8 Td - Tc + Cc >=9 Tk - Tc + Cc>=9 Tj – Tc + Cc>=9 Te – Td + Cd>=6 Tf - Te + Ce >=11 Tk – Te + Ce >=11 Tg - Te + Ce >=11 Tj – Te + Ce >=11 Th - Tf + Cf >= 4 Ti – Th + Ch >=8 Ti - Tg + Cg >=4 Tl – Ti + Ci >=6 Tl – Tj + Cj >=16 Tl – Tk + Ck>=14 Tm - Tl + Cl >=5
Table-4: Precedence Constraints For e.g. consider the precedence relationship between activities A and B. Activity A starts at time Ta and its duration is (4-Ca) days where Ca is the duration activity A can be crashed. Hence activity A finishes at time (Ta+4Ca).This implies that activity B start time (Tb) can be no earlier than (Ta+4Ca). It can be expressed mathematically as: Tb >= Ta + 4-Ca , it can also be
In a similar fashion, precedence relationship of all other activities are expressed in Table-4
2) Crash Time Constraints:
We can reduce the time to complete an activity by simply increasing the resources or by improving the productivity which also require the commitment of additional resources. But it is not possible to reduce the time required to complete an activity after a certain threshold limit. Strive for such intention will result in superfluous resources employment which will be an inefficient approach. That is why the allowable time to crash an activity has a limit. We need a second set of constraints to restrict the number of periods by which an activity can be crashed using the crash time limits given in Table-2. We can write these constraints as: Ca <= 0 Cb <= 4 Cc <= 4.5 Cd <= 4 Ce < = 5.5 Cf <= 2 Cg <= 2 Ch <= 4 Ci <= 3 Cj <= 8 Ck <= 7 Cl <= 2.5 Cm <= 1.5 Table-4: Crash Time Constraints
3) Project Completion Constraints:
This constraint will recognize that the last event (completion of last activities) must take place before the project deadline date. In this case, Activity M, the last activity in the project starts at Tm. The normal duration for activity M is 3 days, and Cm denotes the number of days by which its duration can be crashed. Hence, the actual duration of activity M is (3-Cm), and its completion time is (Tm+3-Cm). This constraint can be written as:
Tm+3-Cm <= 44 i.e. Tm-Cm <= 41
[64 is normal project duration. As per customer it should be reduced by 20 days, hence the last activity M completion time should be <= 64-20 = 44 days.]
4) Non-Negativity Constraints:
All Ti and Ci >= 0
2.3
Excel Solution.
Tale-5: Excel Solution So, the activity B, C, D, F and K are required to be crashed by 4.0, 4.5, 4.0, 0.5 and 7.0 days respectively to complete the total project within stipulated 41 days. The total cost for crashing will be $7252.
2.3.1 Excel Solution Embedded:
D : \ X LR I - P G C B M \ O R \ P r o j e ct \ P ro je c t _ v 4 . x ls
3.
3.1
Analysis:
Sensitivity Analysis: Objective Function
As the solution provide us the starting time of the activities, this can be used for monitoring the project. The sensitivity analysis generated from model solution also provide us the upper limit and lower limit of the variable coefficient of the objective function within which solution would remain optimum. In this example, the final value of variable Cb in the objective function is 4.0. The current coefficient of the variable is 500, allowable increase is 0 and allowable decrease is Infinity. It indicates that current solution would remain optimum if crash cost per unit of time for activity B varies from 500 to Infinity. The reduced cost of the non-basic variables (the variables whose value is zero in the optimum solution) provide us the information about how much objective coefficients of these variables should be reduced to have a positive value of those variables in the optimum solution. In this example, reduced cost of a current non-basic variable Ce is 45. It means the current coefficient of this variable which is now 545 must reduce 45 (that means the coefficient would be 45 or below) to get a basic (positive) value of this variable in the optimum solution (see embedded excel sheet).
3.2
Sensitivity Analysis: Right Hand Side of the constraints
Right hand sensitivity of the constraints provides us information regarding the status of the constraints; which of these constraints are binding (fully utilized) or non-binding. Binding constraints having a value in the shadow price column (see embedded excel sheet) other than zero, means how much contribution these binding constraints will provide individually in the objective function, if the value of the right hand side of these constraints are increased by 1 unit.
For e.g. In this problem, for the precedence constraint A?B, if the duration of the activity A is increased by one unit (1 day) from 4 to 5 days, the overall cost of the project will increase by $500. The value is valid for an increase of up to 1.5 days and decrease by 0.5 days. In contrast, for the Crash constant for activity C (Cc), an increase in duration of this crash time by one unit (1 day) from 4.5 to 5.5 days will cause overall cost of the project to be reduced by $277.8. The value is valid for an increase of up to 0.5 days and decrease by 1.5 days. So, this concludes that liner programming model will help Project Manger to reach the optimality where as sensitivity analysis would provide some flexibility in the model.
doc_323247455.rtf