Rješavanje problema raspoređivanja u okruženju nesrodnih strojeva korištenjem evolucijskih algoritama

diplomski rad

• Naslov (engleski): Solving Scheduling Problems in the Unrelated Machines Environment by Using Evolutionary Algorithms
• Autor: Ivan Vlašić
• Mentor: Domagoj Jakobović (mentor)
• Član povjerenstva: Domagoj Jakobović (predsjednik povjerenstva)
• Član povjerenstva: Goran Delač (član povjerenstva)
• Član povjerenstva: Vlado Sruk (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2018-07-12, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: raspoređivanje; okruženje nesrodnih strojeva; evolucijski algoritmi; pravila raspoređivanja; ograničenja u raspoređivanju
• Ključne riječi (engleski): scheduling; unrelated machines environment; evolutionary algorithms; dispatching rules; scheduling constraints
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:956799
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2019-03-14 02:01:16