|
|
For a
n jobs x m machines
problem, two
random integers between [0, n x m
-1] are generated. n x m is
the code-string' s size. These random
numbers indicate positions in the string
to create a parents' substring. In the
figure these numbers are 3 an 6.
Parents' substrings are
directly inherited by children: father
1's substring
(3 1 1)
is inherited by chid 1
and
father 2's substring (3 2 1) is
inherited by child 2
's.
child 1: [ _, _ , _ , 3, 1, 1, _, _ , _
], that is: job 3's second operation and
job 1's first and second operations
child 2: [ _, _ , _ , 3, 2, 1, _, _ , _
], that is: job 3's first operation, job
2's second operation and job 1's third
operation.
To get the other items of
child 1's string:
■ We
create a new string whose items are got
from
father 2's string but
since the next position of the second
random number and in a cycle way: ( 2 3
3 /// 2 1 1 3 2 1).
■ We
have to remove from this string those
jobs' operations which are already
in child 1's string (that
is,
job 3's second operation and job 1's
first and second operations):
( 2 3 X 2 X X 3 2 1) to get ( 2 3 2 3 2
1).
■ We
fill the child 1's string but:
- since
the next position of the
second random number
[ _, _ , _ , 3, 1, 1, 2, 3 , 2]
-
and in a cycle way [3, 2,
1, 3, 1, 1, 2, 3, 2]
To get the other items of
child 2's string:
■ We
create a new string whose items are got
from
father 1's string but
since the next position of the second
random number and in a cycle way: ( 2 3
1 /// 3 2 2 3 1 1).
■ We
have to remove from this string those
jobs' operations which are already
in child 2's string (that
is,
job 3's first operation, job 2's second
operation and job 1's third operation):
(
2 X 1 3 X 2 3 1 X)
to get ( 2 1 3 2 3 1).
■ We
fill the child 2's string but:
- since
the next position of the
second random number
[ _, _ , _ , 3, 2, 1, 2, 1 , 3]
-
and in a cycle way [2, 3,
1,
3, 2, 1, 2, 1 , 3] |
