Consider n machines M1, M2, ... , Mn and n different jobs J1, J2, .... , Jn. These jobs to be processed by the machines one to one basis i.e., each machine will process exactly one job and e ach job will be assigned to only one machine. For each job the processing cost depends on t he machine to which it is assigned. Now we have to determine the assignment of the jobs to the machines one to one basis such that the total processing cost is minimum. This is called an assignment problem.

If the number of machines is equal to the number of jobs then the above problem is called

balanced or standard assignment problem. Otherwise, the problem is called unbalanced or non standard assignment problem. Let us consider a balanced assignment problem.

For linear programming problem formulation, l et us define the decision variables as

X_ij = {1, if job j is assigned t o machine i

0, otherwise

and the cost of processing job j on machine i as c_ij. Then we can formulate the assignment problem as follows :

subject to,

Σx_ij = 1,           i = 1, 2, ... , n

(E ach job is assigned exactly t o one machine)

Σx_ij = 0 or 1 for all i and j

In matrix form,           Minimize z = Cx

subject to, Ax = 1,

x_ij = 0 or 1, i, j = 1, 2, .... , n.

where A is a 2n * n² matrix and total unimodular i.e., the determinant of every sub square matrix formed from it has value 0 or 1. This property permits us to replace the constraint x_ij = 0 or 1 by the constraint x_ij ≥ 0. Thus we obtain

Minimize z = Cx

subject to, Ax = 1, x ≥ 0

The dual of (1) with the non-negativity restrictions replacing the 0-1 constraints can be written as follows :

subject to, ui + vj ≤ c_ij,                       i, j = 1, 2, . ... , n.

ui, vj unrestricted in signs                  i, j = 1, 2, . ... , n.

Example 1. A company is facing the problem of assigning four operators to four machines. The assignment cost in rupees in given below :

In the above, operators I and III cannot be assigned to the machines M3 and M4 respectively. Formulate the above problem as a LP model.

Solution.

Let       x_ij = { 1, if the ith operator is assigned to jth machine

0, otherwise

i, j = 1, 2, 3, 4.

be the decision variables.

By the problem,  x13 = 0 and x34 = 0.

The LP model is given below :

Minimize z = Sx₁₁ + 7x₁₂ + 4x₁₄ + 7x₂₁ + Sx₂₂ + 3x₂₃ + 2x₂₄

+ 9x₃₁ + 4x₃₂ + 6x₃₃ + 7x₄₁ + 2x₄₂ + 7x₄₃ + 6x₄₄

subject to,

(Operator assignment constraints)

X11+ X12 + X14 =1

X21 + X22 + X23 + X24 =1

X31 + X32 + X33 = 1

X41 + X42 + X43 + X44 = 1

(Machine assignment constraints)

X11 + x21 + x3l + x41 = 1

X12 + X22 + X32 + X42 =1

X23 + X33 + X43 =1

X14 + X24 + X44 =1

Xij ≥ 0 for all i and j.