Solving Scheduling Problems in the Unrelated Machines Environment by Using Evolutionary Algorithms

Problem raspoređivanja je vrlo poznat i spada u klasu NP teških problema, što znači da ne postoje efikasni algoritmi koji pronalaze optimalno rješenje unutar razumnih vremenskih ograničenja. Jedna od metoda rješavanja tog problema je upotreba evolucijskih algoritama. U radu se opisuje primjena evolucijskih algoritama na rješavanje problema raspoređivanja u okruženju nesrodnih strojeva. Uspoređuju se različiti prikazi jedinki korišteni u literaturi kako bi se pronašao onaj koji postiže najbolje rezultate za promatrane kriterije. Dodatno, upotrebom različitih pravila raspoređivanja u inicijalizaciji početne populacije pokušava se postići poboljšavanje rezultata i njihova brža konvergencija. Konačno, različiti algoritmi su primijenjeni za rješavanje problema raspoređivanja s dodatnim ograničenjima te je analiziran utjecaj svakog ograničenja na dobivene rezultate.Scheduling is a well known NP-hard optimization problem, which means an algorithm that finds the optimal solution within reasonable time constraints does not exist. One of the methods for solving this problem is using evolutionary algorithms. This thesis describes the application of evolutionary algorithms in solving the problem of scheduling in the unrelated machines environment. Different solution representations used in the literature are compared to find the one that achieves the best results for the observed criteria. In addition, various dispatching rules in initialization of the population are tried to achieve improved results and their faster convergence. Finally, various algorithms have been applied to solve the problem of scheduling with constraints and the impact of each constraint on the obtained results is analyzed