PPT: Assignment Model | Industrial Engineering - Mechanical Engineering PDF Download

 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 
task.
•
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 
task.
•
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 
task.
•
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 
task.
•
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 
task.
•
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