CONSTRAINT PROGRAMMING AND UNIVERSITY TIMETABLING

G.W. Groves, W. Van Wijck

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 industrie 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 industrie 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.)


Full Text:

PDF


DOI: https://doi.org/10.7166/13-1-314

Refbacks

  • There are currently no refbacks.




Copyright (c) 2015 The South African Journal of Industrial Engineering


ISSN 2224-7890 (on-line) ; ISSN 1012-277X (print)


Powered by OJS and hosted by Stellenbosch University Library and Information Service since 2011.


Disclaimer:

This journal is hosted by the SU LIS on request of the journal owner/editor. The SU LIS takes no responsibility for the content published within this journal, and disclaim all liability arising out of the use of or inability to use the information contained herein. We assume no responsibility, and shall not be liable for any breaches of agreement with other publishers/hosts.

SUNJournals Help