Assignment Model Problem

Assignment Problem
A typical assignment problem, presented in the classic manner, is shown in Fig. 12. Here there are five machines to be assigned to five jobs. The numbers in the matrix indicate the cost of doing each job with each machine. Jobs with costs of M are disallowed assignments. The problem is to find the minimum cost matching of machines to jobs.
Figure 12. Matrix model of the assignment problem.
The network model is in Fig. 13. It is very similar to the transportation model except the external flows are all +1 or 1. The only relevant parameter for the assignment model is arc cost (not shown in the figure for clarity) ; all other parameters should be set to default values. The assignment network also has the bipartite structure.
Figure 13. Network model of the assignment problem.
The solution to the assignment problem as shown in Fig. 14 has a total flow of 1 in every column and row, and is the assignment that minimizes total cost.
Figure 14. Solution to the assignment Problem

The Assignment Model
The assignment model is used to solve the traditional one to one assignment problem of assigning employees to jobs, employees to machines, machines to jobs, etc. The model is a special case of the transportation method. In order to generate an assignment problem it is necessary to provide the number of jobs and machines and indicate whether the problem is a minimization or maximization problem. The number of jobs and machines do not have to be equal but usually they are.
Objective function. The objective can be to minimize or to maximize. This is set at the creation screen but can be changed in the data screen.
Example
The table below shows data for a 7 by 7 assignment problem. Our goal is to assign each salesperson to a territory at minimum total cost. There must be exactly one salesperson per territory and exactly one territory per salesperson.
Mort  Chorine  Bruce  Beth  Lauren  Eddie  Brian  
Pennsylvania  12  54  34  87  54  89  98 
New Jersey  33  45  87  27  34  76  65 
New York  12  54  76  23  87  44  62 
Florida  15  37  37  65  26  96  23 
Canada  42  32  18  77  23  55  87 
Mexico  40  71  78  76  82  90  44 
Europe  12  34  65  23  44  23  12 
The data structure is nearly identical to the structure for the transportation model. The basic difference is that the assignment model does not display supplies and demands since they are all equal to one.
The Solution
The results are very straightforward.
Assignments. The 'Assigns's in the main body of the table are the assignments which are to be made. For example, Mort is to be assigned to Pennsylvania, Chorine is to be assigned to Florida, Bruce is to be sent to Canada, Beth is to work the streets of New York, Lauren is across the river in New Jersey, Eddie works Europe and Brian will work in Mexico.
Total cost. The total cost appears in the upper left cell. In this example the total cost is given by $191.
The assignments can also be given in list form as shown below.
The marginal costs can be displayed also. For example, if we want to assign Chorine to Pennsylvania then the total will increase by $6 to $197.
NOTE: To preclude an assignment from being made (in a minimization problem) you should enter a very large cost. If you enter an 'x' then the program will place a high cost in that cell.
0 Replies to “Assignment Model Problem”