haku: @instructor Janhunen, Tomi / yhteensä: 12
viite: 5 / 12
| Tekijä: | Kylmälä, Lea |
| Työn nimi: | University timetabling using answer set programming techniques |
| Yliopiston lukujärjestelmän laatiminen sääntöpohjaisella rajoiteohjelmoinnilla | |
| Julkaisutyyppi: | Diplomityö |
| Julkaisuvuosi: | 2010 |
| Sivut: | vi + 55 Kieli: eng |
| Koulu/Laitos/Osasto: | Informaatio- ja luonnontieteiden tiedekunta |
| Oppiaine: | Tietojenkäsittelyteoria (T-119) |
| Valvoja: | Niemelä, Ilkka |
| Ohjaaja: | Janhunen, Tomi |
| OEVS: | Sähköinen arkistokappale on luettavissa Aalto Thesis Databasen kautta.
Ohje Digitaalisten opinnäytteiden lukeminen Aalto-yliopiston Harald Herlin -oppimiskeskuksen suljetussa verkossaOppimiskeskuksen suljetussa verkossa voi lukea sellaisia digitaalisia ja digitoituja opinnäytteitä, joille ei ole saatu julkaisulupaa avoimessa verkossa. Oppimiskeskuksen yhteystiedot ja aukioloajat: https://learningcentre.aalto.fi/fi/harald-herlin-oppimiskeskus/ Opinnäytteitä voi lukea Oppimiskeskuksen asiakaskoneilla, joita löytyy kaikista kerroksista.
Kirjautuminen asiakaskoneille
Opinnäytteen avaaminen
Opinnäytteen lukeminen
Opinnäytteen tulostus
|
| Sijainti: | P1 Ark Aalto | Arkisto |
| Avainsanat: | university timetabling answer set programming logic programming yliopiston lukujärjestyssuunnittelu sääntöpohjainen rajoiteohjelmointi logiikkaohjelmointi |
| Tiivistelmä (fin): | Yliopistojen lukujärjestykset ovat suuria, monimutkaisia ja pieni määrä virheitä jää huomaamatta tai ratkaisematta. Suunnitteluprosessin automatisointi voi säästää aikaa huomattavasti ja poistaa virheet. Automatisointi voi myös vapauttaa suunnittelijalle aikaa muulle työlle, kun tietokone tekee suunnittelun mekaanisen osan. Tässä työssä kehitetään ohjelmisto yliopiston lukujärjestyssuunnitteluun luku- ja tenttikausia varten. Ohjelmisto käyttää sääntöpohjaista rajoiteohjelmointijärjestelmää (Answer Set Programming, ASP) lukujärjestysongelman ratkaisemiseen, tietokantaa tiedon tallentamiseen ja selainpohjaista käyttöliittymää sekä suunnittelijoille, että luennoijille. Työn lisätavoitteita ovat sääntöpohjaisen rajoiteohjelmoinnin soveltuvuuden tutkiminen tällaiseen suunnitteluun sekä hakuavaruuden pienentäminen rajoittamatta oleellisesti itse lukujärjestyksen muotoa. Tässä työssä määritellään yleiset säännöt luku- ja tenttikauden lukujärjestyksiä varten. Lisäksi esitetään näiden sääntöjen muunnokset rajoiteohjelmoinnille. Työssä kuvataan myös, miten formaali vastaus muutetaan takaisin oikeaksi lukujärjestykseksi. Ohjelmistoa testattiin täydellä Tietojenkäsittelytieteen laitoksen ja Tietotekniikan laitoksen kurssitarjonnalla. Lukukausijärjestyksen testauksessa käytettiin 67:ää kurssia ja kaikkia lukukauden viikkoja. Tenttikauden testauksessa käytettiin 63:a tenttiä. Nämä syötettiin järjestelmään ja käyttöliittymällä lisättiin erilaisia rajoitteita kurssitiedoille, jotka sitten annettiin rajoiteohjelmointiratkaisimelle. Ratkaisu tuotiin käyttöliittymän kautta takaisin tietokantaan, jonka jälkeen sitä voitiin tarkastella. Ohjelmiston kehittämis- ja testaustulokset viittaavat siihen, että sääntöpohjaisen rajoiteohjelmoinnin yksisuuntaiset säännöt sopivat hyvin lukujärjestyssääntöjen kuvaamiseen ja mahdollistavat modulaarisen koodin. Ratkaisuajat myös viittaavat sääntöpohjaisen rajoiteohjelmoinnin sopivan lukujärjestyksen tekemiseen. Hakuavaruuden rajoittaminen onnistui myös, joiltain osin jopa huomattavasti. Yliopistotason lukujärjestyksien suunnittelun automatisointi on mahdollista ja erittäin kannattavaa. Sääntöpohjainen rajoiteohjelmointi sopii hyvin tähän työhön ja ongelman rajoiteohjelmointikuvausta kannattaa kehittää, kuten myös käyttöliittymää. Muita parannuksia ovat yhteydet muihin yliopiston järjestelmiin automaattisen tiedonsiirron takia. |
| Tiivistelmä (eng): | University timetables are big, complex, and a small amount of errors often remains undetected or unresolved. Therefore, automating the design process can be a great time saver, along with removing errors from the timetables. This can also free up a lot of time for other work by the designer, since a computer does the mechanical part of the work. In this thesis we develop a University Timetabling System (UTS) for semester and exam period timetabling. The UTS uses Answer Set Programming (ASP) techniques for solving an instance of the timetabling problem, a database for storing data, and a web based user interface for both the designer and lecturers. Studying how well ASP is suited for this task and how to limit the search space size, without essentially limiting the form of the timetable, are additional goals of this work. We define general rules describing a university timetable for a semester and an exam period and formalize them using an ASP representation. We also describe how the formalized solution is translated to a real world timetable. The system is tested with the full course load offered by the Department of Information and Computer Science and the Department of Computer Science and Engineering. The semester timetabling was tested with 67 courses and all the weeks of a semester and the exam period was tested with 63 exams. These are loaded into the system and the user interface is then used to input various additional limitations for the data, which is then exported to an ASP solver for solving. The solution is then imported back into the database via the user interface for review. The results of using and developing the UTS indicate that the asymmetric constraints of ASP are well suited to describing the rules of a timetable, allowing the constraints to be written using modular rules. Solving times also indicate that ASP is suited to solving timetabling problems. Limiting the size of the search space for the timetabling problem domain was also found to be possible, in some cases considerably. Automating university timetabling is possible and well worth the effort. ASP techniques are well suited to this task and further development of the ASP representation and user interface is recommended. Other needed improvements are interfaces to other university systems to facilitate automatic data transfer. |
| ED: | 2010-08-26 |
INSSI tietueen numero: 40286
+ lisää koriin
INSSI