<div class="csl-bib-body">
<div class="csl-entry">Demirović, E., & Musliu, N. (2017). Modeling high school timetabling with bitvectors. <i>Annals of Operations Research</i>. https://doi.org/10.1007/s10479-016-2220-6</div>
</div>
High school timetabling (HSTT) is a well known and wide spread problem. The problem consists of coordinating resources (e.g. teachers, rooms), times, and events (e.g. lectures) with respect to various constraints. Unfortunately, HSTT is hard to solve and just finding a feasible solution for simple variants of HSTT has been proven to be NP-complete. We propose a new modeling approach for HSTT using bitvectors in which constraint costs of the general HSTT can be calculated using bit operations. This model allows efficient computation of constraint costs making it useful when implementing HSTT algorithms. Additionally, it can be used to solve HSTT with satisfiability modulo theory (SMT) solvers that support bitvectors. We evaluate the performance for our bitvector modeling approach and compare it to the leading engine KHE when developing local search algorithms such as hill climbing and simulated annealing. The experimental results show that our approach is useful for this problem. Furthermore, experimental results using SMT are given on instances from the ITC 2011 benchmark repository.
en
dc.description.sponsorship
Austrian Science Fund (FWF)
-
dc.language
English
-
dc.language.iso
en
-
dc.publisher
Springer
-
dc.relation.ispartof
Annals of Operations Research
-
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
-
dc.subject
SMT
en
dc.subject
High school timetabling
en
dc.subject
Modeling
en
dc.subject
Bitvectors
en
dc.subject
Local search
en
dc.title
Modeling high school timetabling with bitvectors
en
dc.type
Article
en
dc.type
Artikel
de
dc.rights.license
Creative Commons Namensnennung 4.0 International
de
dc.rights.license
Creative Commons Attribution 4.0 International
en
dc.relation.grantno
P24814-N23
-
dc.rights.holder
The Author(s) 2016
-
dc.type.category
Original Research Article
-
tuw.journal.peerreviewed
true
-
tuw.peerreviewed
true
-
tuw.version
vor
-
dcterms.isPartOf.title
Annals of Operations Research
-
tuw.publication.orgunit
E192 - Institut für Informationssysteme
-
tuw.publisher.doi
10.1007/s10479-016-2220-6
-
dc.date.onlinefirst
2016-07-22
-
dc.identifier.eissn
1572-9338
-
dc.identifier.libraryid
AC11361249
-
dc.identifier.urn
urn:nbn:at:at-ubtuw:3-2878
-
tuw.author.orcid
0000-0002-3992-8637
-
dc.rights.identifier
CC BY 4.0
de
dc.rights.identifier
CC BY 4.0
en
wb.sci
true
-
item.fulltext
with Fulltext
-
item.cerifentitytype
Publications
-
item.openairecristype
http://purl.org/coar/resource_type/c_2df8fbb1
-
item.languageiso639-1
en
-
item.openaccessfulltext
Open Access
-
item.openairetype
research article
-
item.grantfulltext
open
-
crisitem.author.dept
E184 - Institut für Informationssysteme
-
crisitem.author.dept
E192-02 - Forschungsbereich Databases and Artificial Intelligence