Automatski razvoj pravila raspoređivanja za probleme raspoređivanja s ograničenjima

master's thesis

• Title (english): Automated design of dispatching rules for scheduling problems with constraints
• Author: Kristijan Jaklinović
• Mentor: Domagoj Jakobović (mentor)
• Committee member: Domagoj Jakobović (predsjednik povjerenstva)
• Committee member: Leonardo Jelenković (član povjerenstva)
• Committee member: Ante Đerek (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2019-07-12, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Problem raspoređivanja je NP-težak problem, što znači da ga nije moguće optimalno riješiti u polinomijalnom vremenu te se za rješavanje takvih problema najčešće koriste aproksimativne metode. Jedna od tih metoda je i genetsko programiranje. U radu je opisana primjena genetskog programiranja na problem raspoređivanja u okruženju nesrodnih strojeva. Definirani su glavni dijelovi pravila raspoređivanja, prioritetna funkcija koju razvijamo pomoću genetskog programiranja te shema za izradu rasporeda koja donosi konačne odluke prilikom dodjeljivanja posla strojevima. Definirana su i neka ograničenja koja se mogu pojaviti u sustavu kao i prilagodba GP-a za svako navedeno ograničenje. Dodatno, napravljena je analiza kako se GP ponaša za svako pojedinačno ograničenje kao i za kombinaciju različitih ograničenja u sustavu.

Abstract (english)

Scheduling problems are NP-hard, which means that it is not possible to solve them optimally in polynomial time. The most commonly used methods for solving these types of problems are approximate methods. One of those methods is genetic programming. This thesis describes the application of genetic programming on scheduling problems in the unrelated machines environment. It defines main components of dispatching rules, a priority function which is developed by using genetic programming and schedule generation scheme which brings final decisions about job assignment to machine. It describes scheduling constraints which may appear in the system as well as the adjustment of genetic programming for those constraints. Finally, behaviour of genetic programming is analysed in an environment with one or multiple scheduling constraints.

• Keywords: raspoređivanje; okruženje nesrodnih strojeva; genetsko programiranje; pravila raspoređivanja; ograničenja u raspoređivanju
• Keywords (english): scheduling; unrelated machines environment; genetic programming; dispatching rules; scheduling constraints
• Language: croatian
• URN:NBN: urn:nbn:hr:168:773664
• 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: 2020-01-07 18:34:56