Page 306 - Mechatronics for Safety, Security and Dependability in a New Era

Ch58-I044963.fm Page 290 Tuesday, August 1, 2006 4:39 PM
Ch58-I044963.fm
290
290 Page 290 Tuesday, August 1, 2006 4:39 PM
Expression of essential constraints

In the proposed method, 1" is assigned for the dependency relations between the tasks as illustrated
"
in Figure 3. "10" is used for the essential constraint coming from something except for the
dependency relations between the tasks. For example, if the essential constraint on the task order is
that the task 2 has to be performed after the task 5, "10" is assigned to the cell as seen in Figure 3. If
there are no dependency relations between the tasks and the essential constraints, the cell contains '0'
Essential constraint
on task order
Task 1 | Task 2 | Task 3 | Task 4 | i Task 7 | Task 8 |

, 0 0 0
Task 1 • 0 0 1 1
Task 2 0 • 0 ( )o 0 0
10
Task 3 0 0 •i-tr 0 1 0
Task 4 1 0 0 • 0 0 0 0
Task 5 0 1 0 0 • 0 1 0
Task 6 0 0 0 1 • 0 o
Task 7 0 1 0 0 0 0 • o
Task 8 o 0 0 0 0 0 0 •
Figure 3: Description of essential constraint on task order
Expression of chromosome

The gene is expressed through the task identification. The chromosome shows the task order through
the task identification as seen in Figure 4. Therefore the length of the chromosomes coiTesponds to the
number of the target tasks.

Identification number of task

4 56 37 22 5 • • •

Figure 4: Expression of chromosome

Crossover operation

If the regular crossover operation (Holland, 1975) is applied to the aforementioned chromosome, the
chromosome must have the same genes, i.e., the same task identifications in almost all cases. This
means that the chromosome generated by the crossover operation does not express the task order.
Therefore, if the regular crossover operation is used, the efficiency of searching the best task order
degrades significantly. In the proposed method, the special crossover method called Partially Matched
Crossover (Goldberg, 1989) is used. This method was initially developed for the traveling salesman
problem (TSP), where the order of the places the salesman should visit is resolved. This approach can
also be used to resolve the problem which we handle.

Calculation of individual's fitness