Hyper-heuristic Methods for Solving Scheduling Problems on Unrelated Machines

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 prioritetno raspoređivanje gdje se raspored dinamički gradi uz pomoć predefinirane heurističke prioritetne funkcije. U ovom radu opisuje se hiperheuristički model za pronalaženje prioritetnih funkcija temeljen na evolucijskim algoritmima i neurološkim sustavima. U sklopu modela opisuje se kartezijsko genetsko programiranje, gramatička evolucija i neuronske mreže kao tri različita pristupa za evoluciju prioritetnih funkcija. Za svaki pristup se posebno definira struktura, prikaz rješenja i evolucijski operatori križanja i mutacije. Svaki od ta tri pristupa se testira te se analizira njihova efikasnost u usporedbi s postojećim rezultatima drugih metoda. Osim usporedbe kvalitete rezultata, analizira se i vremenska i prostorna složenost različitih pristupa te se daju prijedlozi za moguća poboljšanja.Scheduling is a well known NP-hard optimization problem, which means that an algorithm which can obtain the optimal solution within reasonable time constraints does not exist. One of the methods for solving this problem is priority scheduling where the final schedule is dynamically constructed using a predefined priority function (heuristic). This paper describes a hyper-heuristic model for generating priority functions based on evolutionary algorithms and artificial neural networks. This model describes cartesian genetic programming, grammatical evolution and artifical neural networks as three different methods for evolving priority functions. The structure, solution representation and evolutionary operators are defined for each method. All the methods are tested and their efficiency is analyzed and compared to existing methods. Also, the time and space complexity of the methods is analyzed and possible future improvements are proposed