Issues in Algorithmizing the Construction of a Time Grid for Class Scheduling

I. E. NAATS

(Presented by the scientific seminar of the computing laboratory)

In the general problem of algorithmizing the process of compiling a timetable of classes, a number of independent questions may be singled out. These are, above all, such tasks as the distribution of teaching load among instructors, the construction of the time grid of the timetable, and the distribution of the classroom stock. The first task lies somewhat apart from the problem of automating timetable compilation and is not considered in the present work. Its solution is connected with questions of the scientific organization and planning of the pedagogical work of instructors as one of the specific forms of human activity. Unfortunately, this area of research attracts little attention from specialists, and at present there are no recommendations whatever on this matter.

The second task is the most significant in terms of the manual labor expended by the compiler. The present article is devoted to the study of questions concerning the construction of the time grid of the timetable and to the development of algorithms for automated compilation on computers. The third task is the subject of an independent study and is not considered in the present work.

Basic concepts. Definition of the logical structure of the algorithm for constructing the time grid of the timetable

Before proceeding to the analysis and definition of the structure of the algorithm, it is necessary to introduce concepts in terms of which a formal and unambiguous description of the entire sequence of operations for constructing the time grid of the class timetable is possible. Let us introduce the concept of a timetable element.

Definition 1. By a timetable element we shall mean an expression of the form

\[ A\{abc\ldots\}. \]

In the general case the symbols \(A, a, b, c\ldots\) may have alphabetic, alphanumeric, and numeric designations.

\(A\) is called the index of the element; the expression in braces is called the characteristic of the element. The index expresses the code of the instructor, and the char—

characteristic—the groups in which he conducts the given class. For example, the notation

\[ A\{12345678\} \]

means that instructor \(A\) conducts a class simultaneously in eight groups, whose numbers are conventionally denoted by the digits 1, 2, ... 8. The notation \(B\{00045000\}\) means that instructor \(B\) conducts a class simultaneously with groups 4 and 5 out of the eight under consideration.

If all the symbols of the characteristic, with the exception of one, are 0, this means that the instructor with the given index conducts a class in only one group, whose number is different from zero. Such elements, as a rule, denote practical classes. Elements denoting lecture classes have at least two nonzero symbols. Thus, in constructing the characteristic of an element, the positional principle is used, i.e., the absence of a class or its presence in a given group is denoted by the placement of the zero symbol or the group number in a definite position of the characteristic. In this connection, another, purely semantic definition of an element may be given.

Definition 2. By an element of the schedule is meant a symbolic notation in alphanumeric form of the fact that instructor \(A\) has at least one class with any of the \(N\) groups under consideration.

Definition (1) gives us the structure of the element, definition (2)—its content.

As a result, all the initial information on the teaching load in \(N\) groups can be represented in the form of an ordered set (columns, tables, etc.) of elements. An example of such a notation is

\[ \begin{aligned} A\ &\{12300000\}\\ B\ &\{10345000\}\\ C\ &\{00000678\}.\\ &\ldots\ldots\ldots \end{aligned} \]

If the instructor conducts the same class in a given group several times during the period of time for which the schedule is being compiled (usually this period covers two weeks), then the corresponding element is entered in the load column the corresponding number of times.

Definition 3. Two elements will be called compatible if they have different indices and different characteristics; otherwise the elements will be called incompatible.

The compatibility condition given in definition (3) is of exceptional importance for the subsequent analysis; therefore we shall provide more detailed explanations.

The essence of the process of compiling a time schedule of instructional classes is in fact reduced to identifying such classes as can take place simultaneously or, in other words, can be combined in time. It is obvious that such classes include classes of different instructors in different groups. Otherwise there is a so-called overlap in time, and the schedule loses its practical meaning. In the terms introduced above, the compilation of a schedule can be represented as a partition of the original set of elements into subsets of compatible elements. Such subsets will hereafter be called blocks, i.e., the following is the case:

