The search result changed since you submitted your search request. Documents might be displayed in a different sort order.
  • search hit 3 of 24
Back to Result List

Answer set programming as a modeling language for course timetabling

  • The course timetabling problem can be generally defined as the task of assigning a number of lectures to a limited set of timeslots and rooms, subject to a given set of hard and soft constraints. The modeling language for course timetabling is required to be expressive enough to specify a wide variety of soft constraints and objective functions. Furthermore, the resulting encoding is required to be extensible for capturing new constraints and for switching them between hard and soft, and to be flexible enough to deal with different formulations. In this paper, we propose to make effective use of ASP as a modeling language for course timetabling. We show that our ASP-based approach can naturally satisfy the above requirements, through an ASP encoding of the curriculum-based course timetabling problem proposed in the third track of the second international timetabling competition (ITC-2007). Our encoding is compact and human-readable, since each constraint is individually expressed by either one or two rules. Each hard constraint isThe course timetabling problem can be generally defined as the task of assigning a number of lectures to a limited set of timeslots and rooms, subject to a given set of hard and soft constraints. The modeling language for course timetabling is required to be expressive enough to specify a wide variety of soft constraints and objective functions. Furthermore, the resulting encoding is required to be extensible for capturing new constraints and for switching them between hard and soft, and to be flexible enough to deal with different formulations. In this paper, we propose to make effective use of ASP as a modeling language for course timetabling. We show that our ASP-based approach can naturally satisfy the above requirements, through an ASP encoding of the curriculum-based course timetabling problem proposed in the third track of the second international timetabling competition (ITC-2007). Our encoding is compact and human-readable, since each constraint is individually expressed by either one or two rules. Each hard constraint is expressed by using integrity constraints and aggregates of ASP. Each soft constraint S is expressed by rules in which the head is the form of penalty (S, V, C), and a violation V and its penalty cost C are detected and calculated respectively in the body. We carried out experiments on four different benchmark sets with five different formulations. We succeeded either in improving the bounds or producing the same bounds for many combinations of problem instances and formulations, compared with the previous best known bounds.show moreshow less

Download full text files

  • SHA-1: e0e24549597389ea15602a22d559f08a59471535

Export metadata

Additional Services

Search Google Scholar Statistics
Metadaten
Author details:Mutsunori Banbara, Takehide SohORCiD, Naoyuki TamuraORCiD, Katsumi Inoue, Torsten H. SchaubORCiDGND
URN:urn:nbn:de:kobv:517-opus4-415469
DOI:https://doi.org/10.25932/publishup-41546
ISSN:1866-8372
Title of parent work (English):Postprints der Universität Potsdam : Mathematisch Naturwissenschaftliche Reihe
Publication series (Volume number):Zweitveröffentlichungen der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe (594)
Publication type:Postprint
Language:English
Date of first publication:2019/02/12
Publication year:2013
Publishing institution:Universität Potsdam
Release date:2019/02/12
Tag:answer set programming; course timetabling; educational timetabling
Issue:594
Number of pages:16
First page:783
Last Page:798
Source:Theory and Practice of Logic Programming 13 (2013) 4-5, pp.783–798 DOI 10.1017/S1471068413000495
Organizational units:Mathematisch-Naturwissenschaftliche Fakultät
DDC classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Peer review:Referiert
Publishing method:Open Access
Grantor:Cambridge University Press (CUP)
License (German):License LogoKeine öffentliche Lizenz: Unter Urheberrechtsschutz
External remark:Bibliographieeintrag der Originalveröffentlichung/Quelle
Accept ✔
This website uses technically necessary session cookies. By continuing to use the website, you agree to this. You can find our privacy policy here.