Assignment Problem

Assignment problem is one of the special cases of transportation problems. The goal of the assignment problem is to minimize the cost or time of completing a number of jobs by a number of persons. An important characteristic of the assignment problem is the number of sources is equal to the number of destinations .It is explained in the following way.

1. Only one job is assigned to person.

2. Each person is assigned with exactly one job.

Management has faced with problems whose structures are identical with assignment problems.

Ex: A manager has five persons for five separate jobs and the cost of assigning each job to each person is given. His goal is to assign one and only job to each person in such a way that the total cost of assignment is minimized.

Balanced assignment problem: This is an assignment where the number of persons is equal to the number of jobs.

Unbalanced assignment problem: This is the case of assignment problem where the number of persons is not equal to the number of jobs. A dummy variable, either for a person or job ( as it required) is introduced with zero cost or time to make it a balanced one.

Dummy job/ person: Dummy job or person is an imaginary job or person with zero cost or time introduced in the unbalanced assignment problem to make it balanced one .

An infeasible Assignment: Infeasible assignment occurs when a person is incapable of doing certain job or a specific job cannot be performed on a particular machine. These restrictions should be taken in to account when finding the solutions for the assignment problem to avoid infeasible assignment.

Hungarian method: Assignment problems can be formulated with techniques of linear programming and transportation problems. As it has a special structure, it is solved by the special method called Hungarian method. This method of assignment problem was developed by a Hungarian mathematician D. Konig and is therefore known as Hungarian method of assignment problem.

To solve assignment problem using this method, one should know time of completion or cost of making all the possible assignments. Each assignment problem has a table, persons one wishes to assign are represented in the rows and jobs or tasks to be assigned are expressed in the columns. Cost for each particular assignment is in the numbers in the table. It is referred as cost matrix. Hungarian method is based on the principle that if a constant is added to the elements of cost matrix, the optimum solution of the assignment problem is the same as the original problem. Original cost matrix is reduced to another cost matrix by adding a constant value to the elements of rows and columns of cost matrix where the total completion time or total cost of an assignment is zero. This assignment is also referred as the optimum solution since the optimum solution remains unchanged after the reduction.

ormulation of Assignment problem: Suppose there are r m laborers to whom n tasks are assigned. No labour can be either left idle or given more than one job. take up more than one job an

This method is based on the principle

This method was developed by D. Konig, a Hungarian mathematician and is therefore known as the Hungarian method of assignment problem. In order to use this method, one needs to know only the cost of making all the possible assignments. Each assignment problem has a matrix (table) associated with it. Normally, the objects (or people) one wishes to assign are expressed in rows, whereas the columns represent the tasks (or things) assigned to them. The number in the table would then be the costs associated with each particular assignment. It may be noted that the assignment problem is a variation of transportation problem with two characteristics.(i)the cost matrix is a square matrix, and (ii)the optimum solution for the problem would be such that there would be only one assignment in a row or column of the cost matrix .

Mathematical
Although assignment problem can be formulated as linear programming problem, solution can be found out by using Hungarian bm .

ization Methods: Linear Programming Applications – Assignment Problem 2

1. Each machine is assigned not more than one job.

2. Each job is assigned to exactly one machine.

Because of this special structure, solution of the assignment problems can be found out using Hungarian method .

Formulation of assignment problem: Consider m laborers to whom n tasks are assigned. No laborer can either sit idle or do more than one task. Every pair of person and assigned work has a rating. This rating may be cost, satisfaction, penalty involved or time taken to finish the job. There will be N2 such combinations of persons and jobs assigned. Thus, the optimization problem is to find such man- job combinations that optimize the sum of ratings among all. The formulation of this problem as a special case of transportation problem can be represented by treating laborers as sources and the tasks as destinations. The supply available at each source is 1 and the demand required at each destination is 1.The cost of assigning (transporting) laborer i to task j is cij. It is necessary to first balance this problem by adding a dummy laborer or task depending on whether mn, respectively. The cost coefficient cij for this dummy will be zero.

Let 1111,2,...11,2,...nijinijjxforjnxforim=====££ 10orxij=

Due to the special structure of the assignment problem, the solution can be found out using a more convenient method called Hungarian method which will be illustrated through an example below. Assignment problem can be formulated as a linear programming problems