The assignment problem

The assignment problem is about finding the best way to assign resources to tasks. Examples include assigning machines to jobs, workers to tasks, or soccer players to positions. The goal is to determine the optimal assignment that minimizes the total cost or maximizes overall effectiveness. It is a fundamental problem in the field of combinatorial optimization.

Consider a situation with four jobs that need to be performed by four workers. Since each worker has different skills, the time required to complete a job depends on which worker is assigned to it.

The table below shows the time required (in minutes) for each possible combination of a worker and a job. The jobs are labeled J1, J2, J3, and J4, and the workers are labeled W1, W2, W3, and W4.

Each worker must be assigned exactly one job, and the objective is to minimize the total time needed to complete all jobs.

The optimal assignment is to assign worker W1 to job J3, worker W2 to job J2, worker W3 to job J1, and worker W4 to job J4. The total time required is 69 + 37 + 11 + 23 = 140 minutes. Any other assignment results in a higher total time.

The Hungarian algorithm can be used to find this optimal assignment. You can read a step-by-step explanation of the algorithm here, or see an illustrated explanation using the example above here.