DEVELOPMENT OF A PROGRAM FOR COMPILING A SCHEDULE TIME GRID ON THE “MINSK-1” COMPUTER

N. M. Bylino

(Presented by the scientific seminar of the computing laboratory)

This paper gives a description of a method for coding the initial information about the schedule of classes and of a program for compiling a schedule time grid on the “Minsk-1” machine according to the algorithm described in article [1].

Let us write out the initial set of schedule elements \(\{L_i\}\). Each element must contain the instructor’s code and the code of the group in which the class is held. In addition, in each element it is necessary to mark whether the instructor conducts the class alone, for example practical classes, or together with another, as in laboratory classes and foreign-language classes. If the element denotes a lecture, then the instructor’s code and all the groups that attend this lecture are indicated.

For compact filling of the memory of the “Minsk-1” machine, it is best to allocate one cell for each element. A cell consists of 31 bits. There are about 1200 instructors at the institute. Since

\[ 2^{10}=1024<1200<2048=2^{11}, \]

11 binary bits are needed for the instructor’s code. Of the remaining 20 bits, one is used to mark whether one instructor or two are engaged with the given group; one bit is a service bit, used in the program; 18 bits are allocated for groups. In the cell, for convenience of coding and perforation, the bits are distributed as follows: the zeroth (sign) bit is used to mark whether one instructor conducts the class (then the sign will be plus) or two (then the first element is coded as positive, and the second necessarily as negative, but with the same group); bits 1–18 are allocated for groups; the 19th bit is a service bit, and bits 20–30 are for the instructor’s code. If the class of one group is being coded, then in bits 1–18 of the element there will be a single one in the bit corresponding to the group taken. If a stream lecture is being coded, then in bits 1–18 there will be as many ones as there are groups included in the given stream. If the class occurs several times in the period under consideration, then it is written with the same expression the same number of times. This method of coding makes it possible to record in the machine memory the teaching load for 18 groups.

The load is recorded in the same order as is done in the scheduling office: first all lectures for all 18 groups are coded, then all

laboratory classes and in a foreign language for all groups, and then all practical classes. When coding and entering onto the machine form, the instructor’s code is immediately written in the octal number system (four octal digits in column \(A_2\)), while it is easiest to write the groups in the binary number system, and then, after breaking 18 bits into digits, to write six octal digits in the columns COP and \(A_1\). The resulting information in coded form has the following appearance:

In cell \(k+1\) a lecture by the instructor with code 0001 is encoded for groups 1, 2, 12, 13, 14, 15, 16, 17, 18 of the 18 groups under consideration. In cells \(k+3\)—\(k+6\) two laboratory classes for the 1st group are recorded. The problem reduces to forming, from the given set \(\{\alpha_i\}\), subsets called blocks, in which the group codes and instructor codes would be compatible. This means that the group codes must not overlap and the codes of all instructors must be different. A block into which all 18 groups have entered is called complete. Otherwise the block is called incomplete.

After the set has been divided into blocks, all the blocks must be placed on the time grid. The time grid consists of 36 nodes. The timetable was compiled for full-time groups; they most often have 3 pairs of hours per day, and for two weeks. Hence

\[ 3 \times 6 \times 2 = 36. \]

If there are more than 18 groups (there are 441 of them at the institute), the problem is solved in parts. The solution of the second part of the problem, i.e., distribution over the time grid, becomes more complicated, because in doing so it is necessary to take into account the instructors’ occupancy in the preceding groups.

In the program, the questions of partitioning the set into blocks and distributing them over the time grid are solved simultaneously, i.e., a block is formed and is immediately entered into one of the “time cells”; then a new block is formed and again entered into another “time cell,” and so on (Fig. 1).

Because of the machine’s limited memory, the classes for 18 groups and the “time cells,” into which the codes of all instructors in the entire institute occupied at the given time are entered, are written to magnetic tape in different zones. In solving the problem, as needed, either classes (when forming a block) or “time cells” (when placing blocks on the time grid) are read from the magnetic tape into the same place in the RAM.

