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