Question

Explain what it means for an assignment model to be balanced. Give detailed mathematical examples.

Answer 1

What is Balanced assignment problem:

Suppose we have persons to which we want to assign jobs in such a way that each person get exactly one job(or each job goes to exactly one person). We also know the cost of assigning a given person to a given job. Our aim is to find an optimal assignment one which minimizes total cost.

Mathematical Formulation of the above problem is:

Let if job goes to person and otherwise.

be the cost when job goes to person .Note that cost can not be negative quantity, so . We define the cost matrix to be .

An assignment is a set of entry positions in the cost matrix, no two of which lies in the same row or same column

Minimize

subject to

Note: In Balanced assignment problem we got the cost matrix as square matrix. But if the problem is unbalanced the cost matrix is not square.In such problems, dummy rows (or columns) are added in the matrix so that it form a square matrix. The dummy rows or columns will contain all costs elements as zero.

Examples:

1.Balance assignment problem:

A company has four machines that are used for four jobs. Each job can be assigned to one and only one machine. The cost of each job on each machine is given in the following Table.

observe that there are 4 machines and 4 jobs that means each job goes to one machine or each machine assigns one job. So this is an example of Balanced assignment problem. The cost matrix for this problem is , which is a square matrix of order 4.

2.Unbalance assignment problem:

A company has four machines that are used for three jobs. Each job can be assigned to one and only one machine. The cost of each job on each machine is given in the following Table.

observe that each machine can not be assigned job. This is an example of unbalanced assignment problem. In this case the cost matrix is not a square matrix. In order to solve this unbalanced assignment problem first we balance it by adding a dummy row in the cost matrix C whose entries are zero..