DC FieldValueLanguage
dc.contributor.authorDemirović, Emir-
dc.contributor.authorMusliu, Nysret-
dc.contributor.otherDemirović, Emiir-
dc.date.accessioned2020-06-27T16:09:29Z-
dc.date.issued2016-
dc.identifier.issn1572-9338-
dc.identifier.urihttps://resolver.obvsg.at/urn:nbn:at:at-ubtuw:3-2878-
dc.identifier.urihttp://hdl.handle.net/20.500.12708/338-
dc.description.abstractHigh 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.sponsorshipAustrian Science Fund (FWF)-
dc.languageEnglish-
dc.language.isoen-
dc.publisherSpringer Science and Business Media-
dc.relation.ispartofAnnals of Operations Research-
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/-
dc.subjectSMTen
dc.subjectHigh school timetablingen
dc.subjectModelingen
dc.subjectBitvectorsen
dc.subjectLocal searchen
dc.titleModeling high school timetabling with bitvectorsen
dc.typeArticleen
dc.typeArtikelde
dc.relation.grantnoP24814-N23-
dc.rights.holderThe Author(s) 2016-
dc.type.categoryResearch Articleen
dc.type.categoryForschungsartikelde
tuw.versionvor-
dcterms.isPartOf.titleAnnals of Operations Research-
tuw.publication.orgunitE192 - Institut für Informationssysteme-
tuw.publisher.doi10.1007/s10479-016-2220-6-
dc.identifier.libraryidAC11361249-
dc.identifier.urnurn:nbn:at:at-ubtuw:3-2878-
dc.contributor.typeCorresponding author-
dc.rights.identifierCC BY 4.0-
item.languageiso639-1en-
item.openairetypeArticle-
item.openairetypeArtikel-
item.fulltextwith Fulltext-
item.cerifentitytypePublications-
item.cerifentitytypePublications-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.grantfulltextopen-
Appears in Collections:Article

Files in this item:

Show simple item record

Page view(s)

56
checked on Apr 13, 2021

Download(s)

192
checked on Apr 13, 2021

Google ScholarTM

Check


This item is licensed under a Creative Commons License Creative Commons