Assignment Problems Linear Programming

The assignment problem is a special type of transportation problem, where the objective is to minimize the cost or time of completing a number of jobs by a number of persons.

In other words, when the problem involves the allocation of n different facilities to n different tasks, it is often termed as an assignment problem.

The model's primary usefulness is for planning. The assignment problem also encompasses an important sub-class of so-called shortest- (or longest-) route models. The assignment model is useful in solving problems such as, assignment of machines to jobs, assignment of salesmen to sales territories, travelling salesman problem, etc.

It may be noted that with n facilities and n jobs, there are n! possible assignments. One way of finding an optimal assignment is to write all the n! possible arrangements, evaluate their total cost, and select the assignment with minimum cost. But, due to heavy computational burden this method is not suitable. This chapter concentrates on an efficient method for solving assignment problems that was developed by a Hungarian mathematician D.Konig.

"A mathematician is a device for turning coffee into theorems." -Paul Erdos

Formulation of an assignment problem

Suppose a company has n persons of different capacities available for performing each different job in the concern, and there are the same number of jobs of different types. One person can be given one and only one job. The objective of this assignment problem is to assign n persons to n jobs, so as to minimize the total assignment cost. The cost matrix for this problem is given below:

The structure of an assignment problem is identical to that of a transportation problem.

To formulate the assignment problem in mathematical programming terms, we define the activity variables as

xij = 1 if job j is performed by worker i
0 otherwise

for i = 1, 2, ..., n and j = 1, 2, ..., n

In the above table, cij is the cost of performing jth job by ith worker.

Generalized Form of an Assignment Problem

The optimization model is

Minimize c11x11 + c12x12 + ------- + cnnxnn

subject to
xi1 + xi2 +..........+ xin = 1          i = 1, 2,......., n
x1j + x2j +..........+ xnj = 1          j = 1, 2,......., n

xij = 0 or 1

In Σ Sigma notation

minimize cijxij

subject to

xij = 1 for i = 1, 2, ....., n

xij = 1 for j = 1, 2, ....., n

xij = 0 or 1 for all i and j

An assignment problem can be solved by transportation methods, but due to high degree of degeneracy the usual computational techniques of a transportation problem become very inefficient. Therefore, a special method is available for solving such type of problems in a more efficient way.

Assumptions in Assignment Problem

  • Number of jobs is equal to the number of machines or persons.
  • Each man or machine is assigned only one job.
  • Each man or machine is independently capable of handling any job to be done.
  • Assigning criteria is clearly specified (minimizing cost or maximizing profit).

Share this article with your friends

A linear programming model can be used to solve the assignment problem. Consider the example shown in the previous table, to develop a linear programming model.
Let,

x11 represent the assignment of operator A to job 1
x12 represent the assignment of operator A to job 2
x13 represent the assignment of operator A to job 3
x21 represent the assignment of operator B to job 1
and so on.

Formulating the equations for the time taken by each operator,
10 x11 + 16 x12 + 7 x13 = time taken by operator A.
9 x21 + 17 x22 + 6 x23 = time taken by operator B.
6 x31 + 13 x32 + 5 x33 = time taken by operator C.

The constraint in this assignment problem is that each operator must be assigned to only one job and similarly, each job must be performed by only one operator. Taking this constraint into account, the constraint equations are as follows:

x11 + x12 + x13< 1 operator A
x21 + x22 + x23< 1 operator B
x31 + x32 + x33< 1 operator C
x11 + x21 + x31 = 1 Job 1
x12 + x22 + x32 = 1 Job 2
x13 + x23 + x33 = 1 Job 3

Objective function: The objective function minimizes the time taken to complete all the jobs. Using the cost data table, the following equation can be arrived at:

The objective function is,
Minimize Z = 10 x11 + 16 x12 + 7 x13 +9 x21 + 17 x22 + 6 x23 +6 x31 + 13 x32 + 5 x33

The linear programming model for the problem will be,

Minimize Z = 10 x11 + 16 x12 + 7 x13 +9 x21 + 17 x22 + 6 x23 +6 x31 + 13 x32 + 5 x33

subject to constraints

x11 + x12 + x13< 1 ....................(i)
x21 + x22 + x23< 1 ....................(ii)
x31 + x32 + x33< 1 ....................(iii)
x11 + x12 + x13 = 1 ....................(iv)
x12 + x22 + x32 = 1 ....................(v)
x13 + x23 + x33 = 1 ....................(vi)
where, xij> 0 for i = 1,2,3 and j = 1,2,3.

The problem is solved on a computer, using transportation model in TORA package. The input screen and output screens are shown in the previous and following figures respectively.

TORA, Input Screen


TORA, Output Screen

The objective function value = 28 mins.

The Assignment Schedule

One thought on “Assignment Problems Linear Programming

Leave a Reply

Your email address will not be published. Required fields are marked *