ON AN ALGORITHM FOR SCHEDULING ACADEMIC CLASSES

N. M. Bylino, I. E. Naats, G. N. Tarusin

(Presented by the scientific seminar of the Department of Computational Mathematics)

Scheduling academic classes is one of the problems of scheduling theory. The use of computers for its solution is being studied in many countries: the USSR, Poland, the USA, England, the FRG, Canada, Australia, Belgium, Denmark, Norway, Switzerland, Scotland, Holland, Sweden, and India. There are a number of publications on theoretical solutions to this problem [1–10] and on practical results. This article presents an algorithm for solving the problem which was tested in compiling the timetable for the daytime division of Tomsk Polytechnic Institute (1500 instructors, 600 study groups, 500 classrooms), and gave a positive result. The basis for this algorithm was provided by publications [1–3].

In describing the algorithm, we use the matrix apparatus now accepted for this class of problems. We shall denote vectors and matrices by capital Latin letters with subscripts. In this notation, vectors will have one subscript, and matrices two or more subscripts. The elements of matrices and vectors will be denoted by lowercase Latin letters. Thus, a notation of the form $\bar{B}=\{b_i^j\}$ means the selection of a vector from the matrix $B=\{b_{ij}\}$ by the index $i$ with fixed $j$.

Let us introduce the following notation:

$\bar{L}=\{l_i\},\ i=1,2,\ldots,\alpha$ — the set of instructors;

$\bar{A}=\{a_q\},\ q=1,2,\ldots,\beta$ — the set of classrooms;

$\bar{T}=\{t_k\},\ k=1,2,\ldots,\gamma$ — the set of time intervals equal in duration to one class period (the set of periods);

$C=\{c_j\},\ j=1,2,\ldots,\Theta$ — the set of study groups.

The initial data in scheduling academic classes are:

1. Assignments to instructors for the planned period. Each assignment is an individual task for one instructor, in which the following are indicated: the type of discipline that the instructor is to conduct; the numbers of all groups in which the instructor is to conduct classes; the number of class hours and other requirements determined by the specific educational institution.

All assignments are reduced to the initial matrix of instructors’ assignments $P$, each element of which, $P_{ij}$, represents the number of classes that instructor $l_i$ must conduct in group $c_j$ in [[unclear: text continues on next page]]

interval for which the schedule is being drawn up. In the general case the matrix may be multidimensional and, in addition to temporal relations between teachers and groups, may reflect intergroup relations (if groups are divided into subgroups), relations among teachers in cases where classes are conducted by a group of teachers; relations with classrooms (if classes must be held using special equipment), relations with periods (if classes must be held at a strictly specified time), and other relations determined by the particular educational institution.

1. The list of the classroom stock of the educational institution, indicating the time during which a classroom may be made available for classes. This list is reduced to the initial matrix of classroom time reserves \(A\), each element of which, \(a_{qk}\), takes the value 1 if classroom \(a_q\) can be used for classes in period \(t_k\), and the value 0 if it cannot (repairs, conferences, etc.).

In the general case this matrix, like the preceding one, may be multidimensional if it is necessary to take into account capacity and the availability of special equipment.

1. Teachers’ requests for release from classes for a specified period of time (part-time work in other organizations, family circumstances, public assignments, etc.). These requests are represented in the form of the initial matrix of teachers’ time reserves \(L\). This is a two-dimensional Boolean matrix, each element of which, \(l_{ik}\), takes the value 1 if teacher \(l_i\) can conduct classes in period \(t_k\), and the value 0 if he cannot.

2. The stock of instructional time of the groups is reduced to the initial matrix of group time reserves \(C\)—a two-dimensional Boolean matrix, each element of which, \(c_{jk}\), takes the value 1 if group \(c_j\) can attend classes in period \(t_k\), and the value 0 if it cannot (industrial practice, etc.).

In light of the structure of the initial matrices analyzed above, the problem of constructing a schedule will have the following formulation.

Using the initial matrix of assignments to teachers \(P\), the initial matrix of teachers’ time reserves \(L\), the initial matrix of group time reserves \(C\), and the initial matrix of classroom time reserves \(A\), form the schedule matrix \(S\), taking into account the conditions listed below:

