9.2 The Assignment Problem
The assignment problem refers to the class of LP problem that involves determining the most efficient assignment of people to projects, salespeople to territories, auditors to companies for audits, contracts to bidders, jobs to machines, heavy equipment (such as cranes) to construction jobs, and so on. The objective is most often to minimize total cost or total time of performing the tasks at hand. One important characteristic of assignment problems is that only one job or worker is assigned to one machine or project.
Figure 9.2 provides a network representation of an assignment problem. Notice that this network is very similar to the network for the transportation problem. In fact, an assignment problem may be viewed as a special type of transportation problem in which the supply at each source and the demand at each destination must equal one. Each person may be assigned to only one job or project, and each job needs only one person.
Figure 9.2 Example of an Assignment Problem in a Transportation Network Format
Linear Program for Assignment Example
The network in Figure 9.2 represents a problem faced by the Fix-It Shop, which has just received three new repair projects that must be completed quickly: (1) a radio, (2) a toaster oven, and (3) a coffee table. Three repair persons, each with different talents, are available to do the jobs. The shop owner estimates the cost in wages if one worker is assigned to each of the three projects. The costs differ due to the talents of each worker. The owner wishes to assign the jobs so that total cost is minimized, each job has one person assigned to it, and each person is assigned to only one job.
In formulating this as a linear program, the general LP form of the transportation problem can be used. In defining the variables, let
where
The LP formulation is
subject to
The solution is shown in Program 9.4. From this, so Adams is assigned to project 3; so Brown is assigned to project 2; and so Cooper is assigned to project 1. All other variables are 0. The total cost is $25.
Program 9.4 Mr. Fix-It Shop Assignment Solution in Excel 2016 Using Excel QM
This problem could be input into Excel, Excel QM, or QM for Windows as a linear program, or it could be input as a transportation problem with all supplies and demands equal to 1. However, both Excel QM and QM for Windows have a module for this assignment problem. In Excel QM, from the Alphabetical menu on the Excel QM ribbon, select Assignment. The initialization window opens, and you enter the number of assignments and select Minimization. Click OK, and a worksheet opens for you to enter the costs as shown in the Data table in Program 9.4. Then select Solver from the Data ribbon, and click Solve in the Solver input window. The results are shown in Program 9.4.
The software for the assignment problem assumes that the problem is balanced, which means that the number of sources (or people) is equal to the number of destinations (or jobs). If the problem is not balanced, a dummy source or a dummy destination is added to the problem to make it balanced. In some cases, more than one dummy source or destination is used. Because this dummy is not a real assignment and indicates only which source or destination will be lacking an assignment, all costs are zero. Solved Problem 9.2 at the end of the chapter illustrates this.
In the assignment problem, the variables are required to be either 0 or 1. Due to the special structure of this problem, with the constraint coefficients as 0 or 1 and all the right-hand-side values equal to 1, the problem can be solved as a linear program. The solution to such a problem (if one exists) will always have the variables equal to 0 or 1. There are other types of problems where the use of such 0 and 1 variables is desired, but the solution to such problems using normal linear programming methods will not necessarily have only zeros and ones. In such cases, special methods must be used to force the variables to be either 0 or 1, and this will be discussed as a special type of integer programming problem in Chapter 10.