Naslov
Automated design of dispatching rules in unrelated machines environment

Autori
Đurasević, Marko

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, doktorska disertacija

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
13.02

Godina
2018

Stranica
500

Mentor
Jakobović, Domagoj

Ključne riječi
genetic programming ; scheduling problems ; unrelated machines environment ; multi-objective optimisation ; ensemble learning ; dynamic scheduling conditions ; static scheduling conditions ; machine learning

Sažetak
Scheduling is a decision-making process in which a certain set of activities or tasks needs to be allocated on one of the available scarce resources, over a given time period. The objective of the scheduling process is to create a schedule which optimises certain user defined criteria. Scheduling problems appear in many real world situations, such as in manufacturing processes, airports, and computer clusters. Unfortunately, most scheduling problem instances belong to the category of NP- hard problems. Therefore, various heuristic methods are most often used in order to obtain solutions for different scheduling problems. One of the most commonly used methods for solving scheduling problems are dispatching rules. Unlike many other methods which iteratively improve the quality of schedules, dispatching rules create the schedule incrementally by selecting which job should be scheduled on which machine at each decision moment. This makes dispatching rules especially useful for scheduling under dynamic conditions, since they can quickly adapt to the changing conditions of the system. However, designing good dispatching rules is a difficult and tedious task. For that reason, genetic programming is often used in order to automatically design new dispatching rules. The main objective of this thesis is to improve the performance of dispatching rules which are generated by genetic programming. In the first part of the thesis multi-objective and manyobjective optimisation methods were used in order to generate dispatching rules for optimising several objectives simultaneously. The obtained results demonstrate that the methods generated new dispatching rules which perform well for various scheduling objectives. In the second part of the thesis different ensemble learning methods were applied with genetic programming to generate ensembles of dispatching rules, which can achieve better results than by using only a single dispatching rule. The third part of the thesis proposes a procedure for selecting the dispatching rule which is best suited for a concrete problem instance. The aforementioned procedure achieves a better performance than if only a single dispatching rule would be used to solve all problem instances. The final part of the thesis analyses the adaptation of dispatching rules for static scheduling, by using several different methods. The tested methods provide different trade-offs between the quality of the results and execution times of the methods, with several methods outperforming results achieved by a genetic algorithm.

Izvorni jezik
Engleski

Znanstvena područja
Računarstvo

POVEZANOST RADA