Oblikovanje prioritetnih pravila za problem raspoređivanja s ograničenim sredstvima.

doctoral thesis

• Title (english): Design of priority for resource constrained project scheduling problem.
• Author: Mateja Đumić
• Mentor: Domagoj Jakobović (mentor)
• Committee member: Domagoj Jakobović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; (Department of Electronics, Microelectronics, Computer and Intelligent Systems); Zagreb
• Defense date and country: 2020, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing; Artificial Intelligence
• Universal decimal classification (UDC): 004 - Computer science and technology. Computing. Data processing

Abstract

Problem raspoređivanja s ograničenim sredstvima je problem u kojem je potrebno pronaći raspored aktivnosti koji će zadovoljiti uvjete prednosti i uvjete na sredstva i pri tome optimizirati jedan ili više kriterija. Ovaj problem pripada klasi NP-teških problema zbog čega pronalazak optimalnog rješenja za većinu instanci nije moguć. U skladu s tim, razvijaju se brojne heurističke metode koje su uglavnom ograničene na primjenu u statičkim okruženjima, dok su prioritetna pravila jedna od rijetkih metoda koja se može primijeniti i u dinamičkim okruženjima. Razvoj prioritetnih pravila je zahtjevan posao zbog čega se sve više koriste postupci za automatizirani razvoj pravila raspoređivanja. Ova disertacija usmjerena je prema oblikovanju prioritetnih pravila za problem raspoređivanja s ograničenim sredstvima upotrebom genetičkog programiranja i podijeljena je u tri glavna dijela. Prvi dio je usmjeren prema samom razvoju prioritetnih pravila, u drugom dijelu primjenom ansambala dodatno se povećava kvaliteta rezultata ostvarenih razvijenim prioritetnim pravilima, dok treći dio donosi prilagodbu razvijenih pravila za korištenje u statičkim uvjetima. Provedena ispitivanja pokazuju da razvijena pravila ostvaruju značajno bolje rezultate od onih ostvarenih postojećim prioritetnim pravilima te da njihovom dodatnom prilagodbom, u ovisnosti o okruženju u kojem se primjenjuju, mogu biti ostvarena značajna poboljšanja u rezultatima.

Abstract (english)

Resource constrained project scheduling problem is a problem in which it is necessary to find a schedule of activities that will meet the resource and precedence constraints and at the same time optimize one or more criteria. This problem belongs to the class of NP-hard problems, which is why it is not possible to find the optimal solution for most problem instances. Accordingly, numerous heuristic methods are being developed whose usage is mostly limited to static environments, while priority rules are one of the few methods that can be applied in dynamic environments as well. The development of priority rules is a demanding job, which is why procedures for the automated development of scheduling rules are increasingly being used. This thesis is focused on the design of priority rules for resource constrained project scheduling problem using genetic programming and is divided into three main parts. The first part is focused on the development of priority rules, in the second part ensembles od priority rules were used to further increase the quality of results achieved by the developed priority rules, while the third part brings the adaptation of developed rules for use in static environments. The conducted experiments show that the developed rules achieve significantly better results than those achieved by the existing priority rules and that their additional adaptation, depending on the environment in which they are used, can lead to significant improvements in results.

• Keywords: problem raspoređivanja s ograničenim sredstvima; genetičko programiranje; prioritetna pravila; hiperheuristika; strojno učenje; ansambli
• Keywords (english): resource constrained project schedulin problem; genetic programming; priority rules; hyperheuristic; machine learning; ensembles
• Language: croatian
• URN:NBN: urn:nbn:hr:168:631498
• Promotion: 2020
• Study programme: Title: Computer Science; Study programme type: university; Study level: postgraduate; Academic / professional title: Doktor znanosti (Doktor znanosti)
• Type of resource: Text
• Extent: 154 str.
• File origin: Born digital
• Access conditions: Open access
• Created on: 2020-09-16 15:03:30