Homehork 14 Question  

A company is assembling a team to carry out a series of operations. There are four members of the team: A, B, C and D, and four operations to be carried out. Each team member can carry out exactly one operation. All four operations must be carried out successfully for the overall project to succeed, however the probability of a particular team member succeeding in a particular operation varies, as shown in the table below. For example, if the team members were assigned to operations in the order ABCD, then the overall probability of successful completion of the project is (0.9)(0.6)(0.85)(0.7) = 0.3213. If there is any possible way that the team can be arranged such that the overall probability of success exceeds 45%, then the manager will approve the project. Will the manager approve the project? If yes, what is the arrangement of the team that gives the highest probability of success?

Homehork 14 Answer  

At the root node, no decisions have been made. We will choose the best person for each of the jobs. In this case, person (A) has the best probability of success for each of the 4 operations. This gives a bounding value of: (0.9)(0.8)(0.9)(0.85)= 0.5508 We will label the root node with this solution and the bounding function value

Now, we will expand this node by branching on the first operation. Each node is labeled with the person who is assigned to operation 1 at that node. We will now evaluate the bounding function at each of these nodes.

Also, the decision has been made that person A will perform operation 1. we will indicate this by coloring A in green. Person A cannot be selected to perform any other operation because it has already been chosen.

stage 1

alt text

alt text

stage 2

The remaining people will be assigned to the remaining jobs. This is done in the same way that we have done it before. The person with the best probability for success will be chosen for the job. In the case of a tie, choose one arbitrarily. This assignment gives a bounding function value of: (0.9)(0.7)(0.85)(0.8)=0.4284  

alt text

alt text

stage 3

We will now move on to the next nodes.

alt text

alt text

stage 4

We will be branching on operation 2. There are only 3 nodes, because person C is already locked into performing operation 1.

alt text

alt text

stage 5  

This solution assigns a different person to each job, therefore, it is a feasible solution. This is our first feasible solution. We will mark this node as the incumbent. We will now evaluate the remaining nodes

alt text

alt text

stage 6

We will now choose the next node for expansion. The node selection policy we have chosen is global best. We will select the node in the decision tree that has the highest bounding function value.

alt text

alt text

stage 7

We will expand this node, branching on operation 2. Again, there are only 3 nodes, because person D is locked into performing operation 1

alt text

alt text

stage 8

This node has a bounding function value that is less than the current incumbent. This means that this node cannot produce a solution better than the current incumbent. There is no need to expand this node. It will be Pruned.

alt text

alt text

stage 9

We will now choose the node with the highest bounding function value to be expanded

alt text

alt text

stage 10

We will be branching on operation 3. There are only 2 nodes here because C and D are locked into performing operation 1 and 2 respectively. Evaluate these nodes.

alt text

alt text

stage 11

This node is a feasible solution. However, the value of the objective function is less than the current incumbent. This node will be Pruned

alt text

alt text

stage 12

This node is feasible solution and it has an objective function value greater than the current incumbent. This node will replace the current incumbent because it is a better solution.

alt text

alt text

stage 13

With the new incumbent, we can prune all the live bud nodes that have a lower bounding function value than the current incumbent.

alt text

alt text

stage 14

Since we have a tie, simply choose one arbitrarily.

alt text

alt text

stage 15

We will now evaluate these nodes.

alt text

alt text

stage 16

The value of the bounding function of all three nodes is leower than the current incumbent. These nodes will be Pruned.

alt text

alt text

stage 17

We will now expand the next node and evaluate

alt text

alt text

stage18

Pruned nodes, and expand the next node.

alt text

alt text

stage 19

Pruned nodes, and expand the next node

alt text

alt text

stage 20

Pruned nodes, and expand the next node

alt text

alt text

stage 21

Conclusion:

There are no more live buds, so we are done.
The solution is the current incumbent.
The person - operation assignment is as follows:
C - Operation 1
D - Operation 2
B - Operation 3
A - Operation 4

The probability of success of 0.4046. Because the highest probability of success is less than 0.4500 the manager will NOT approve the project

alt text

alt text