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:

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.

Add comment

Security code
Refresh