## The Allocation Assignment Problem

The allocation or assignment problem is to distribute tasks between workers in such a way that the total cost, time, waste (or some other measure) involved in doing a job which involves completing a range of tasks is minimized. In general, people are better at some things than others. In general a person more effective at doing one task than everyone else may also be more effective at other tasks. Nevertheless, an allocation of tasks is often necessary.

The allocation problem allocates each worker to a single task. This means we require the same number of workers as tasks. The cost of each worker doing each task is represented in the form of a matrix. The problem then becomes one of choosing an element in each column and row so that no two entries in a row or column are selected, and the sum of the costs associated with each worker doing their allocated task is minimized.

For example, the table below shows costs for four workers to do four tasks.

 Task A Task B Task C Task C Albert 13 24 42 17 Bob 11 31 22 27 Chris 15 18 34 54 David 56 33 43 56

We might allocated these workers to these tasks:

The total cost is then 13+31+34+56=134

One the other hand we could allocate 