Learning Curve…

MB0048 : (a) Give an algorithm to solve an assignment problem. (b) Show that an assignment problem is a special case of transportation problem?

Posted on: October 4, 2011

MB0048 : (a) Give an algorithm to solve an assignment problem.
(b) Show that an assignment problem is a special case of transportation problem?

Answer: – Hungarian Method Algorithm can be used to solve assignment problem

Hungarian method algorithm is based on the concept of opportunity cost and is more efficient in solving assignment problems. Adopt the following steps mentioned below to solve an AP using the Hungarian method algorithm:

Step 1: Prepare row ruled matrix by selecting the minimum values for each row and subtract it from other elements of the row.

Step 2: Prepare column reduced matrix by subtracting minimum value of the column from the other values of that column.

Step 3: Assign zero row-wise if there is only one zero in the row and cross (cancel) (X) other zeros in that column.

Step 4: Assign column wise if there is only one zero in that column and cross other zeros in that row.

Step 5: Repeat steps 3 and 4 till all zeros are either assigned or crossed. If the number of assignments is equal to number of rows present, you have arrived at an optimal solution, if not, then proceed to step 6.

Step 6: Mark (P) the unassigned rows. Look for crossed zero in that row. Mark the column containing the crossed zero. Look for assigned zero in that column. Mark the row containing assigned zero. Repeat this process till all makings are over.

Step 7: Draw straight line through unmarked rows and marked column. The number of straight line drawn will be equal to number of assignments made.

Step 8: Examine the uncovered elements. Select the minimum.

a) Subtract it from uncovered elements.

b) Add it at the point of intersection of lines.

c) Leave the rest as it is.

d) Prepare a new table.

Step 9: Repeat steps 3 to 7 till optimum assignment is obtained.

Step 10: Repeat steps 5 to 7 till number of allocations = number of rows.

The assignment algorithm applies the concept of opportunity costs. The cost of any kind of action or decision consists of the opportunities that are sacrificed in taking that action. If we do one thing, we cannot do another.

Assignment problem is a special case of transportation problem

The assignment problem is a special case of the transportation problem, where the objective is to minimize the cost or time of completing a number of jobs by a number of persons, maximizes revenue and sales efficiently.

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. This model is mostly used for planning. The assignment model is useful in solving problems, such as assignment of machines to jobs, assignment of salesman to sales territories, travelling salesman problem and many more similar situations. 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, valuate their total cost and select the assignment model offering minimum cost. This method can be unfeasible due to involvement of computational procedures. In this unit, we will study an efficient method for solving assignment problems.

Let’s say there are ‘n’ jobs in a factory having ‘n’ machines to process the jobs. A job i (=1… n), when processed by machine j (=1… n) is assumed to incur a cost Cij. The assignment is to be made in such a way that each job can associate with one and only one machine. You can then determine an assignment of jobs to the machines to minimize the overall cost.

The cost data is given as a matrix where rows correspond to jobs and columns to machines and there are as many rows as the number of columns. The number of jobs and number of machines should be equal.

Assignment becomes a problem because each job requires different skills and the capacity or efficiency of each person with respect to these jobs can be different. This gives rise to cost differences. If each person is able to do all jobs with same efficiency then all costs will be the same and each job can be assigned to any person. When assignment is a problem it becomes a typical optimization problem. Therefore, you can compare an assignment problem to a transportation problem. The cost element is given and is a square matrix and requirement at each destination is one and availability at each origin is also one.


2 Responses to "MB0048 : (a) Give an algorithm to solve an assignment problem. (b) Show that an assignment problem is a special case of transportation problem?"

Hai thanks for the assignment of 2nd sem. could u send me the remaining paper assignment for 2nd sem which are not posted on this site. i will be thankful to u. my id is karan_singh1609@yahoo.com.

nice one….very imp…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Learning days (Calendar)

October 2011
« Sep   Nov »

Knowledge Bank (Archives)

I am on Twitter

Blog Stats

  • 498,419 hits

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 43 other followers

%d bloggers like this: