The first step in constructing timetables in secondary schools in Netherlands consists of constructing the clusterschemes for the higher classes. A clusterscheme contains clusterlines with optional subjects that will be taught in parallel; the problem is to divide these optional subjects in clusterlines, such that the number of hours needed is as low as possible. We describe an efficient branch-and-bound method for this problem. Moreover we describe a fast heuristic to assign students to subjectgroups. Some test results are presented.
|Publisher||Department of Applied Mathematics, University of Twente|