Optimizacija hiperheuristika za probleme raspoređivanja na zahtjev

master's thesis

• Title (english): Optimization of hyperheuristics for online scheduling problems
• Author: Mihael Miličević
• Mentor: Domagoj Jakobović (mentor)
• Committee member: Domagoj Jakobović (predsjednik povjerenstva)
• Committee member: Nikolina Frid (član povjerenstva)
• Committee member: Leonardo Jelenković (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2024-07-09, Croatia

Abstract

U ovom je radu predstavljen novi pristup rješavanju problema raspoređivanja. Model raspoređivanja koji je korišten je model strojeva i poslova, gdje se sustav sastoji od nekoliko strojeva i njihovih međusobnih veza, određen broj poslova treba biti obrađen u sustavu, i cilj raspoređivača je da, u svakom trenutku, odredi koji posao se izvodi na kojem stroju, kako bi optimirao neke kriterije. Model za reprezentaciju topologija strojeva je predstavljen. Ovaj model je proširen s model događaja, koji podržava složena ponašanja poput prekida izvođenja poslova, kvarova strojeva, izmjene konteksta između poslova, preduvjeta za izvođenje, redova čekanja s ograničenom veličinom i grupnim izvođenjem poslova. Objašnjeni su evaluacija i optimizacija takvih sustava u predeterminiranom načinu rada, i načinu rada na zahtjev. Kroz nekoliko studija slučaja, koje su sadržavale probleme različitih konfiguracija i karakteristika, demonstrirano je da se ovaj model može iskoristiti za uspješno rješavanje problema raspoređivanja na zahtjev. Rješenje je ostvareno korištenjem hiperheuristika, gdje cilj nije efektivno riješiti neki problem, nego je cilj pronaći efektivnu metodu za rješavanje problema.

Abstract (english)

In this thesis, a novel approach to solving scheduling problems is presented. The model of scheduling which was used was the model of machines and jobs, in which a system consists of several machines and their connections, a certain number of jobs needs to be processed in the system, and the scheduler needs to decide, at each moment, which job is being processed on which machine, in order to optimize some criteria. A model for representing machine topologies is introduced. This model is extended with an events model, which supports complex behaviors such as preemptions, breakdowns, setups, prerequisites, buffers of a limited size and batch processing. Evaluation and optimization of such systems in both an offline and an online setting is presented. Through a series of case studies, containing problems of different configurations and characteristics, it is demonstrated that this model can be used to successfully solve online scheduling problems. The solution was achieved using hyperheuristics, where the goal is not to effectively solve a problem, instead the goal is to find an effective method for solving a problem.

• Keywords: raspoređivanje; raspoređivanje na zahtjev; optimizacija; metaheuristike; hiperheuristike; evolucijsko računarstvo; genetsko programiranje
• Keywords (english): scheduling; online scheduling; optimization; metaheuristics; hyperheuristics; evolutionary computing; genetic programming
• Language: english
• URN:NBN: urn:nbn:hr:168:637350
• 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: 2024-10-12 21:36:35