LESSON 1. Assignment problems - Introduction

Assignment problems – introduction – mathematical representation - comparison with transportation problems  - theorems of assignment problems. 

1. Introduction

The assignment problem is defined as  assigning each facility to one and only one job so as to optimize the given measures of effectiveness, when n facilities and n jobs are available and given the effectiveness of each facility for each job.

Let there be  n facilities (machines) to be assigned to n jobs. Let cij is cost of assigning ith facility to jth job and xij  represents the assignment of ith facility to jth job. If ith facility can be assigned to jth job, xij=1, otherwise zero. The objective is to make assignments that minimize the total assignment cost or maximize the total associated gain.

  161111

Thus an assignment problem can be represented by n x n matrix which continues n! possible ways of making assignments. One obvious way to find the optimal solution is to write all the n! possible arrangements, evaluate the cost of each and select the one involving the minimum cost. 

However, this enumeration method is extremely slow and time consuming even for small values of n. For example, for n = 10, a common situation, the number of possible arrangements is 10! = 3,628,800. Evaluation of so large a number of arrangements will take a probability large time. This confirms the need for an efficient computational technique for solving such problems.

 2. Mathematical Representation of Assignment Model

 Mathematically, the assignment model can be expressed as follows: 

Let xij  denote the assignment of facility i to job j such that

                        xij = 0, if the ith facility is not assigned to jth job,

                        xij = l, if the ith facility is assigned to jth job.

Then, the model is given by

             161112

            subject to constraints   

161113(one job is assigned to the ith facility)         

                        161114  (one job is assigned to the jth facility)                                                      

 

and                  xij  = 0  or 1 (or xij = xij2).

 If the last condition is replaced by xij ≥0, this will be a transportation model with all requirements and available resources equal to 1.

3. Comparison with the transportation model

An assignment model may be regarded as a special case of the transportation model. Here, facilities represent the ‘sources’ and jobs represent the ‘destinations’. Number of sources is equal to the number of destinations, supply at each source is unity (ai = 1 for all i) and demand at each destination is also unity (bj = 1, for all j). The cost of ‘transporting’ (assigning) facility i to job j is cij and the number of units allocated to a cell can be either one or zero. i.e., they are non-negative quantities.

However the transportation algorithm is not very useful to solve this model, when an assignment is made, the row as well as column requirements are satisfied simultaneously (rim conditions being always unity) resulting in degeneracy. Thus the assignment problem is a completely degenerate form of the transportation problem. In n x n problem, there will be n assignments instead of n+n–1 or 2n–1–n = n–1 epsilons which will make the computations quite cumbersome. However, the special structure of the assignment model allows a more convenient and simple method of solution.

 

Difference between the transportation problem and the assignment problem
 

Transportation Problem

Assignment Problem

(a)

Supply at any source may be any positive quantity ai

Supply at any source (machine) will be 1 i.e., ai =1.

(b)

Demand at any destination may be any positive quantity bj

Demand at any destination (job) will be 1 i.e., bj = 1.

( c)

One or more source to any number of destinations

One source (machine) to only one destination (job).

 

4. Theorems

The technique used for solving assignment model makes use of the following two theorems:

4.1. Theorem I

It states that in an assignment problem, if we add or subtract a constant to every element of a row (or column) in the cost matrix, then an assignment which minimizes the total cost on one matrix also minimizes the total cost on the other matrix”.

Let, cij represent the original cost elements of the matrix. If constants ui and vj are subtracted from the ith row jth column respectively, the new cost elements will be

161115

If Z is the original objective function, the new objective function will be


161116                          

  Now with reference,                            

                       161117

 and

                   161118

         or z' is minimum when z is minimum. This proves the theorem.

 Likewise, if in an assignment problem some cost elements are negative, we may convent them into an equivalent assignment problem where all the cost elements are non-negative by adding a suitably large constant to the elements of the relevant row.

 4.2. Theorem II

 It states “If all cij ≥ 0 and we can find a set xij=x’ij,  such that

     161119

 then this solution is optimal.

 The result follows automatically since as neither of cij is negative, the value of

              1611110             cannot be negative.

Hence, its minimum value is zero which is attained when xij=xij' . 

Thus the present solution is optimal solution.

The above two theorems indicate that if one can create a new cij' matrix with zero entries, and if these zero elements, or a subset thereof, constitute feasible solution, then this feasible solution is the optimal solution.

 Thus the method of solution consists of adding and subtracting constant from rows and columns until sufficient number of cij's become zero to yield a solution with a value of zero. 

Last modified: Thursday, 3 October 2013, 9:37 AM