\[ \sum_{jq} s_{ijq}^{k} \leqslant 1 \quad \text{for all values of } i,\, k; \tag{1} \]

\[ \sum_{iq} s_{ijq}^{k} \leqslant 1 \quad \text{for all values of } j,\, k; \tag{2} \]

\[ \sum_{ij} s_{ijq}^{k} \leqslant 1 \quad \text{for all values of } q,\, k. \tag{3} \]

Conditions (1–3) state the fact that in the schedule \(S\), in any of the periods \(t_k\), each of the teachers \(l_i\), each group \(c_j\), and each classroom \(a_q\) can support no more than one class.

The schedule matrix \(S\) is a four-dimensional Boolean matrix; each element \(s_{ijqk}\) takes the value 1 if teacher \(l_i\) conducts a class in group \(c_j\), in classroom \(a_q\), in the time interval \(t_k\), and the value 0 if there is no class. In the general case the schedule matrix may have dimensionality greater than four.

We now proceed to the description of the algorithm for constructing the schedule, which can be broken down into a number of consecutive operations.

1. If the number of schedule periods is limited, then before the construction of the schedule begins, fulfillment of the condition is checked.

\[ p_{ij} \leq \sum_k t_k \quad \text{for all values of } i, j. \tag{4} \]

If condition (4) is not satisfied, then the placement of all assignments in the timetable is impossible. In this case, condition (4) can be satisfied either by reducing those \(p_{ij}\) that exceed the total number of timetable periods, or by increasing the number of timetable periods.

1. Before drawing up the timetable, the following conditions are checked:

\[ \text{Satisfaction of the condition } \sum_j p_i^j \leq \sum_k l_i^k \quad \text{for all values of } i \tag{5} \]

is a guarantee that instructor \(l_i\) has a sufficient number of reserve hours to carry out the assignments.

\[ \text{Satisfaction of the condition } \sum_i p_j^i \leq \sum_k c_j^k \quad \text{for all values of } j \tag{6} \]

is a guarantee that group \(c_j\) has a sufficient number of reserve hours to carry out the assignments.

\[ \text{The condition } \sum_{ij} p^{ij} \leq \sum_{qk} a^{qk} \quad \text{for all values of } i, j, q, k \tag{7} \]

determines the guarantee that there is a sufficient number of classrooms \(a_q\) for holding classes. In the event that at least one of conditions (5–7) is not satisfied, drawing up the timetable is impossible.

1. The assignments are placed in the timetable matrix sequentially in each period.

Suppose that a timetable is being drawn up for the period \(t_k\). The placement process begins with the selection, in the assignment matrix, of an element of the assignment matrix \(p_{ij} \ne 0\). Since usually several elements of the matrix satisfy such an inequality, the choice of the element may be made either purely at random or purposefully (taking priority into account). For the selected element of the matrix corresponding to \(i\) and \(j\), the elements of the matrices \(l_{ik}\), \(c_{jk}\), \(a_{qk}\) are found in the matrix of instructors’ time reserve \(L\), the matrix of groups’ time reserve \(C\), and the matrix of classroom reserve \(A\) for the given period \(t_k\). If \(l_{ik} \ne 0\), \(c_{jk} \ne 0\), \(a_{qk} \ne 0\) (i.e., instructor \(l_i\), group \(c_j\), and classroom \(a_q\) are free in period \(t_k\)), then in the timetable matrix the element \(s_{ijqk}\) is assigned the value 1. The elements \(l_{ik}\), \(c_{jk}\), \(a_{qk}\) are assigned the value 0. The element \(p_{ij}\) of the instructors’ assignment matrix is assigned the value \(p_{ij} - 1\).

If at least one of the elements \(l_{ik}\), \(c_{jk}\), \(a_{qk}\) is equal to 0, then one proceeds to the next element of the assignment matrix and carries out the entire placement process from the very beginning. Assigning the value 1 to the element \(s_{ijqk}\) of the timetable matrix completes one placement cycle.

1. The satisfaction of the condition is checked

\[ \sum_{ij} p^{ij} = 0 \quad \text{for all values of } i, j. \tag{8} \]

