Definition and formulation of Assignment Problem

Definition and formulation

Consider the problem of assigning n jobs to n machines (one job to one machine). Let C_ij be the cost of assigning i^th job to the j^th machine and x_ij represents the assignment of i^th job to the j^th machine.

 x_ij is missing in any cell means that no assignment is made between the pair of job and machine.(i.e) x_ij = 0.

x_ij presents in any cell means that an assignment is made their.In such cases x_ij = 1

The assignment model can be written in LPP as follows

Subject to the constrains

Note

The optimum assignment schedule remains unaltered if we add or subtract a constant from all the elements of the row or column of the assignment cost matrix.

Note

If for an assignment problem all C_ij > 0 then an assignment schedule (x_ij) which satisfies ∑ C_ij x_ij  = 0 must be optimal.