search query: @keyword logic programming / total: 8
reference: 2 / 8
« previous | next »
Author:Kylmälä, Lea
Title:University timetabling using answer set programming techniques
Yliopiston lukujärjestelmän laatiminen sääntöpohjaisella rajoiteohjelmoinnilla
Publication type:Master's thesis
Publication year:2010
Pages:vi + 55      Language:   eng
Department/School:Informaatio- ja luonnontieteiden tiedekunta
Main subject:Tietojenkäsittelyteoria   (T-119)
Supervisor:Niemelä, Ilkka
Instructor:Janhunen, Tomi
OEVS:
Electronic archive copy is available via Aalto Thesis Database.
Instructions

Reading digital theses in the closed network of the Aalto University Harald Herlin Learning Centre

In the closed network of Learning Centre you can read digital and digitized theses not available in the open network.

The Learning Centre contact details and opening hours: https://learningcentre.aalto.fi/en/harald-herlin-learning-centre/

You can read theses on the Learning Centre customer computers, which are available on all floors.

Logging on to the customer computers

  • Aalto University staff members log on to the customer computer using the Aalto username and password.
  • Other customers log on using a shared username and password.

Opening a thesis

  • On the desktop of the customer computers, you will find an icon titled:

    Aalto Thesis Database

  • Click on the icon to search for and open the thesis you are looking for from Aaltodoc database. You can find the thesis file by clicking the link on the OEV or OEVS field.

Reading the thesis

  • You can either print the thesis or read it on the customer computer screen.
  • You cannot save the thesis file on a flash drive or email it.
  • You cannot copy text or images from the file.
  • You cannot edit the file.

Printing the thesis

  • You can print the thesis for your personal study or research use.
  • Aalto University students and staff members may print black-and-white prints on the PrintingPoint devices when using the computer with personal Aalto username and password. Color printing is possible using the printer u90203-psc3, which is located near the customer service. Color printing is subject to a charge to Aalto University students and staff members.
  • Other customers can use the printer u90203-psc3. All printing is subject to a charge to non-University members.
Location:P1 Ark Aalto     | Archive
Keywords:university timetabling
answer set programming
logic programming
yliopiston lukujärjestyssuunnittelu
sääntöpohjainen rajoiteohjelmointi
logiikkaohjelmointi
Abstract (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.
Abstract (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.
ED:2010-08-26
INSSI record number: 40286
+ add basket
« previous | next »
INSSI