Definition 4. A block is a set all of whose elements are compatible with one another.

Let us note that the introduced concept of compatibility differs from the concept of equivalence. Therefore, the problem of partitioning the original set of elements into blocks differs from partitioning a set into equivalence classes. Indeed, the following lemmas hold:

Lemma 1. An element \(A\) is incompatible with itself.

Lemma 2. If element \(A\) is compatible with element \(B\), and element \(B\) is compatible with element \(C\), then \(A\) and \(C\) are not necessarily compatible with one another.

These lemmas are easily proved by contradiction. In the concept of equivalence, however, an element of a set is equivalent to itself. This indicates that the compatibility condition has a more complex logical structure. From the analysis given above it follows that, in order to decide whether the element under consideration can be included in a given block or not, it is necessary to check whether the compatibility condition is satisfied with all elements of this block, i.e., with the block as a whole. When partitioning a set into equivalence classes, however, it is sufficient to check the equivalence condition of the element under consideration with any element of the given subset.

In a block, as a set of complex structure, one can construct two simple sets: the set of all indices of the elements of the given block and the set of all characteristics. These sets do not contain two identical elements, except for the element 0. When constructing the second set (the union of characteristics), we preserve the positional principle of arranging elements, discarding the corresponding zero elements and thereby keeping unchanged the total number of symbols (places) in passing from the characteristics to the given set. We shall use these constructions to simplify the logical structure of the algorithm for forming blocks from compatible timetable elements. To this end we introduce the concept of a hyperelement of a block.

Definition 5. A hyperelement of a block is an expression of the form

\[ \gamma ABC\ldots\{abc\ldots\}, \]

where \(\gamma\) is the number of the hyperelement (respectively, of the block),

\(ABC \ldots\) is the index of the hyperelement,

\(\{abc \ldots\}\) is the characteristic.

The characteristic of a hyperelement, like the characteristic of an element, will below be written in numerical form. In this case the index of the hyperelement and its characteristic are, respectively, the union of the indices and characteristics, according to the rule stated above, of all elements belonging to the block with number \(\gamma\).

Lemma 3. A hyperelement is not an element of a block.

By definition, a hyperelement is the union of the indices and characteristics of elements and, consequently, is incompatible with any element of the given block. This proves lemma (3).

Lemma 4. If a block consists of one element, then this element is a hyperelement of this block. The validity of lemma (4) follows from definition (5) of a hyperelement.

A hyperelement is a certain generalized characteristic of a block, having no substantive meaning and intended to simplify the logical structure of the algorithm. The purpose of the hyperelement in the algorithm for machine compilation of the timetable will be disclosed more fully below; for now we shall formulate the following theorem.

Theorem 1. If an element is compatible with a certain hyperelement, then it is compatible with the corresponding block as a whole.

The theorem is easily proved by contradiction using Lemma (3).

The results obtained may be formulated as follows: in order to decide whether a given element may be included in a block \(\gamma\), it is sufficient to check the compatibility condition of this element with the hyperelement of this block. Thus, the introduction of a hyperelement significantly reduces the number of operations performed by the machine, since there is no need to check the compatibility condition of the given element with each element of the block.

Complete and incomplete blocks. Filling the time grid of the schedule

Definition 6. A characteristic containing no zeros will be called complete with respect to the set of groups; otherwise, incomplete.

An example of a complete characteristic of an element (respectively, of a hyperelement) is a characteristic of the form \(\{1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\}\), and of an incomplete one, \(\{1\ 0\ 0\ 0\ 0\ 0\ 0\ 8\}\).

Definition 7. If a hyperelement has a complete characteristic, then the corresponding block will be called complete with respect to the set of groups under consideration; otherwise, incomplete.

The completeness of a block with respect to the set of groups under consideration means that not a single element from the initial set of classes can be included in this block any longer, and the process of forming the given block must be completed. The following theorem is valid.

