Hiperheurističke metode rješavanja problema raspoređivanja u okruženju nesrodnih strojeva

master's thesis

• Title (english): Hyper-heuristic Methods for Solving Scheduling Problems on Unrelated Machines
• Author: Hrvoje Backović
• Mentor: Domagoj Jakobović (mentor)
• Committee member: Domagoj Jakobović (predsjednik povjerenstva)
• Committee member: Vlado Sruk (član povjerenstva)
• Committee member: Marko Čupić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2017-07-11, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: raspoređivanje; prioritetno raspoređivanje; nesrodni strojevi; genetski algoritam; evolucijski algoritam; genetsko programiranje; kartezijsko genetsko programiranje; gramatička evolucija; umjetne neuronske mreže
• Keywords (english): job shop scheduling; priority scheduling; unrelated machines; genetic algorithm; evolutionary algorithm; genetic programming; cartesian genetic programming; grammatical evolution; artificial neural network
• Language: croatian
• URN:NBN: urn:nbn:hr:168:001508
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-03-13 18:43:14