Verbal Formulation


   Minimize the total cost it takes to perform a set of jobs

   Subject to the following requirements:
    - Each person is assigned no more than one job.
    - Each job is assigned to exactly one person.

One can imagine a number of variations on this objective or the corresponding constraints are also possible. Here are just a few possibilities some models may include (although not all at once!):

   Minimize the total time it takes to perform a set of jobs.
   Maximize the total satisfaction of the group.
   Maximize the performance of the group (based on skill levels).

   Subject to:
    - Each person is assigned no more than five jobs.
    - Each person may complete as many jobs as possible in eight hours.
    - Each job requires three people working on it.

Now, let's model a specific example. Imagine that we have a set of household jobs to be completed, and a group of available people to complete them. In order to create a mathematical version of this model, we need to define a few variables:

 
   assign(Sally, dusting)  =  "amount" of Sally assigned to dusting (0 or 1)
                           .
                           .
   assign(Sally, washing)  =  "amount" of Sally assigned to mowing (0 or 1)
                           .
                           .
   assign(Joe, dusting)	   =  "amount" of Joe assigned to washing (0 or 1)
                           .
                           .
   assign(Joe, washing)	   =  "amount" of Joe assigned to washing (0 or 1)

   Note:  Each of these variables can take on the value of 0 (if the 
   assignment is not made) or 1 (if the assignment is made). 

For the general problem formulation we need the following parameters:

 
   cost(Sally, dusting) = amount to pay Sally to dust the furniture
                        .
                        .
   cost(Joe, washing)   = amount to pay Joe to wash the dishes

   --------------------------------------------------

   max_jobs(Sally)  = maximum number of jobs Sally may perform
                     .
                     .
   max_jobs(Joe)    = maximum number of jobs Joe may perform

Basic Formulation


Based on the notation from above, the model can be rewritten as follows:

Minimize:

   cost(Sally, dusting) * assign(Sally, dusting) + 
                         .
                         .
 + cost(Joe, washing) * assign(Joe, washing)

Subject to:

   No more than the maximum number of tasks per person:
      assign(Sally, dusting) + . . . + assign(Sally, washing) <= max_tasks[Sally]
                                 .
                                 .
      assign(Joe, dusting) + . . . + assign(Joe, washing) <= max_tasks[Joe]


   No more than one person assigned to each task:
      assign(Sally, dusting) + . . . + assign(Joe, dusting) <= 1
                                 .
                                 .
      assign(Sally, washing) + . . . + assign(Joe, washing) <= 1

   Each variable assign[i,j] is (0 or 1).

Mathematical Formulation


The formulation from above can be made more mathematical if we define a set of people and a set of jobs.

   Let PEOPLE = (Sally, . . . , Joe)
    - assume there are P people in PEOPLE.

   Let JOBS = ( dusting, . . . , washing)
    - assume there are J jobs in JOBS.

and a set of parameters:

   cost[i,j]    = costs for person i (1..P)  and job j (1..J)
   time[i,j]    = time required for person i (1..P) to process job j (1..J)
   max_tasks[i] = maximum number of jobs person i (1..P) may be assigned

and a set of variables:

   assign[i,j]  = unknown assignments for person i (1..P) and job j (1..J)

Formulation: (If mathematical symbols do not appear below, try to activate this page

Minimize cost:

'Sum('Sum(cost(i,j) * assign(i,j), j,1,J), i,1,P)

Subject to


The Ampl Code


We can transform this mathematical formulation into a program that a computer will recognize and solve. We will model this problem in the AMPL language, which is easy to use and similar to the mathematical formulation. Here is an ampl model that corresponds to the mathematical formulation above.

set PEOPLE;
set JOBS;

param maxjobs {PEOPLE}, default 1;	
param cost {PEOPLE, JOBS} >= 0, default 1;

var Assign {PEOPLE, JOBS} >= 0, <= 1;

#-------------------------------------

minimize Total_Cost:
   sum {i in PEOPLE, j in JOBS} cost[i,j] * Assign[i,j];


#-------------------------------------
				
subj to Max_Num_Jobs {i in people}:  
   sum {j in jobs} Assign[i,j] <= maxjobs[i];
subj to Assign_Job {j in jobs}:  
   sum {i in people} Assign[i,j] = 1;


Network Formulation


The assignment problem is a specialized case of transportation problems which fall into the class of "network" problems. Network problems have a special structure, and in this case that structure is known as the "bipartite" graph. There are two groups of nodes, one is the origin of flow, and the other is the destination. In the assignment problem, each origin node is associated with one person, and each destination node with one of the targets (a job for example).

The network formulation in AMPL is given below:

set PEOPLE;
set JOBS;

param maxjobs {PEOPLE}, default 1;	
param cost {PEOPLE, JOBS} >= 0, default 1;

#-------------------------------------

minimize Total_Cost:

node People_Nodes {i in PEOPLE}: net_out <= maxjobs[i];				

node Job_Nodes {j in JOBS}: net_in = 1;

arc Assign {(i,j) in (PEOPLE cross JOBS)} >= 0, 
   from People_Nodes[i], to Job_Nodes[j], obj Total_Cost cost[i,j];

Although we are able to use the same data file for the linear programming and network formulations, note a few differences between them. In the network formulation we no longer need to declare a variable, and our constraints are represented as flow in and out of the nodes. The objective on the network formulation is simplified, and an additional constraint fills in the gaps. Despite the differences, however, the models will calculate the same optimal solution.


Algorithms for Solving


There are various ways to solve assignment problems. Certainly it can be formulated as a linear program (as we saw above), and the simplex method can be used to solve it. In addition, since it can be formulated as a network problem, the network simplex method may solve it quickly.

However, sometimes the simplex method is inefficient for assignment problems (particularly problems with a high degree of degeneracy). The Hungarian Algorithm developed by Kuhn ( computer algorithm provided by netlib) has been used with a good deal of success on these problems. In addition, there are various algorithms for network problems that may prove efficient.

As a side note, neural networks have also been used to solve the assignment problem. Although these have not proven as computationally efficient as the simplex approach yet, they provide an interesting contrast. (See Wolfe and Wang in the References section.)



[ Assignment Problem Case Study | Formulation | Camping Trip | Marriage Theorem | Links and References ]

Comments or questions? Write to julie.swann@isye.gatech.edu.

Return to Julie's home page.


LAST MODIFIED 21 MARCH 1997