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:
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.