Lineaarisen kokonaislukuoptimoinnin hyödyntäminen lukujärjestysten muodostamisessa
Vehmaanperä, Milja (2016)
2016
Teknis-luonnontieteellinen koulutusohjelma
Luonnontieteiden tiedekunta - Faculty of Natural Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2016-06-08
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tty-201605254088
https://urn.fi/URN:NBN:fi:tty-201605254088
Tiivistelmä
Automatisoitu aikataulujen luominen on haastava tutkimusala, johon kuuluvat myös koulujen ja yliopistojen lukujärjestykset. Tässä työssä luodaan yleiskatsaus lukujärjestysongelmaan sekä muodostetaan ja ratkaistaan esimerkkiongelma kahdella eri kustannusfunktiolla.
Lukujärjestysten muodostamisessa on kyse oppimistapahtumien ja resurssien eli opettajien, oppilasryhmien sekä opetustilojen jakamisesta eri aikaväleille, eli tunneille, tiettyjä rajoitteita noudattaen. Automatisoidussa lukujärjestysten luomisessa voidaan käyttää hyödyksi esimerkiksi lineaarista binäärilukuoptimointia. Tähän optimointimalliin luodaan rajoitteet ja kustannusfunktio, jonka arvo pyritään optimoimaan rajoitteita noudattaen. Rajoitteet voivat olla joko kovia tai pehmeitä ja ne voivat vaihdella tapauksittain. Kovien rajoitteiden on toteuduttava, jotta lukujärjestys voidaan muodostaa, kun taas kustannusfunktioon sisältyvien pehmeiden rajoitteiden avulla määritetään muodostettavan lukujärjestyksen laatu.
Eri pehmeille rajoitteille voidaan antaa erisuuruiset painoarvot sen mukaan, kuinka tärkeinä niiden toteutumista pidetään verrattuna muihin pehmeisiin rajoitteisiin. Tämän työn esimerkkitapauksessa kustannusfunktion avulla minimoidaan hyppytuntien määrää ja opetustilojen käytöstä aiheutuvia kustannuksia. Mikäli oppimistapahtumia on melko vähän, kuten tässä työssä, nämä kaksi optimoitavaa tekijää eivät riitä muodostamaan mielekkäitä lukujärjestyksiä. Lukujärjestyksiin muodostuu yksittäisen oppimistapahtuman päiviä, mikä ei ole toivottavaa. Täten laadukkaiden lukujärjestysten luomiseksi tarvitsee kustannusfunktioon sisällyttää myös muita pehmeitä rajoitteita.
Lukujärjestysten muodostamisessa on kyse oppimistapahtumien ja resurssien eli opettajien, oppilasryhmien sekä opetustilojen jakamisesta eri aikaväleille, eli tunneille, tiettyjä rajoitteita noudattaen. Automatisoidussa lukujärjestysten luomisessa voidaan käyttää hyödyksi esimerkiksi lineaarista binäärilukuoptimointia. Tähän optimointimalliin luodaan rajoitteet ja kustannusfunktio, jonka arvo pyritään optimoimaan rajoitteita noudattaen. Rajoitteet voivat olla joko kovia tai pehmeitä ja ne voivat vaihdella tapauksittain. Kovien rajoitteiden on toteuduttava, jotta lukujärjestys voidaan muodostaa, kun taas kustannusfunktioon sisältyvien pehmeiden rajoitteiden avulla määritetään muodostettavan lukujärjestyksen laatu.
Eri pehmeille rajoitteille voidaan antaa erisuuruiset painoarvot sen mukaan, kuinka tärkeinä niiden toteutumista pidetään verrattuna muihin pehmeisiin rajoitteisiin. Tämän työn esimerkkitapauksessa kustannusfunktion avulla minimoidaan hyppytuntien määrää ja opetustilojen käytöstä aiheutuvia kustannuksia. Mikäli oppimistapahtumia on melko vähän, kuten tässä työssä, nämä kaksi optimoitavaa tekijää eivät riitä muodostamaan mielekkäitä lukujärjestyksiä. Lukujärjestyksiin muodostuu yksittäisen oppimistapahtuman päiviä, mikä ei ole toivottavaa. Täten laadukkaiden lukujärjestysten luomiseksi tarvitsee kustannusfunktioon sisällyttää myös muita pehmeitä rajoitteita.