Automated design of dispatching rules in unrelated machines environment : doctoral thesis - Đurasević, Marko; Jakobović, Domagoj (Zagreb : M. Đurasević, Fakultet elektrotehnike i računarstva, 2018)
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 many-objective 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.
Keywords: genetic programming, scheduling problems, unrelated machines environment, multi-objective optimisation, ensemble learning, dynamic scheduling conditions, static scheduling conditions, machine learning
Raspoređivanje je proces donošenja odluka u kojem je, tijekom određenog vremenskog razdoblja, zadani skup aktivnosti ili zadataka potrebno dodijeliti jednom od nekoliko dostupnih resursa. Cilj procesa raspoređivanja jest izraditi raspored koji optimira određene korisnički definirane kriterije. Problemi raspoređivanja javljaju se u mnogim situacijama iz stvarnog svijeta, kao primjerice u proizvodnim procesima, zračnim lukama i računalnim klasterima. Nažalost, većina instanci problema raspoređivanja pripada kategoriji NP-teških problema. Zbog toga se za rješavanje različitih problema raspoređivanja najčešće koriste razne heurističke metode. Jedna od najčešće korištenih metoda za rješavanje problema raspoređivanja su pravila raspoređivanja. Za razliku od mnogih drugih metoda koje iterativno unapređuju kvalitetu rasporeda, pravila raspoređivanja izrađuju raspored inkrementalno na način da u svakom trenutku odlučivanja odabiru koji je posao potrebno rasporediti na koji od strojeva. Zbog toga su pravila raspoređivanja iznimno korisna za raspoređivanje u dinamičnim uvjetima jer se mogu brzo prilagoditi promjenjivim uvjetima u sustavu. Međutim, izrada dobrih pravila raspoređivanja je težak i dugotrajan proces, zbog čega se genetsko programiranje često koristi u svrhu automatske izrade novih pravila raspoređivanja.

Glavni cilj disertacije je unaprijediti performanse pravila raspoređivanja koja su izrađena genetskim programiranjem. U prvom dijelu disertacije korištene su višekriterijske i mnogokriterijske metode optimizacije za oblikovanje pravila raspoređivanja koja optimiraju nekoliko kriterija istodobno. Dobiveni rezultati pokazuju kako su pomoću testiranih metoda dobivena pravila raspoređivanja koja ostvaruju dobre rezultate za razne kriterije raspoređivanja. U drugom dijelu disertacije različite metode skupnog učenja su primijenjene zajedno s genetskim programiranjem kako bi se izradili skupovi pravila raspoređivanja, koji mogu ostvariti bolje rezultate nego individualna pravila raspoređivanja. U trećem dijelu disertacije predložena je procedura za odabir pravila raspoređivanja koja su najprikladnija za rješavanje konkretne instance problema. Prethodno spomenuta procedura postiže bolje rezultate nego kada se koristi samo jedno pravilo raspoređivanja za rješavanje svih instanci problema. U posljednjem dijelu disertacije analizira se prilagodba pravila raspoređivanja za statičko raspoređivanja pomoću nekoliko različitih metoda. Testiranje metode ostvaruju različite kompromise između kvalitete dobivenog rezultata i trajanja izvođenja metoda, s tim da nekoliko metoda nadmašuje rezultate ostvarene korištenjem genetskog algoritma.
Ključne riječi: genetsko programiranje, okolina nesrodnih strojeva, višekriterijska optimizacija, skupno učenje, dinamični uvjeti raspoređivanja, statični uvjeti raspoređivanja, strojno učenje
Bibliografija str. 411-445.