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 36Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!

91 videos|52 docs|59 tests