Information Technology Reference
In-Depth Information
11.3.2 The Task Assignment Problem
The task assignment problem (TAP) of this section is the simple toy problem
chosen by Tank and Hopfield (1987) in their
Scientific American
article to
illustrate the workings of Hopfield networks on combinatorial cost-optimi-
zation problems.
In TAP there are
n
tasks that must be accomplished by using only
n
work-
ers. Each worker performs better at some tasks and worse at others and obvi-
ously some workers are better than others at certain tasks. The goal is to
minimize the total cost for accomplishing all tasks or, stated differently, to
maximize the overall output of all the workers as a whole.
Suppose we had to shelve
n
topic collections in a library using
n
shelving
assistants. Each assistant is familiar with the subject areas to varying de-
grees and shelves the collections accordingly. The input data or fitness cases
in this task assignment problem consist of the rates at which topics are shelved
per minute (Figure 11.7).
A
B
C
D
E
F
1
2
3
4
5
6
10
6
1
5
3
7
5
4
6
4
9
7
8
3
6
3
7
2
2
5
6
6
4
1
5
3
4
1
8
3
1
2
6
4
7
2
Figure 11.7.
The task assignment problem. Each assistant (1-6) should be assigned
to one collection of topics (A-F) based on the rates at which topics are shelved per
minute (fitness cases). Shaded squares show the best assignment with the largest
sum of shelving rates, 44.
For this simple six-by-six problem there are already 6! = 720 possible as-
signments of assistants to topic collections. The best solution has the highest
sum of rates for the chosen assistants. For the particular set of fitness cases
shown in Figure 11.7,
f
max
= 44.
This kind of toy problem is very useful for comparing the performance of
different algorithms and different search operators and, here, the potentiali-
ties of inversion will be further tested in systems in which chromosomes
