Definition of Assignment Model

Let us consider one assignment problem that includes ‘n’ resources for ‘n’ destinations. The objective of finding the solution is to determine the maximization or minimization. It means the maximization of total profit and minimization of total time taken to complete each and every task (‘n’ tasks).

For the formulating of assignment models, following assumptions should be considered:

1. Each resource should be assigned to only one task
2. Each task should be assigned to one resource

• To find out the solution, the available number of resources must be equal to total numbers of tasks to be performed.

Let _ijbe any variable then;

_Xij        =         (1 if resource I is assigned to task j @0 if resource I is not assigned to task j)

C_ij        =          Objective function contribution if resource is assigned to task j

n          =          Number of resources and the number of tasks

Now, As only one job is assigned to one resource then, it can be written as,

_ij= 1                   and                  _ij= 1

And the total assignment cost is given by,

Z = _ijC_ij

Hence, the mathematical formulation assumes this following form;

Determine _ij 0 (i, j = 1, 2, …..n) so as to minimize, Z = _ijC_ij subject to following constraints, i.e.;

_ij= 1       where, j = 1, 2, 3, …..n and _ij= 0 or 1

Thus,

The general assignment model can be written as,

Maximize or Minimize,

Z = C₁₁₁₁ + C₁₂₁₂ + …………+ C_1n1n + C₂₁₂₁ + ………C_nnnsubject to,

₁₁ + ₁₂ + …………+ _1n                 =          1

₂₁ + ₂₂ + …………+ _2n                 =          1

:           :                       :

:           :                       :

_n1 + _n2 + …………+ _nn                 =          1

₁₁ + ₂₁ + …………+ _n1                 =          1

₁₂ + ₂₂ + …………+ _n2                 =          1

:           :                       :

:           :                       :

_1n + _2n + …………+ _nn                 =          1

_ij= 0 or, 1 for all values of i and j

Students should notice that the variables are restricted to only two values i.e. 0 and 1 for this model. Here, 0 means non-assignment of resources and 1 means assignment of resources. This restriction is different from other Linear Programming (LP) models that we have seen so far.

Theorem 1:

The optimum assignment schedules remain unaltered if we subtract or add ant constant to/ from all the elements of row/ column of the assignment cost matrix.

Theorem 2:

For assignment problems where all C_ij 0, the assignment schedule (_ij) that satisfy _ijC_ij= 0 should be optimal.

These two theorems mentioned above are the basis of assignment algorithm. If we add/ subtract any suitable constant to/ from the elements of cost matrix, then the new C_ij 0 should produce at least one new C_ij= 0 at each row and column. And, it should try to make the assignments from these 0 positions. Thus, the assignment schedule becomes optimal if there is only one assignment in each row and column (It means exactly one should be assigned to 0).