Constraint programming and university timetabling
Date
2002
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
SAIIE
Abstract
ENGLISH ABSTRACT: The technology of Constraint Programming is rapidly becoming a popular alternative for
solving large-scale industry problems. This paper provides an introduction to Constraint
Programming and to Constraint Logic Programming (CLP), an enabler of constraint
programming. The use of Constraint Logic Programming is demonstrated by describing a
system developed for scheduling university timetables. Timetabling problems have a high
degree of algorithmic complexity (they are usually NP-Complete), and share features with
scheduling problems encountered in industry. The system allows the declaration of both hard
requirements, which must always be satisfied, and soft constraints which need not be
satisfied, though this would be an advantage.
AFRIKAANSE OPSOMMING: Hierdie artikel beskryf ’n familie van probleem-oplossingstegnieke bekend as “Constraint Programming”, wat al hoe meer gebruik word om groot-skaalse industriële probleme op te los. Die nut van hierdie tegnieke word gedemonstreer deur die beskrywing van ’n skeduleringsisteem om die roosters vir ’n universiteit te genereer. Roosterskeduleringsprobleme is in praktiese gevalle NP-volledig en deel baie eienskappe met industriële skeduleringsprobleme. Die sisteem wat hier beskryf word maak gebruik van beide harde beperkings (wat altyd bevredig moet word) en sagte beperkings (bevrediging hiervan is wel voordelig maar dit is opsioneel.)
AFRIKAANSE OPSOMMING: Hierdie artikel beskryf ’n familie van probleem-oplossingstegnieke bekend as “Constraint Programming”, wat al hoe meer gebruik word om groot-skaalse industriële probleme op te los. Die nut van hierdie tegnieke word gedemonstreer deur die beskrywing van ’n skeduleringsisteem om die roosters vir ’n universiteit te genereer. Roosterskeduleringsprobleme is in praktiese gevalle NP-volledig en deel baie eienskappe met industriële skeduleringsprobleme. Die sisteem wat hier beskryf word maak gebruik van beide harde beperkings (wat altyd bevredig moet word) en sagte beperkings (bevrediging hiervan is wel voordelig maar dit is opsioneel.)
Description
CITATION: Groves, G. W. & Van Wijck, W. 2002. Constraint programming and university timetabling. South African Journal of Industrial Engineering, 13(1):1-12, doi:10.7166/13-1-314.
The original publication is available at http://sajie.journals.ac.za
The original publication is available at http://sajie.journals.ac.za
Keywords
Logic programming, Constraint programming (Computer science), Universities and colleges -- Timetables
Citation
Groves, G. W. & Van Wijck, W. 2002. Constraint programming and university timetabling. South African Journal of Industrial Engineering, 13(1):1-12, doi:10.7166/13-1-314