Given jobs, resources and cost matrix, what assignment minimizes the overall cost?

Question

2	4	5	3	11
3	5	6	4	8
4	3	5	7	9
3	4	3	8	12
4	2	6	4	9

Given jobs, resources and cost matrix.....for which assignment overall cost is minimum?

Answer 1

This problem of job assignment can be done by using the branch and bound approach.

The minimum cost for assigning the jobs { j1, j2, j3, j4, j5 } to the resources { a, c, d, e, b } is achieved with a total payment of (2 + 8 + 3 + 3 + 4), resulting in a sum of 20.

Answer 2

In the enumeration tree, node (i, j) represents job i is assigned to resource j.

Lower Bound Calculation
We calculate the lower bound at a node by 2 following principles:
1. A job must be assigned to a resource.
2. A resource must be assigned with a job.

Upper Bound Calculation
Greedy: At each step, select an unselected job, assign it to the resource with minimum cost.

In the enumeration tree, if the lower bound of a node is greater than or equals the current upper bound, which means no improvement is made to a feasible solution, we do pruning.