The Allocation Assignment Problem

• Print

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.

We might allocated these workers to these tasks:

Albert to Task A:Cost 13

Bob to Task B:Cost 31

Chris to Task C:Cost 34

David to Task D:Cost 56

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

One the other hand we could allocate

Albert to Task C:Cost 17

Bob to Task A:Cost 11

Chris to Task B:Cost 18

David to Task D:Cost 56

The total cost is then 17+11+18+56=102

The allocation problem may be solved methodically using The Hungarian Algorithm.