Courses

# PPT: Assignment Model Mechanical Engineering Notes | EduRev

## Mechanical Engineering : PPT: Assignment Model Mechanical Engineering Notes | EduRev

``` Page 1

WHAT IS ASSIGNMENT PROBLEM ?
•
Assignment problem refers to special class of linear
programming problems that involves determining the most
efficient assignment of people to projects, salespeople to
territories, contracts to bidders  and so on.
•
It is often used to minimize total cost or time of performing
•
One important characteristic of assignment problems is
that only one job (or worker) is assigned to one machine
(or project).
Page 2

WHAT IS ASSIGNMENT PROBLEM ?
•
Assignment problem refers to special class of linear
programming problems that involves determining the most
efficient assignment of people to projects, salespeople to
territories, contracts to bidders  and so on.
•
It is often used to minimize total cost or time of performing
•
One important characteristic of assignment problems is
that only one job (or worker) is assigned to one machine
(or project).
WHAT IS ASSIGNMENT PROBLEM ?
•
Each Assignment problem has a Matrix associated with it.
•
The number in the table indicates COST associated with
the assignment.
•
The most efficient linear programming algorithm to find
optimum solution to an assignment problem is Hungarian
Method (It is also know as Flood’s Technique).
Page 3

WHAT IS ASSIGNMENT PROBLEM ?
•
Assignment problem refers to special class of linear
programming problems that involves determining the most
efficient assignment of people to projects, salespeople to
territories, contracts to bidders  and so on.
•
It is often used to minimize total cost or time of performing
•
One important characteristic of assignment problems is
that only one job (or worker) is assigned to one machine
(or project).
WHAT IS ASSIGNMENT PROBLEM ?
•
Each Assignment problem has a Matrix associated with it.
•
The number in the table indicates COST associated with
the assignment.
•
The most efficient linear programming algorithm to find
optimum solution to an assignment problem is Hungarian
Method (It is also know as Flood’s Technique).
ASSIGNMENT PROBLEM USING HUNGARIAN METHOD
•
The Hungarian method is a combinatorial
optimization algorithm that solves the assignment
problem in polynomial time and which anticipated
later primal-dual methods.
•
It was developed and published in 1955 by Harold
Kuhn, who gave the name "Hungarian method"
because the algorithm was largely based on the earlier
works of two Hungarian mathematicians: Denes Konig
and Jeno Egervary.
Page 4

WHAT IS ASSIGNMENT PROBLEM ?
•
Assignment problem refers to special class of linear
programming problems that involves determining the most
efficient assignment of people to projects, salespeople to
territories, contracts to bidders  and so on.
•
It is often used to minimize total cost or time of performing
•
One important characteristic of assignment problems is
that only one job (or worker) is assigned to one machine
(or project).
WHAT IS ASSIGNMENT PROBLEM ?
•
Each Assignment problem has a Matrix associated with it.
•
The number in the table indicates COST associated with
the assignment.
•
The most efficient linear programming algorithm to find
optimum solution to an assignment problem is Hungarian
Method (It is also know as Flood’s Technique).
ASSIGNMENT PROBLEM USING HUNGARIAN METHOD
•
The Hungarian method is a combinatorial
optimization algorithm that solves the assignment
problem in polynomial time and which anticipated
later primal-dual methods.
•
It was developed and published in 1955 by Harold
Kuhn, who gave the name "Hungarian method"
because the algorithm was largely based on the earlier
works of two Hungarian mathematicians: Denes Konig
and Jeno Egervary.
REQUIREMENTS OF DUMMY ROWS AND
COLUMN
•
To arrive at the solution, assignment problems requires
equal number of Row and Column.
•
If the number of task that needs to be done exceeds the
number of resource  available, dummy row or a column
just needs to be added as the case may be.
•
This creates a table of equal dimensions.
•
The dummy row or column is non existent . Hence the
value can be entered as Zeros.
Page 5

WHAT IS ASSIGNMENT PROBLEM ?
•
Assignment problem refers to special class of linear
programming problems that involves determining the most
efficient assignment of people to projects, salespeople to
territories, contracts to bidders  and so on.
•
It is often used to minimize total cost or time of performing
•
One important characteristic of assignment problems is
that only one job (or worker) is assigned to one machine
(or project).
WHAT IS ASSIGNMENT PROBLEM ?
•
Each Assignment problem has a Matrix associated with it.
•
The number in the table indicates COST associated with
the assignment.
•
The most efficient linear programming algorithm to find
optimum solution to an assignment problem is Hungarian
Method (It is also know as Flood’s Technique).
ASSIGNMENT PROBLEM USING HUNGARIAN METHOD
•
The Hungarian method is a combinatorial
optimization algorithm that solves the assignment
problem in polynomial time and which anticipated
later primal-dual methods.
•
It was developed and published in 1955 by Harold
Kuhn, who gave the name "Hungarian method"
because the algorithm was largely based on the earlier
works of two Hungarian mathematicians: Denes Konig
and Jeno Egervary.
REQUIREMENTS OF DUMMY ROWS AND
COLUMN
•
To arrive at the solution, assignment problems requires
equal number of Row and Column.
•
If the number of task that needs to be done exceeds the
number of resource  available, dummy row or a column
just needs to be added as the case may be.
•
This creates a table of equal dimensions.
•
The dummy row or column is non existent . Hence the
value can be entered as Zeros.
Case Study:
A company has a five job to be done by 5 workers each
worker are assigned to one and only one job. Number of
hours each worker takes to complete a job is given with
A J1 J2 J3 J4 J5
W1 28 27 24 35 38
W2 26 24 23 32 39
W3 18 20 22 30 32
W4 27 30 25 24 27
W5 29 31 28 40 36
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

## Manufacturing and Industrial Engineering

91 videos|52 docs|59 tests

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;