engleski

Improving genetic algorithm performance by population initialisation with dispatching rules

Scheduling is an important process that is present in many real world scenarios where it is essential to obtain the best possible results. The performance and execution time of algorithms that are used for solving scheduling problems are constantly improved. Although metaheuristic methods by themselves already obtain good results, many studies focus on improving their performance. One way of improvement is to generate an initial population consisting of individuals with better quality. For that purpose a variety of methods can be designed. The benefit of scheduling problems is that dispatching rules (DRs), which are simple heuristics that provide good solutions for scheduling problems in a small amount of time, can be used for that purpose. The goal of this paper is to analyse whether the performance of genetic algorithms can be improved by using such simple heuristics for initialising the starting population of the algorithm. For that purpose both manual and different kinds of automatically designed DRs were used to initialise the starting population of a genetic algorithm. In case of the manually designed DRs, all existing DRs for the unrelated machines environment were used, whereas the automatically designed DRs were generated by using genetic programming. The obtained results clearly demonstrate that using populations initialised by DRs leads to a significantly better performance of the genetic algorithm, especially when using automatically designed DRs. Furthermore, it is also evident that such a population initialisation strategy also improves the convergence speed of the algorithm, since it allows it to obtain significantly better results in the same amount of time. Additionally, the DRs have almost no influence on the execution speed of the genetic algorithm since they construct the schedule in time which is negligible when compared to the execution of the genetic algorithm. Based on the obtained results it can be concluded that initialising individuals by using DRs significantly improves both the convergence and performance of genetic algorithm, without the need of having to manually design new complicated initialisation procedures and without increasing the execution time of the genetic algorithm.

scheduling ; unrelated machines environment ; genetic algorithms ; dispatching rules ; population initialisation

nije evidentirano