Projekt obuhvaća izgradnju računalnog sustava (programskog alata) za stvaranje postupaka raspoređivanja prilagođenih korisničkim zahtjevima o okruženju i kriterijima raspoređivanja. Pronalaženje prikladnog algoritma ostvaruje se strojnim učenjem temeljenim na genetskom programiranju.
Postupci raspoređivanja su ugrađeni u većinu procesa kojima se upravlja na nekoj razini. Primjeri uključuju proizvodne procese (npr. građevinske radove), upravljanje računalnim poslovima (npr. u grozdu ili spletu računala), uslužne djelatnosti (poslovi održavanja, posluživanje zahtjeva u tiskari), logističku potporu (dostava, opskrba materijalom), održavanje oblika nastave (laboratoriji, ispiti) itd. Budući je velik broj problema raspoređivanja u ovim primjerima nerješiv determinističkim postupcima u stvarnom vremenu, postupci raspoređivanja su često jednostavni heuristički algoritmi, a nerijetko se temelje i samo na osobnoj procjeni čovjeka – voditelja procesa. Glavninu algoritama raspoređivanja u industrijskoj uporabi čine pravila raspoređivanja, koja uz pomoć metrike – funkcije prioriteta, ocjenjuju raspoložive aktivnosti te najbolje ocijenjenu aktivnost dodjeljuju sredstvu. Primjer pravila raspoređivanja je npr. 'odaberi aktivnost najkraćeg trajanja'.
Teorija raspoređivanja poznaje mnoga pravila koja odgovaraju određenoj vrsti okruženja i kriterija. Problem na koji se u praksi nailazi je upravo odabir odgovarajućeg pravila, budući da stvarne uvjete raspoređivanja može biti teško svesti na neki matematički model. Osim toga, za specifične kombinacije okruženja i načina vrednovanja rasporeda koje korisnici mogu tražiti često ne mora niti postojati odgovarajući postupak raspoređivanja.
Predloženi projekt ima za cilj stvaranje računalnog sustava koji uz zadane korisničke uvjete i kriterije izrade rasporeda pronalazi, postupkom strojnog učenja, odgovarajuće pravilo raspoređivanja – prilagođenu funkciju prioriteta. Rješenje je pri tome dano u obliku u kojem se može ugraditi u postojeće računalne sustave raspoređivanja ili koristiti od strane čovjeka – voditelja procesa.U okviru projekta u dosadašnjem radu ostvarena je podrška za nekoliko okruženja i kriterija raspoređivanja. Programska podrška obuhvaća alate za strojno učenje (evoluciju) heuristike raspoređivanja prilagođenu zadanoj okolini i kriteriju. Osim toga, ostvareni su alati za usporedbu postojećih algoritama (prilagodljivo po pitanju okruženja) s izvedenim heuristikama. Učenje i usporedba obavljaju se temeljem skupova ispitnih primjera koji su dostupni unutar rezultata projekta za podržane okoline ili mogu biti definirani od strane korisnika.
Trenutni paket programske podrške, ispitnih podataka i kompletne dokumentacije moguće je dohvatiti putem ove poveznice.
Budući rad uključuje integraciju sustava učenja s novim okruženjem za evolucijsko računanje (ECF, http://gp.zemris.fer.hr/ecf), mogućnost definiranja novih inačica okruženja i ograničenja u postupku raspoređivanja.
(u postupku recenzije) Evolving Priority Scheduling Heuristics with Genetic Programming
Dynamic Scheduling with
Genetic Programming
D. Jakobović, L. Budin, (2006) EuroGP 2006, Lecture Notes in Computer
Science 3905, pp. 73-84
(Dynamic Scheduling with
Genetic Programming: presentation in PDF)
Abstract: This paper investigates the use of genetic programming in automatized synthesis of scheduling heuristics. The applied scheduling technique is priority scheduling, where the next state of the system is determined based on priority values of certain system elements. The evolved solutions are compared with existing scheduling heuristics for single machine dynamic problem and job shop scheduling with bottleneck estimation.
Genetic Programming
Heuristics for Multiple Machine Scheduling
D. Jakobović, L. Jelenkovic, L. Budin, (2007) EuroGP 2007, Lecture Notes
in Computer Science 4445, pp. 321-330.
Abstract: In this paper we present a method for creating scheduling heuristics for parallel proportional machine scheduling environment and arbitrary performance criteria. Genetic programming is used to synthesize the priority function which, coupled with an appropriate meta-algorithm for a given environment, forms the priority scheduling heuristic. We show that the procedures derived in this way can perform similarly or better than existing algorithms. Additionally, this approach may be particularly useful for those combinations of scheduling environment and criteria for which there are no adequate scheduling algorithms.
Evolutionary Algorithms for
Solving Resource Constrained Scheduling Problem
Toni Frankola, Marin Golub, Domagoj Jakobovic (2008), Information
Technology Interfaces (ITI) 2008
Abstract: This paper investigates the use of evolutionary algorithms for solving resource constrained scheduling problem. This problem is in the class of NP complete problems. It involves finding optimal sequence of activities with given resource constraints. Evolutionary algorithms used in this paper are genetic algorithms and genetic programming, for which an adequate scheduling mechanism is defined. Presented solutions are compared with existing heuristic or optimal results.
Informatički projekt je financiran
od strane Ministarstva znanosti i tehnologije Republike Hrvatske
Zadnja promjena:
17. veljače 2011.
Za dodatne informacije:
domagoj.jakobovic@fer.hr