advertisement

Assignment Problem Concepts Concepts What is the Assignment Problem? The assignment problem deals with assigning machines to tasks, workers to jobs, soccer players to positions, and so on. The goal is to determine the optimum assignment that, minimizes the total cost or maximizes the team effectiveness. Concepts What is the Assignment Problem? Suppose we have “n” resources to which we want to assign to “n” tasks on a one-to-one basis. Suppose also that we know the cost of assigning a given resource to a given task (i.e. cost matrix). We wish to find an optimal assignment - one which minimizes total cost. Assignment Example Assignment Example We have 3 workers and 3 tasks Decision: Which worker to assign to which task? Objective: Minimize cost in wages to get all 3 tasks done Estimated Wages Cost of Possible Assignments Worker Dish Washing Car Cleaning Laundry John Peter Robert Rs. 11 Rs. 8 Rs. 9 Rs. 14 Rs. 10 Rs. 12 Rs. 6 Rs. 11 Rs. 7 Assignment Example Workers (Supply) Tasks (Demand) John Dish Washing Peter Car Cleaning Robert Laundry Possible Assignments The “flow” on each arc is either “0” (false) or “1” (true) Assignment Example Decision Variables: Xij = “1” if worker “i” is assigned to task “j” , else it is “0” Objective Function: Min 11Xjd + 14Xjc + 6Xjl + 8Xpd + 10Xpc + 11Xpl + 9Xrd + 12Xrc + 7Xrl Constraints: (supply nodes) - (11Xjd + 14Xjc + 6Xjl) = - 1 - (8Xpd + 10Xpc + 11Xpl) = - 1 - (9Xrd + 12Xrc + 7Xrl) = - 1 Estimated Wages Cost of Possible Assignments Worker Dish Washing Car Cleaning Laundry John Rs. 11 Rs. 14 Rs. 6 Peter Rs. 8 Rs. 10 Rs. 11 Robert Rs. 9 Rs. 12 Rs. 7 Constraints: (demand nodes) 11Xjd + 8Xpd + 9Xrd = 1 14Xjc + 10Xpc + 12Xrc = 1 6Xjl + 11Xpl + 7Xrl = 1 Solution to the Assignment Problem There are 4 methods of solving the assignment problem: 1. Complete Enumeration Method 2. Transportation Method 3. Simplex Method 4. Hungarian Method Hungarian Method Hungarian Method Hungarian Method handles assignment method in the most efficient way. It is based on the concept of opportunity cost. Theorem: If a number is added to or subtracted from all of the entries of any one row or column of a cost matrix, then on optimal assignment for the resulting cost matrix is also an optimal assignment for the original cost matrix. Hungarian Formulation of Model The Mathematical Model: Let cij be the cost of assigning the ith resource to the jth task. the n × n matrix We define the cost matrix to be - An assignment is a set of n entry positions in the cost matrix, no two of which lie in the same row or column. - An assignment with the smallest possible cost is called an optimal assignment. Maximization / Minimization Problems • In some situations, the assignment problem may call for maximization of profit, revenue, etc. as the objective. • Examples: – Minimization: Find the optimum assignment of products to machine setups resulting in minimum cost/time. – Maximization: Find the optimum assignment of salesmen to markets resulting in maximum revenue/profits. Balanced / Unbalanced Problems • In some situations the number of supply nodes do not identically match the number of demand nodes resulting in unbalanced problems. • Examples: – Balanced: 5 workers and 5 machines – Unbalanced: 4 workers and 6 machines In unbalanced situations, either of the nodes will remain idle. Prohibited Assignment Problems • In some situations some specific supply nodes may not be able to match some specific demand nodes resulting in constrained assignment problems. • Examples: – Constrained: Worker ‘A’ cannot perform Task ‘Y’ To cope with constrained situations, the cost of performing that job by such a person is taken extremely large (which is written as “M”) Hungarian Method of Solution The Hungarian Method: The following algorithm applies the theorem to a given n × n cost matrix to find an optimal assignment. Numerical Minimization, Balanced Type Maximization, Unbalanced Problem Multiple Assignment, One Optimal Solution Constrained Assignment, Multiple Optimal Solutions