Theorem 2. If the characteristic of some element of the initial set of classes is complete, then this element forms a complete block.

In other words, Theorem (2) determines the conditions under which a complete block consists of a single element. This sole element is at the same time the hyperelement of the block.

Suppose that a schedule is being compiled for \(N\) groups, and that the \(i\)-th group has \(a_i\) classes in two weeks (respectively, \(2a_i\) hours) \((i=1,2\ldots N)\). If we denote by

\[ a_{\min}=\min_{1\le i\le N} a_i, \tag{1} \]

\[ a_{\max}=\max_{1\le i\le N} a_i, \tag{2} \]

then the number of complete blocks is equal to

\[ n_{\text{п}}=a_{\min} \tag{3} \]

and, correspondingly, the number of incomplete blocks is

\[ n_{\text{н}}=a_{\max}-a_{\min}. \tag{4} \]

The total number of blocks is determined as

\[ n=n_{\text{п}}+n_{\text{н}}. \tag{5} \]

The quantity \(n\) determines the number of cells of the time grid required for conducting classes in these \(N\) groups. Here, in this case, a time cell is understood as the period of time necessary for conducting one class, i.e., 2 hours. Then the total working time over 2 weeks (daily 7 classes, from 9 a.m. to 11 p.m.)

in $2 \times 7 \times 12 = 168$ hours can be regarded as a time grid of 84 cells. In this sense, the concepts of a time grid and a cell will be used below.

In these terms, the further compilation of the schedule after the formation of the blocks consists in placing them in the cells of the time grid. In doing so, if $N$ groups are considered, then two blocks must not fall into one and the same cell. The condition that two blocks do not fall into one and the same cell is their incompatibility.

Definition 8. We shall call two blocks incompatible if their hyperelements are incompatible. Otherwise, they are compatible.

Lemma 5. For the $N$ groups under consideration, all blocks are incompatible with one another.

Indeed, if two compatible blocks were found, then they could be combined into one owing to the compatibility of their hyperelements. In particular, this proves the validity of (5), since $a_i$ determines how many times the $i$-th group enters into the elements of the initial set of classes.

As a result of distributing the blocks over the time grid, each block is assigned the number of the corresponding cell, and the timetable may be considered compiled. In practice, however, distributing blocks among cells is very complicated and laborious.

Consider two sets of groups $G$ and $P$. The set of teachers conducting classes in these groups is denoted by $I_G$ and $I_P$, respectively. The following is true.

Theorem 3. The blocks of the set $G$ are compatible with the blocks of the set $P$ only in the case when the sets $I_G$ and $I_P$ do not intersect, i.e.

\[ I_G \cap I_P = \varnothing . \]

The theorem is proved by contradiction, using the corresponding definitions 1.

As a result, the following interesting problem arises: can the entire set of groups be partitioned into a system of subsets in such a way that the corresponding subsets of teachers do not intersect? If such a problem is solved, then for each of the obtained subsets of groups the timetable can be compiled independently of the others, for their blocks will be compatible. This is very important from the standpoint that, when such independent sets of groups exist, the amount of information processed simultaneously will be relatively small. In the opposite case, one has to operate with a large volume of information, even if the timetable is compiled for a small number of groups. If, however, it is not possible to partition the groups into independent subsets, then the problem is posed of combining blocks for the sets $G$ and $P$. Since the sets of blocks $L_G$ and $L_P$ contain incompatible blocks, the problem reduces to finding a pair of compatible blocks: one from $L_G$, the other from $L_P$. To solve this problem, the same algorithm may be used as for compiling blocks.

Compact Timetables

It has already been noted above that the number of time cells necessary for placing the timetable is determined by the number of blocks compiled, since one block is placed in each cell. In turn, the number of blocks is determined by the maximum value of the load of the $i$-th group from the set of all groups. However, the analysis will be incomplete if