The program has a working cell in which, in bits 1–18, the groups of elements entering into a block are accumulated, and working cells where the codes of the instructors conducting these classes are stored. In each element there is a service bit, the 19th, in which it is indicated whether the element has entered one of the blocks or not.

To form a block, the elements not entering into other blocks are examined, starting with the first. In the element found, the groups-

occupied, and the instructor code are compared with the contents of the corresponding working cells. If the groups or instructor codes prove to be compatible, the element remains free. We proceed to a new element. If, however, the groups and instructor codes are incompatible, then the group and instructor code of this element are joined to the groups and instructor codes of the working cells, and it is noted that the element has entered the block, i.e., a “1” is written in its 19th digit, and the element itself is printed. The process moves on to the next free element. This continues until all ones stand in digits 1–18 of the corresponding working cell, i.e., until the block is complete.

Figure 1. Brief block diagram of the program

Flowchart labels:

• Reading elements from tape
• Finding a free element
• Is the element compatible with the block being formed?
• yes
• no
• Element ∪ block → block
• Print element
• Is the block complete?
• no
• yes
• Write elements to tape
• Reading time cells from tape
• Is the time cell suitable for the block?
• no
• yes
• Block ∪ time cell → cell
• Write time cells to tape
• Print class time
• Interval

After this, the entire set of classes is written to magnetic tape, and in its place in the magnetic-core storage those “time cells” are read from magnetic tape in whose corresponding hours the given groups are not occupied. The instructor codes of the “time cell” read are compared with all instructor codes of the newly formed block until a “time cell” is found into which the given instructor codes can be written. The “time cells” are arranged in the following order: first all cells from 9 o’clock on all days of the two weeks, then all cells from 11 o’clock on all days of the two weeks, and so on. The entire “time cell,” with the newly added instructor codes, is written to magnetic tape, and its attribute denoting the day and hour of the class is printed. The whole process then begins to repeat from the start.

It turns out that all classes of the block are sent to print; at the end of all the classes, the “time cell” into which the block entered is printed. Blocks are separated from one another by intervals. The results printed by the machine have the following form:

6001770001
1774000007

0002000024
—0002000025
0000000011
6001770001
1776000000
0000000021
6001770007
1776000001
0000000012
6000000003
1776000001
0001770013
0000000022

If a block is incomplete, this means that the missing groups have, for this time, either a window, or else classes for that day have ended. It may happen that none of the “time cells” fits the block being formed: either the groups or the instructors are busy. Then a “0” is printed at the end of the block. To avoid this, the time grid can be expanded, making it consist not of 36 but of 48 nodes, i.e., 4 pairs of classes per day. The entire schedule should then be compiled anew for 48 “time cells.”

It is clear that this problem requires a large amount of memory. All the information being processed is written to magnetic tape (\(650_{10}\) 31-bit cells for the classes of one faculty). The codes of instructors who are busy in the teaching process are also written to magnetic tape (\(15360_{10}\) 31-bit cells for 48 “time cells”). The program itself occupies \(390_{10}\) cells. Because of the small size of the RAM of the “Minsk-1” machine, the tape has to be accessed very often (at least 4 times for one block). The speed of tape motion is low compared with the operating speed of the machine. Therefore the simplest case was taken: the schedule was compiled for one faculty, i.e., it was assumed that all instructors were free and were not occupied at other faculties. Under these conditions, compiling the schedule for all five years on the machine took about three hours.

For the next faculty the solution becomes more complicated, because some of the instructors will be busy at the previous faculty, and the time required to select a suitable “time cell” for each new block increases. Consequently, the time required to solve the entire problem also increases. If the institute has 10 faculties, then 35–40 hours of continuous machine operation will be required in order to compile a class schedule only for groups of full-time study.

It is therefore clear that solving this problem on the “Minsk-1” machine is not advantageous. It is better to solve the problem on a machine with a larger RAM, so as to access the magnetic tape as rarely as possible.

REFERENCES

1. I. E. Naats. Questions of the algorithmization of compiling a time grid for a schedule of instructional classes. (The present collection).