If condition (8) is not satisfied, then the satisfaction of conditions (5–7) is checked. If any of conditions (5–7) is not satisfied, then the placement process is terminated, since in this case the problem has no solution and the incomplete matrix \(S\) is erased. However, it makes no sense to judge from the first attempt the possibility of drawing up a timetable, since the choice of elements of matrix \(P\) for placement is random.

It is advisable to repeat the process of drawing up the timetable, beginning with item 4, while changing either the order of selecting elements from the assignment matrix or the initial data.

If conditions (5–7) are satisfied, one proceeds to place the next assignment of the matrix \(P\). The placement process in the period \(t_k\) is considered complete if all elements of the matrix \(P\) have been examined or if conditions (9–11) are satisfied:

\[ \sum_{jq} s_{ijq}^{k}=1 \quad \text{for all values of } i,\ k; \tag{9} \]

\[ \sum_{iq} s_{ijq}^{k}=1 \quad \text{for all values of } j,\ k; \tag{10} \]

\[ \sum_{ij} s_{ijq}^{k}=1 \quad \text{for all values of } q,\ k. \tag{11} \]

The fulfillment of conditions (9–11) means that each instructor, each study group, and each classroom has, in the given period, one class each. After this one proceeds to compile the timetable for the period \(t_k+1\) (item 2).

If, in formulating the problem, it is specified that there must be no gaps in the timetable for groups, then after compiling the timetable for any period \(t_k\), except the last ones, it is necessary to check fulfillment of condition (10). If it is necessary to have no gaps for instructors, then fulfillment of condition (9) should be checked. When classroom capacity is to be used to the maximum, condition (11) should be checked. Failure of these conditions indicates the impossibility of solving the problem for the given attempt.

The algorithm set out above for the time being makes it possible to compile a timetable that is, in a certain sense, random; that is, for the given assignments, other timetable variants are also possible. Therefore it makes sense to compile several timetables and choose from them the one which, to one degree or another, satisfies local requirements as to the minimum number of gaps for groups and instructors, maximum use of the classroom stock, and so on.

REFERENCES

1. C. C. Gottlieb. Hrsg. Bibliography, Institute of Computer Science, University of Toronto, 1963.

2. G. R. Sherman. A Combinatorial Problem Arising from Scheduling University Classes. Journal of the Tennessee Academy of Science 38, 116—117, 1963.

3. M. Almond. An algorithm for constructing University timetable. Computer J. 8, 4, 331—340, 1966.

4. C. C. Gotlib. The construction of class—teacher time—tables. Proc. IFIP Congress, 62, Munich North Holland Pabl. Co Amsterdam 73—77, 1963.

5. P. Stahlkuecht, Zur electronichen Berechnung von Stundenplänen, Elektron, Datenverarb, 6, 2, 85—91, 1964.

6. Dipl.—Hath. Hartman Jochen Genrith, Rheinisch—Westfalisches Institut für Instrumentale Mathematik Bonn (IIM) Nr 1713 (Nr II der Schriften des IIM. Serie A). Die automatische Aufstellung von Schulstundenplanen auf refetationen theoretisher Grundlage, Westdeutsher verlag, Köln und Opladen, 1966.

7. R. Guuzenhauser, W. Zunginger. Über eine methode Zur Erstellung von Schulstundenplanen mit Hilfe einer Ziffernrechenanlagen, Mathematic—Technik—Wortschaft (Austria) 11, 3, 100—104, 1964.

8. R. Guuzenhauser, W. Iunginger. Ein Programm fur electronischen Berechnung von Stundenplanen Electron. Datenverarb, 6, 5, 212—215, 1964.

9. J. Csima, C. C. Gottlieb. Tests on a Computer method for Constructiug School Timetables, Communications of the ACM, 7, 3, 160—163, Bibl. 14. March 1964.

10. J. S. Applaby, D. V. Blake, E. A. Newman, Techniques for Producing School Timetables on a Computer and their Applications to other Scheduling Problem. The Computer Journal, 3, 4, 237—245, Jon 1961.

11. A. N. Laferov. Development of a methodology for the use of computing equipment for automating the compilation of academic class timetables. R-756. (STL TPI), Tomsk, 1966.