not take into account the set of instructors when forming blocks. Let, as before, \(a\) be the number of classes in the \(i\)-th group over two weeks, where \(i=1, 2 \ldots N\). Introduce \(b_j\) as the number of classes conducted by the \(j\)-th instructor in the \(N\) groups under consideration, also over two weeks, where \(j=1, 2 \ldots M\).

It is quite obvious that the following inequality holds:

\[ \sum_{j=1}^{M} b_j \leq \sum_{i=1}^{N} a_i . \tag{6} \]

Equality in (6) holds only for the set of practical classes, i.e., when each instructor simultaneously conducts a class with only one of the groups. In the general case, taking lectures into account, (6) gives a strict inequality. Since in each block an instructor and a group occur only once, the following is true:

Theorem 4. The number of blocks is determined as

\[ n=\max_{1<i<N} a_i, \tag{7} \]

if

\[ \max_{1<j<M} b_j \leq \max_{1<i<N} a_i, \tag{8} \]

and as

\[ n'=\max_{1<j<M} b_j, \tag{9} \]

in the opposite case, i.e., when

\[ \max_{1<j<M} b_j > \max_{1<i<N} a_i. \tag{10} \]

In the first case, i.e., when condition (8) is satisfied, we shall call the timetable compact; in the second, noncompact.

Compactness means that, when the time cells are filled with blocks, the corresponding timetable will not contain “windows” for groups. Incidentally, this is one of the basic requirements imposed on a class timetable.

With a noncompact timetable, since the number of blocks \(n'\) exceeds all without exception the numbers \(a_i\), “windows” are possible in the timetable when the time cells are filled with blocks. This fact is explained either by a shortage of instructors or by an uneven distribution of workload, since the largest workload falling on some instructor (or instructors) exceeds the largest teaching load of a group according to (10). Such unevenness in the distribution of workload must be eliminated at least so that

\[ \max_{1<j<M} b_j = \max_{1<i<N} a_i, \tag{11} \]

for otherwise an unjustified lengthening of the timetable by \(\Delta n=b_{\max}-a_{\max}\) cells, or \(2\Delta n\) hours, will occur. However, such a lengthening of the timetable is hardly possible in practical cases. As an example of the analysis, the initial set of classes was considered for

groups of the geological-prospecting faculty according to the schedule of the 1965/66 academic year.

Analysis shows that every 8 groups (the average number of groups in a year) are, on average, for 15 different subjects “served” by 46 or more instructors, i.e., there is weak localization of instructors in these groups. This makes it doubtful that the entire set of groups can be divided into independent subsets (in the sense of Theorem 3) in order to reduce the amount of information processed simultaneously. Therefore, in order to obtain the corresponding efficiency in the use of computing facilities for compiling the time grid of the schedule, it is necessary to compile it at once as a whole for the entire institute. Otherwise, the intermediate manual processing of information needed to coordinate the individual parts of the grid will call into question the advisability of using computers.

Algorithm for Compiling the Time Grid of the Schedule

We shall first give a general description of the algorithm. For simplicity, we shall assume that a schedule element is placed in one memory cell of the machine; the following cell structure is adopted:

\[ \theta a,\ \gamma a,\ \tau a, \]

where the part of the cell \(\tau a\) records the instructor’s index, \(\gamma a\) records the characteristic of the element, and \(\Theta a\) records the attributes “element occupied” or “element free,” i.e., whether or not it has entered one of the previously formed blocks. The initial set of classes is presented as a set of cells \(A[a+i]\) \((i=1, 2 \ldots N)\). We shall store the index of a hyperelement in cell \(r1\), and its characteristic in cell \(c1\). If an element is compatible with the hyperelement of the block being formed at the given moment, then its characteristic \(\gamma[a+i]\) is added to the contents of cell \(c1\), and its index is entered in the corresponding place of cell \(r1\). At the same time, the contents of cell \((a+i)\) are printed (output). As a result, the block is printed as a column of compatible elements. A block is considered formed if the characteristic of the hyperelement is full, i.e., \(c1 = 111\ldots\), or if among the remaining initial elements there are no more compatible ones.

The cells of the time grid are represented by an array of memory cells \(B[b+j]\). In cell \((b+j)\) are written the indices, by category \(\tau\), of the instructors who had already been placed in this time cell during previous compilation of the schedule. If the formed block can be placed in this time cell (respectively, memory cell \((b+j)\)), i.e., if the contents of cells \((b+j)\) and \(r1\) are compatible, then, following the printed elements of the block, the address of cell \((b+j)\), corresponding to the number of the time cell, is printed. The index part of the hyperelement \(r1\) is entered in cell \((b+j)\). Then the program is repeated for the remaining elements of the initial set of classes.

We shall give a formal description of the algorithm in terms of the algorithmic language ALGOL-60.

Algorithm

Start array \(A[a+i]\);

\[ \begin{aligned} L:\quad & i := 1 \quad \text{go to } Q;\\ Q:\quad & \text{if } \Theta[a+i] = 0 \text{ then execute;} \end{aligned} \]

Begin, if \(c1=0\) then

\[ c1:=\gamma[a+i]; \]

output \((a+i)\);

\[ \Theta[a+i]:=1; \]
\[ \Gamma1:=\tau[a+i]; \]
\[ k:=1; \]

Else go to \(M\);

End

Else execute

Begin \(i:=i+1\);

If \(i\le N\), then go to \(Q\), otherwise;

(stop)

End

\(M\): begin if \(\gamma[a+i]\ne c1\) then go to \(P\)

Else execute;

\[ i:=i+1; \]

If \(i\le N\) then \(Q\), otherwise \(L1\);

End

\(P\): index \(:=\tau[a+i]\times 2\uparrow(\tau\times j)\);

If index \(\ne r1\) for \(j=0\) step 1 until \(k\), then

\[ c1:=c1+\gamma[a+i]; \]
\[ r1:=r1+\tau[a+i]\times 2\uparrow(i\times k); \]

output \((a+i)\);

\[ \Theta[a+i]:=1; \]
\[ k:=k+1; \]

Go to \(P1\), otherwise \(L1\);

\(P1\): if \(c1=11\ldots\), then \(L1\), otherwise

\(i:=i+1\) go to \(Q\);

\(L1\): array \(B[b+j]\)

\[ j:=1; \]

\(Q1\): if \(\Theta[b+j]=0\) then \(G1\), otherwise

\(j:=j+1\) go to \(Q1\);

Comment: it is assumed that \(j\le M\) in practically all cases; the condition \(j>M\) would mean that the given block cannot be placed in any time cell. If it is necessary to check the filling of the time grid, then the following operator may be introduced into \(Q1\):

\[ \text{if } j\le M \text{ then } G1 \text{ otherwise;} \]

Then a stop follows, since an ambiguity arises in the placement of the block, which can be eliminated by increasing the number of cells in the time grid.

\(G1\): \(p:=0\)

\(G2\): begin lecturer \(:=\tau[r1]\times 2\uparrow(\tau\times p)\);

\[ \text{time}:=\tau[b+j]\times 2\uparrow(\tau\times q); \]

For \(q=0\) step 1 until \(m\), execute;

If lecturer \(\ne\) time then

\[ p:=p+1; \]

If $p \leq k$ then $G2$ otherwise $G3$ otherwise;

\[ j := j+1 \quad \text{go to } Q1; \]

End;

$G3$: $\Theta[b+j] := 1$;
output $(b+j)$
Commentary, i.e., the time for the given block is printed.

\[ c1 := 0; \]
\[ r1 := 0; \]
\[ k := 0; \]

Go to $L$
End

The algorithm described was implemented on the “Minsk-1” machine in the computing laboratory of TPI (see [1]).

REFERENCES

1. N. M. Bylino. Development of a program for constructing a time grid for scheduling on the “Minsk-1” computer. (This collection).