Title

Algorithms and heuristics for combinatorial optimization problems: Case study of academic course scheduling

Date of Award

12-2000

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Electrical Engineering and Computer Science

Advisor(s)

Geoffrey Fox

Keywords

Heuristics, Combinatorial optimization, Academic course scheduling

Subject Categories

Computer Sciences | Databases and Information Systems

Abstract

In this dissertation we try to answer the following question: How do we go about solving the problem of academic scheduling at the university level, in particular? we give a detailed answer to this question, and shed some light on the case of tackling optimization problems in general. Combinatorial optimization problems involve choosing the best solution from a finite set of mutually exclusive outcomes and are often deceptively difficult to solve. To summarize, we have investigated a variety of optimization algorithms, in particular, random search, hill climbing, knowledge-based systems (or rule-based expert systems), mean-field annealing, and simulated annealing methods to solve a large scale optimization problem, namely university academic course scheduling, represented as generalized assignment-type problems. The core heuristics of our approach are annealing-based and include mean-field annealing, simulated annealing with three different cooling schedules, and the use of two types of preprocessors, namely rule-based and graph coloring. Moreover, preprocessors are only used with simulated annealing to provide a good starting point for the algorithm. Along with the use of preprocessing we also have investigated a number of techniques to accelerate (i.e. 'speed up') the convergence of annealing to a good quality solution. These techniques include the selection of appropriate annealing schedules and subsequent parameter fine-tuning, as well as recording the best solution encountered in an annealing run. In terms of convergence speedup as well as solution quality, the best results were obtained using simulated annealing with adaptive cooling and reheating as a function of cost, and a rule-based preprocessor. This approach enabled us to obtain valid schedules for the course scheduling problem for a large University, using a complex cost function that includes student preferences. None of the other methods we investigated were able to provide a complete valid schedule. The same approach using a graph-coloring preprocessor did extremely well but not as well as the approach with the rule-based preprocessor.

Access

Surface provides description only. Full text is available to ProQuest subscribers. Ask your Librarian for assistance.

http://libezproxy.syr.edu/login?url=http://proquest.umi.com/pqdweb?did=727949331&sid=1&Fmt=2&clientId=3739&RQT=309&VName=PQD

Link to Full Text

Share

COinS