TIMETABLE SCHEDULING WITH NEURAL NETWORKS

Abstract

Connectionist systems have shown very promising results, particularly in 'low-level' perceptual and signal processing tasks. However, limited success was found in the application of parallel distributed processing to higher-level cognitive process and sequential symbol processing such as expert reasoning, planning and scheduling, and natural language processing. This thesis describes a conceptual hybrid neural networks model and a transputer implementation of a Timetable Scheduling system. In the hybrid model, scheduling tasks (classes) and resources (time slots and classrooms) are represented as distinct pools of neurons. Preference between a class and a resource is encoded as excitatory connection strength between neurons and prevention of a class from being assigned to a resource will be represented as inhibitory connection strength. The hybrid model embeds a Scheduling Network, based on the Interactive Activation and Competition model [Gros78] [McRu81] [McRu88], within a conventional A.I. scheduling framework. Under the conventional A.I. scheduling framework, classes are scheduled, in the order of most-constrained first, sequentially by the Scheduling Network, which parallelly searches and settles for the most appropriate resource combination for the class under simultaneous interaction of hard and soft constraints. Upon settling of the network, the selected resources, indicated by the winners of competition from each resource pool, are assigned to the class and the constraints induced by this assignment are propagated by appropriate weight adjustments. The next class is then selected for scheduling. Thus, classes are scheduled sequentially whereby each assignment is achieved by the parallel interactive activation and competition mechanism. Relaxation of soft constraints followed by user-intervention are performed when unsuccessful class assignment occurs. A quantitative measure for evaluating the quality of a schedule in terms of the preferences of resources has been proposed. The parallelization of the hybrid model's simulation on transputers adopts task decomposition. Independent groups of classes are scheduled by different transputers. After scheduling a class, the transputers exchange their scheduling results via message passing to detect possible conflict. If two classes are scheduled to the same time slot and classroom (a clash), the more constrained class will win the resources. A loosing transputer will have to reschedule its class while a winning transputer will go on to schedule its next classes. The simulation of the hybrid model and its parallelization use the Science Faculty Timetable Scheduling Problem as a testbed. 113 lecture classes of first year to third year (final year) undergraduate courses from 4 departments (Information Systems and Computer Science (hereafter, ISCS), Mathematics, Physics, Chemistry), and all the 89 tutorial/laboratory classes of the second year ISCS undergraduates are scheduled in the sequential simulation. For the parallel version, only the 113 lecture classes are considered. The scheduling results obtained from both sequential and parallel simulations are encouraging: no hard constraint is violated and all soft constraints considered are satisfied to a great extent. Scheduling with reduced number of classrooms as well as Grossberg's formulation of the Interactive Activation and Competition model [McRu88] [Gros78] have also been experimented.