Timetabling Using the Ural-11B Electronic Digital Computer
Abstract Generated abstract
This article describes a program under development at the Tomsk Polytechnic Institute for compiling class timetables on the Ural-11B electronic digital computer. It formulates the scheduling problem as the distribution of teaching assignments across a planned period subject to constraints on instructors, student groups and subgroups, classroom capacity, special rooms, load balancing, and priority classes. The program is organized into three subprograms for preliminary sorting of input data, construction of time blocks and classroom allocation, and printed output of institute-wide schedules and available classroom stock. The described implementation supports timetabling for up to 1024 groups, 2048 instructors, and 512 classrooms, including both special-purpose and general rooms.
Full Text
PROCEEDINGS
of the Tomsk Polytechnic Institute
awarded the Order of the October Revolution
and the Order of the Red Banner of Labor
named after S. M. Kirov
Vol. 203 1974
TIMETABLING USING THE “URAL-11B” ELECTRONIC DIGITAL COMPUTER
N. M. BYLINO, L. A. EFIMOVA, I. E. NAATS, G. N. TARUSIN
(Submitted by the scientific seminar of the DCS Department, TPI)
This article gives a general description of a program being developed in the computing laboratory of the Tomsk Polytechnic Institute for compiling a timetable of classes with the aid of the “Ural-11B” machine.
Compiling a timetable of classes consists in distributing, in a certain order, a specified amount of teaching material while taking into account a number of constraints.
In the proposed program these constraints are as follows:
-
Each instructor, during one class period, works with only one group or with one subgroup (the exception is with several groups combined into a stream).
-
A student group, during one class period, is served by only one or two instructors.
-
A student group may be divided only into two subgroups.
-
The hours of classes must be distributed with allowance for an even student load over the planned period, with priority given to individual classes.
-
The maximum number of groups meeting in one classroom must not exceed its capacity. At the same time, several instructors may conduct classes in the classroom with several groups.
-
Some part of the classes must be held in a strictly specified special classroom (laboratory classes, etc.).
The program includes three subprograms:
- Preliminary sorting of information.
- Timetable compilation.
- Output of results.
The first subprogram organizes the input of lists of groups, faculties, the classroom stock, and teaching assignments for instructors [1]; it divides the list of assignments into elementary assignments and identifies classes that have priority (priority is given to such classes as physical education, lectures, etc.).
The second subprogram compiles the time timetable of classes and allocates the classroom stock.
The compilation of the time timetable reduces to identifying those classes that can take place simultaneously, or, in other words,
may be simultaneous in time. A set all of whose elements can be combined in time will hereafter be called a time block. Thus, a time schedule consists of a certain number of time blocks, each of which characterizes the state of instructional classes in the groups at a definite moment in time [2]. In the proposed program there are 48 such blocks, since the timetable is compiled for 12 days, with 4 two-hour periods each day.
Conventionally, each time block may be divided into a set of elements, each of which characterizes a strictly definite study group. The position of an element in a time block determines the number of the study group. An element occupies two full cells and has the following structure:
\[ \begin{array}{c|c|c|c} \alpha_1 & \varepsilon_1 & \alpha_2 & \varepsilon_2 \end{array} \]
\[ \begin{array}{ccccccccc} p & 0 & 11 & 12 & 23 & 24 & 35 & 36 & 47 \end{array} \]
\(\alpha_1\) and \(\alpha_2\) are the codes, respectively, of the first and second classrooms;
\(\varepsilon_1\) and \(\varepsilon_2\) are the codes, respectively, of the first and second instructor.
The presence of two instructors and two classrooms is due to the division of groups into two subgroups.
The third subprogram forms the institute-wide timetable from the elements of the time blocks and outputs it to the ACPU line printer in the form
| 9 h | 11 h | 13 h | 15 h | ||
|---|---|---|---|---|---|
| Faculty | Group code | ||||
| Days of the week | \(\alpha_1\varepsilon_1\alpha_2\varepsilon_2\) | \(\alpha_3\varepsilon_3\alpha_4\varepsilon_4\) | \(\alpha_5\varepsilon_5\alpha_6\varepsilon_6\) | \(\alpha_7\varepsilon_7\alpha_8\varepsilon_8\) |
The subprogram prints out the available classroom stock for every two hours of instructional classes.
All three subprograms work with the NML cabinet.
The proposed program makes it possible to compile a timetable for 1024 groups, 2048 instructors, 256 special-purpose and 256 general classrooms.
The first subprogram contains 1000 commands, the second 1500 commands, and the third 600 commands.
REFERENCES
-
N. M. Bylino, I. E. Naats, G. N. Tarusin. Problems of machine compilation of class timetables. Coding of initial information. (The present collection.)
-
I. E. Naats. Problems of algorithmization in compiling the time grid of a class timetable. Izv. TPI, vol. 187, 1974.