373
3.6 Crossover operator
The crossover operation produces newer offspring (new chromosomes) from the parents
(old chromosomes) by exchanging information (genes) among the latter. A crossover
probability decides the number of chromosomes which would undergo crossover at every
generation.
In this study, the design of the crossover operator was a tricky task as crossover operators, if normally employed, might produce sequences which violate the precedence relationship among blocks. Keeping this in mind, following crossover operators have been
designed:
3.6.1 Similar before point crossover (SBPX) operator
The operation of SBPX operator is carried out in two steps. In the first step, a crossover point
is randomly selected and all the blocks which lie on left hand side of the point are directly
copied from the parents to corresponding offspring i.e. from parent 1 to offspring 1 and from
parent 2 to offspring 2. In the second step, the blocks are cross copied i.e. from parent 1 to
offspring 2 and from parent 2 to offspring 1 while maintaining the relative order of blocks in
the parents to generate new chromosomes.
3.6.2 Similar after point crossover (SAPX) operator
SAPX’s operation is similar to SBPX except the fact that in the first step, instead of directly
copying all the blocks which lie on the left hand side, all the blocks which lie on the right hand
side of randomly selected crossover point are directly copied from corresponding parents to
the offspring. The second step of its operation is exactly the same as that of SBPX.
3.6.3 Similar before and after 2 point crossover (SBA2PX) operator
In this crossover operator, instead of one, two crossover points are randomly selected in the
first step. Then, all the blocks which lie on the left hand side and right hand side of the first
and second crossover points respectively are directly copied from the parents to corresponding offspring. Again, the second step of its operation is exactly similar to SBPX.
3.7 Mutation operator
In mutation operation, the genes of a chromosome are tweaked a little to induce some variations in the same. This invokes and maintains diversity in the population thereby avoiding
premature convergence of the algorithm. A mutation probability, similar to crossover, determines the number of chromosomes which would undergo mutation.
Similar to crossover operators, the mutation operator has to be designed in such a way
that the precedence relationship between the blocks is always satisfied. Thus, in the designed
mutation operator, a block is randomly selected from period 1 and it along with all its successors extracted in period 1 are moved to period 2. The space vacated by the moved blocks
is then filled by shifting blocks from period 2 to period 1 from right to left while maintaining
the same relative order. The sequence produced after the movement of blocks is then checked
for its precedence feasibility. If the generated sequence is feasible, it is accepted and if infeasible, another move is tried between period 1 and 2 until a feasible move is found. This process
is then repeated for all the consecutive periods until the blocks are moved between the second
last and the last period.
4 CASE STUDY
The proposed model and the solution approach were applied to a real iron ore mine in India.
This is a captive mine which supplies iron ore to India’s largest steel making company. The
mine has 4 pits in operation to meet the quality and quantity requirements of the 2 processing plants. In this case study, 1212 blocks from the 4 pits to be extracted over a horizon of
1 year were taken. The granularity of a time period is one month and thus the problem has
3.6 Crossover operator
The crossover operation produces newer offspring (new chromosomes) from the parents
(old chromosomes) by exchanging information (genes) among the latter. A crossover
probability decides the number of chromosomes which would undergo crossover at every
generation.
In this study, the design of the crossover operator was a tricky task as crossover operators, if normally employed, might produce sequences which violate the precedence relationship among blocks. Keeping this in mind, following crossover operators have been
designed:
3.6.1 Similar before point crossover (SBPX) operator
The operation of SBPX operator is carried out in two steps. In the first step, a crossover point
is randomly selected and all the blocks which lie on left hand side of the point are directly
copied from the parents to corresponding offspring i.e. from parent 1 to offspring 1 and from
parent 2 to offspring 2. In the second step, the blocks are cross copied i.e. from parent 1 to
offspring 2 and from parent 2 to offspring 1 while maintaining the relative order of blocks in
the parents to generate new chromosomes.
3.6.2 Similar after point crossover (SAPX) operator
SAPX’s operation is similar to SBPX except the fact that in the first step, instead of directly
copying all the blocks which lie on the left hand side, all the blocks which lie on the right hand
side of randomly selected crossover point are directly copied from corresponding parents to
the offspring. The second step of its operation is exactly the same as that of SBPX.
3.6.3 Similar before and after 2 point crossover (SBA2PX) operator
In this crossover operator, instead of one, two crossover points are randomly selected in the
first step. Then, all the blocks which lie on the left hand side and right hand side of the first
and second crossover points respectively are directly copied from the parents to corresponding offspring. Again, the second step of its operation is exactly similar to SBPX.
3.7 Mutation operator
In mutation operation, the genes of a chromosome are tweaked a little to induce some variations in the same. This invokes and maintains diversity in the population thereby avoiding
premature convergence of the algorithm. A mutation probability, similar to crossover, determines the number of chromosomes which would undergo mutation.
Similar to crossover operators, the mutation operator has to be designed in such a way
that the precedence relationship between the blocks is always satisfied. Thus, in the designed
mutation operator, a block is randomly selected from period 1 and it along with all its successors extracted in period 1 are moved to period 2. The space vacated by the moved blocks
is then filled by shifting blocks from period 2 to period 1 from right to left while maintaining
the same relative order. The sequence produced after the movement of blocks is then checked
for its precedence feasibility. If the generated sequence is feasible, it is accepted and if infeasible, another move is tried between period 1 and 2 until a feasible move is found. This process
is then repeated for all the consecutive periods until the blocks are moved between the second
last and the last period.
4 CASE STUDY
The proposed model and the solution approach were applied to a real iron ore mine in India.
This is a captive mine which supplies iron ore to India’s largest steel making company. The
mine has 4 pits in operation to meet the quality and quantity requirements of the 2 processing plants. In this case study, 1212 blocks from the 4 pits to be extracted over a horizon of
1 year were taken. The granularity of a time period is one month and thus the problem has