Skip Navigation

The Computer Journal 1990 33(4):356-364; doi:10.1093/comjnl/33.4.356
© 1990 by British Computer Society
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (4)
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Feldman, R.
Right arrow Articles by Golumbic, M. C.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Optimization Algorithms for Student Scheduling via Constraint Satisfiability

R. Feldman1 * and M. C. Golumbic2 §

1 Department of Mathematics and Computer Science, Bar-Ilan University, Ramat Gan, Israel, 2 IBM Israel Scientific Center, Technion City, Haifa, Israel

Techniques for solving constraint satisfiability problems have received much attention in artificial intelligence, operation research and symbolic logic. Applications which may be viewed as CSPs are found in scene identification in computer vision, space and motion planning, database consistency, combinatorial optimization, and cryptarithm puzzle solving.

Our research effort attempts to determine which algorithms perform best, and under what conditions, in solving a special CSP known as the student scheduling problem (SSP). Since constraint satisfiability problems are, in general, NP-complete, it is of interest to develop and compare the effectiveness and efficiency of heuristic algorithms as applied, in particular, to our application.

In this paper, we assign priorities to the constraints and investigate optimization algorithms for finding schedules which rank high with respect to the priorities. Experimental results have been collected and are reported here. Our system was developed for and used at Bar-Ilan University during the registration period, being available for students to construct their timetables.

Received June 1989. revised October 1989.

* Department of Mathematics and Computer Science, Bar-Ilan University, Ramat Gan, Israel

§ IBM Israel Scientific Center, Technion City, Haifa, Israel

Current address: Department of Computer Science, Cornell University, Ithaca, New York 14853, U.S.A.

{ddagger} Currently on leave at the IBM Watson Research Center, P.O.Box 704, Yorktown Heights, New York 10598, U.S.A.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.