A factory has five workers, Anne, Bob, Carol, Dave and Ethan. It also has 5 tasks which must be done. Each worker does the tasks with a different efficiency. Apply the branch and bound strategy to allocate the tasks with minimum overall cost, when each task must be completed by a different worker. 

The cost for each worker to do the tasks is given in the following table:  

a) Describe a suitable method to calculate the lower bound value for all similar problems, where the total number of workers and the total number of tasks are equal?

b) Describe a method to calculate a suitable upper bound for similar problems?

c) Use the branch and bound strategy to find the most cost-efficient allocation of tasks to workers. Show the details of the expansion and pruning (branch and bound) of the decision tree along with reasons.

Transcribed Image Text:

Task 1 Task 2 Task 3 Task 4 Task 5 Anne $4.00 $8.00 $8.00 $3.00 $4.00 Bob $9.00 $5.00 $5.00 $2.00 $7.00 Carol $4.00 $2.00 $9.00 $4.00 $6.00 $1.00 $3.00 Dave $7.00 $5.00 $8.00 Ethan $3.00 $6.00 $4.00 $4.00 $5.00 Task 1 Task 2 Task 3 Task 4 Task 5 Anne $4.00 $8.00 $8.00 $3.00 $4.00 Bob $9.00 $5.00 $5.00 $2.00 $7.00 Carol $4.00 $2.00 $9.00 $4.00 $6.00 $1.00 $3.00 Dave $7.00 $5.00 $8.00 Ethan $3.00 $6.00 $4.00 $4.00 $5.00

Answer rating: 100% (QA)

a Branch and bound startegy can be used to find the upper and lower bou... View the full answer