A comparative study of solution representations for the unrelated machines environment (CROSBI ID 279568)
Prilog u časopisu | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Vlašić, Ivan ; Đurasević, Marko ; Jakobović, Domagoj
engleski
A comparative study of solution representations for the unrelated machines environment
Scheduling problems are quite difficult to solve since in many cases no exact algorithms exist which can obtain the optimal solution in a reasonable amount of time. Therefore, these problems are often solved by using various metaheuristic methods, like genetic algorithms. To use these methods, the first step which needs to be performed is to define an encoding scheme that will be used to represent the solutions. Until now, several encoding schemes were proposed for the unrelated machines environment, each of which comes with its own benefits and drawbacks. However, the performance of metaheuristic methods depends on the applied encoding scheme. Unfortunately, no extensive research was performed in the literature to compare different solution representations for the unrelated machines scheduling problem. Therefore, the choice of the solution representation used is mostly provisional and is usually not based on any existing knowledge of how it would perform on the considered problem. This can cause the algorithms to obtain suboptimal results, which can lead to wrong conclusions about the performance. Thus, the goal of this paper is to test seven solution representations that were used in previous studies to represent solutions for the unrelated machines scheduling problem. The selected solution representations were tested for optimising four scheduling criteria, while additionally measuring the execution time of the genetic algorithm when using each of the encodings. The obtained results demonstrate that the encoding which is based on the permutation of jobs obtains the best results, making it the superior encoding scheme for this type of scheduling problem.
Unrelated machines environment ; Genetic algorithms ; Solution representations ; Scheduling
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o izdanju
123
2020.
105005
15
objavljeno
0305-0548
1873-765X
10.1016/j.cor.2020.105005