Älykkäät algoritmit ja aikataulutusongelmat

Vaikeiden aikataulutusongelmien mahdollisimman hyvällä ratkaisemisella on sekä taloudellista että yhteiskunnallista merkitystä. Esimerkkeinä ongelmista mainittakoon teollisuuden tuotantolinjojen optimointi, tehtaiden ja sairaaloiden työvuorolistojen laatiminen, oppilaitosten lukujärjestysten tekeminen, joukkoliikenteen aikatauluttaminen sekä urheilun sarjaohjelmien laatiminen.

SAMKin aikataulutustutkimuksen kohteena ovat tähän mennessä olleet lukujärjestysongelmat, urheilun sarjaohjelmat ja työvuorolistojen laatiminen. Seuraavana sovelusalueena on joukkoliikenteen aikatauluttaminen. SAMKin yhteistyökumppaneita ovat mm. Jääkiekon SM-liiga, Mestis ja Turun Liikennelaitos.

Tutkimustulokset ovat sijoittuneet kansainväliseen kärkeen. SAMK vetää kansainvälistä tutkimusyhteistyötä, jonka tavoitteena on muodostaa yhtenäinen näkemys sarjaohjelmaongelmasta, kehittää sen ratkaisemiseen soveltuvia laskennallisia menetelmiä sekä luoda kaikille tutkijoille avoin käytännön ongelmia esittelevä tutkimussivusto. Yhteistyössä on mukana tutkijoita Saksasta, Belgiasta, Argentiinasta, Brasiliasta, Chilestä ja USAsta. Lisäksi SAMK on mukana lukujärjestysongelmaa tutkivassa yhteistyöryhmässä, jossa on tutkijoita Hollannista, Englannista, Kreikasta, Italiasta, Brasiliasta ja Australiasta.

Koska aikataulutusongelmat ovat erittäin vaikeita laskennallisia ongelmia, täytyy niiden ratkaisemiseksi kehittää älykkäitä algoritmeja, jotka etsivät ongelmaan parhaan järkevässä ajassa löydettävissä olevan ratkaisun. Ratkaisemisessa tarvitaan innovatiivista tutkimusotetta, laadukasta ohjelmointitaitoa ja laskennallisesti tehokkaita tietokoneita. Käytettävät tutkimusmenetelmät ovat evoluutioalgoritmien,
muurahaisoptimoinnin, paikallisheuristiikkojen ja tilastollisten menetelmien hybridejä.

Tärkeimpänä tutkimustuloksena on, että aiemmin mainituilla sovellusalueilla saadaan ratkaistua käytännön ongelmia, jotka otetaan tuotantokäyttöön. Merkittävien tieteellisten läpimurtojen tekeminen on juuri nyt ajankohtaista, koska

1. Tutkimusryhmä on kyennyt kombinoidaan ideoitaan älykkäiksi laskennallisiksi menetelmiksi
2. Kehitetyt algoritmit on saatu koodattua erittäin tehokkaiksi tietokoneohjelmiksi
3. Tietokoneet ovat kehittyneet sille tasolle, että ne ovat riittävän nopeita haastavissa laskennallisissa tehtävissä käytännön sovellusalueilla.

TUTKIMUSPARTNERIT

University of Buenos Aires, Argentina
University of Sydney, Australia
Catholic University of Leuven, Belgium 
Federal University of Minas Gerais, Brazil
Fluminense Federal University, Brazil
Universidade Federal de Ouro Preto, Brazil
University of Chile, Chile
De Montfort University, England
Christian-Albrechts-Universität of Kiel, Germany
University of Patras, Greece 
Reykjavik University, Iceland
University of Udine, Italy
University of Leiden, Netherlands
University of Twente, Netherlands

Lisätietoja: ,

Lue lisää: Sports Scheduling Problem, School Timetabling Problem ja Benchmarking project for School Timetabling

Julkaisuluettelo (PDF)