QUESTIONS OF STORING INFORMATION ABOUT A UNIVERSITY CLASS SCHEDULE

A. N. LAFEROV

(Presented by the scientific seminar of the computing laboratory)

The possibilities of human perception of information are limited (15–20 bits/sec), and the retention in memory of a large amount is possible only in general outline. In connection with this, the task of mechanizing and automating the process of accumulating, storing, and finding the necessary information is becoming ever more widespread.

General analysis of the problem of an automatic dispatcher service

The need to process a large amount of information arises in compiling a university schedule. In particular, such a need arises in the distribution and control of the use of the classroom stock. The classrooms of a university are used by various educational institutions, all kinds of courses, and public and party organizations of the city and district. The work of the operator of existing scheduling bureaus consists in finding the required number of free classrooms at specified hours and days and in their rational use. When the stock is heavily loaded, the rapid determination of “through” classrooms, i.e., those free at the same time over the course of two weeks (or conversely), is difficult, and all the more so when solving a combinatorial problem.

The amount of information processed by an operator in a scheduling bureau can be judged from the example given below. In time, the entire university schedule (by faculties) is compiled for two weeks (12 days), with a time-grid volume of \(12 \times 7 = 84\) elements, 7 pairs of class hours per day. Separately compiled is the classroom-stock schedule of classroom allocation, which represents the distribution of the time schedule by classrooms.

In order to record the compiled schedule, \(m = 12 \times 7 \times 300 = 25200\) cells on sheets of Whatman paper are required. With a university stock equal to 300 (for TPI), each cell, in turn, may be regarded as a binary-memory cell, i.e., occupied–free or, in terms of Boolean algebra, false–true, 0–1. The quantity of information about the distribution of the schedule by classrooms will thus amount to 50,400 states, or more than 15.6 bits. Hence it follows that the principal element of the dispatcher installation must be binary memory, in which all information about the schedule will be stored, and

the essence of the installation’s work comes down to the possibility of addressing this memory in order to extract and visually present the corresponding information (an answer to questions, etc.).

If \(m\) binary memory cells are regarded as the domain of definition of some function, then the indication of the memory states that is to be viewed by the operator can be expressed as a binary function of \(m\) variables \(F(x_1 x_2 \ldots x_m)\). In the general case the solution of this function is written [1]:

\[ F(x_1 x_2 \ldots x_m)=\varphi_1\varphi_2 \vee \ldots \vee \varphi_l, \tag{1} \]

where

\[ \varphi_\nu=y_{\nu,1}\wedge y_{\nu,2}\wedge \ldots \wedge y_{\nu,m}\quad(\nu=1,2,\ldots,l), \]

and \(\nu\) are the points of the domain of definition at which \(F=1\), with \(\mu=1,2,\ldots,m\).

\[ y_{\nu,\mu}= \begin{cases} x_\mu, & \text{or } x_\mu=1 \text{ at the point } Q_\nu,\\ \overline{x}_\mu, & \text{if } x_\mu=0 \text{ at the point } Q. \end{cases} \]

Fig. 1. On the question of indication of a university classroom schedule fund

If \(m\) is the total number of variables of the function \(F\), and \(F\) at each point of the set \(m\) repeats the value of the argument \(\mu\), then \(F\) can be represented as a function of the variable \(\mu\), taking the values \(1,2,\ldots,m\); therefore the total number of possible states-solutions of the correspondence function \(F'\) is written as \(2^m\). Naturally, singling out one solution from \(2^m\) by means of general indication (\(m=25\,200\) signal lamps) is difficult and is unlikely to be of any use. Most often the operator has to answer the following 2 questions:

1. Which classrooms are free at a given time?

2. How occupied is a particular classroom at one time or another?

In searching for answers to these questions, i.e., in determining the solution of the correspondence function, the operator has to sort through sheets with the schedule (“memory”). For this purpose the set of all values of the argument \(\mu\) can be divided into the following 3 sequences:

1. \(\mu_k\) — the sequence of university classrooms, \(\mu_k=1,2\ldots\). \(K=300\) — the university fund.

2. \(\mu_i\) — the sequence of days for which the schedule is compiled.

\[ \mu_i=1,2,\ldots i.\quad i=12 \]

(two weeks without days off).

1. \(\mu_j\) — the sequence of classes during one day.

\[ \mu_j=1,2,\ldots j.\quad j=7 \]

(pairs of class hours per day).

Then, defining the value of \(\mu\) as the intersection of the 3 sets \(\mu_k,\mu_i,\mu_j\), we shall have \(\mu=f(\mu_k,\mu_i,\mu_j)\), or, expanding according to (1), we obtain

\[ \mu=\mu_k\wedge\mu_i\wedge\mu_j. \tag{2} \]

In other words, \(\mu\) is determined (is equal to 1) only in the case when each of the arguments \(\mu\) takes a value equal to 1.

In problems of a combinatorial nature, where the number of arguments of each sequence may be greater than one, expression (2) will accordingly take on a different form.

In order to solve the question of the minimum number of signal lamps satisfying the stated conditions (the questions answered by the operator), i.e., lamps showing the solution \(F^1(\mu)\), let us represent the variables of this function in a Cartesian coordinate system (Fig. 1). Fixing successively the values \(\mu_k, \mu_i, \mu_j\), respectively, we obtain the type of combination:

\[ \begin{aligned} &1.\quad \mu_k,\ \mu_i \times \mu_j \quad (300 \cdot 12 \times 7 = 84).\\ &2.\quad \mu_i,\ \mu_j \times \mu_k \quad (12 \cdot 7 \times 300 = 2100).\\ &3.\quad \mu_j,\ \mu_k \times \mu_i \quad (7 \cdot 300 \times 12 = 3600). \end{aligned} \]

Thus, in order to represent 25,200 memory cells by means of external indication, in the first combination 384 lamps are needed, in the second—2112, and in the third—3607. The first variant is the most acceptable, since in this case it is possible to answer both questions posed at once. The answer to the first question can be obtained on the room-stock display (room indication, variable \(\mu_k\)), consisting of 300 indicator lamps, while one of 84 time states is specified (variables \(\mu_i, \mu_j\)); the answer to the second question is obtained on the time display (variables \(\mu_i, \mu_j\)), consisting of 84 signal lamps, for a specified room number (\(\mu_k\)).

Such an interpretation of the solutions \(F^1\) makes it possible to find not only the values of \(F^1(\mu)\) at the point \(\theta(\mu_k\mu_i\mu_j)\), but also to represent one of the solutions (not values) \(F(\mu_k)\) for \(\mu_i\mu_j=\mathrm{const}\), where \(\mu_k\) runs through all values from 1 to 300, and \(F(\mu_i\mu_j)\) can take the values 0 or 1; or the solution \(F(\mu_i\mu_j)\) for \(\mu_k=\mathrm{const}\), where, respectively, \(\mu_i, \mu_j\) run through \(1—12, 1—7\). And \(F^1(\mu_i\mu_j)\) can take the values 0 or 1. By the solution of the function \(F^1(\mu_k)\) one should understand the indication of all rooms simultaneously at a specified time \((\mu_i, \mu_j)\); analogously, the solution of the function \(F'(\mu_i\mu_j)\) is the indication of the state of one room for all time over the course of two weeks.

Memory Device for the Room Stock

The construction of a memory unit for the state of the room stock may be based on a diode-switch matrix (Fig. 2). In the matrix, by means of switches \(K_{ij}\), the 84 states of one room are stored. Along the rows of the matrix are arranged buses imitating the days for which the schedule is drawn up. For example, the days from Monday to Saturday of the even week have indices 1—6, and indices 7—12, respectively, are for the odd week. Along the columns are arranged buses imitating class times—7 pairs of hours per day. The connection of the corresponding row and column buses constitutes the \(ij\)-th memory cell. The storage of a state is effected by closing or opening the switches \(K_{ij}\).

Indication of the \(ij\)-th state of the room matrix is performed with the aid of one signal lamp SL, located on the indicator display; therefore the number of such matrices must be equal to the number of rooms in the university, but in order to judge the state of a given room over the entire time, it is necessary successively to poll-

to enter all 84 states of the given classroom and output them to the display, first storing them in some storage device.

A further increase in the amount of memory, i.e., entering into the memory cell not only the value of the state (occupied–free), but also the instructor code and the group code, will make it possible to connect the device directly with the computer that compiles the schedule; moreover, it becomes possible to create an automatic memory device for the university schedule (based on computer blocks), which will be able to output individual schedules in the form of punched cards by faculties, groups, instructors, etc. In addition, the device will make it possible to enter current changes in the schedule: exchanging classrooms, deletion—the end of classes, etc.

Fig. 2. Memory matrix for storing the states (occupied–free) of one classroom

Designing such a device may be expedient when the schedule is compiled entirely on a computer. In this case the computer must print out not only the contents of the time cell, but also its address (the classroom number and its time position). Thus, the input information for the machine can be represented in the following form:

In order to encode the address (26,800 memory cells for a stock of 350 classrooms), 15 address digits are needed, since \(2^{15}\) is greater than 26,800. Similarly, for 440 groups, taking into account that one instructor may lecture to several groups—9 digits, and 11 digits for 1,500 instructors, provided that in one group (laboratories,

practical classes) there may be 2 instructors. Therefore, taking into account the service digits, their total number in a cell must be no less than 40. In other words, the cell must contain 40 bits of information, and since there are 26,800 such cells, information on the order of

\[ 40-\log_2 26\,800 \approx 55\ \text{bits}. \]

The described coding method requires 26,800 forty-digit words. To reduce the number of digits in a word, another coding method may be proposed. For example, representing the same information in several cells, but this will not reduce its total amount in memory. Hence it is clear that, with such a volume of information, one cannot do without magnetic tape.

A block diagram of an installation with memory on magnetic tape may be presented as in Fig. 3.

Fig. 3. On the issue of storing and working with a complete university timetable

The compiled timetable on punched tape is fed to the input device, and then into memory. The timetable is entered both automatically and selectively by addresses. In nonautomatic recording, the number of the classroom and its time cell are set on the address register. Then the contents of the cell are set on the instructor-code and group-code register and are entered at this address. Indication on display A is carried out by means of the classroom register, and on display B by the time-state register. The output device will allow individual timetables to be printed and even displays A and B to be duplicated, if the number of queries about the state of the stock is within the “norm,” since the answer to each query is printed on a punched card. Therefore, instead of two displays of the state of the stock, one is introduced for viewing a single cell (dotted line).

Analysis shows that an installation of this kind will constitute a specialized device whose use is rational only with complete scheduling on a digital computer, and therefore its design can be begun only after the problem of compiling a university timetable has been solved. The proposed device, when the timetable is compiled by machine, will significantly reduce the staff of the timetable bureau.

The designed installation can be used both under the existing state of affairs in the preparation of schedules and for fully machine-based schedule preparation, since creating an analogous installation (with binary memory) using contactless elements will not simplify the design.

As for the immediate tasks of solving certain problems involved in working with a university’s room stock, it is quite advisable to take advantage of the possibility of creating an automatic dispatching installation with two-state memory in a cell: occupied–free, with the manual entry of a given state into memory.

A similar design for a relay-type installation has been created in the computing laboratory of TPI. The design is based on the considerations described above.

The block diagram of the installation is shown in Fig. 4, where SF is the room-stock selector, which selects the required room, whose state is then expanded by the time selector (VS). VS is also necessary in order to set the time value for all rooms simultaneously. SU is the device control system.

Fig. 4. Block diagram of an automatic dispatching installation for distributing the room stock

The introduction of OZU (random-access memory) is dictated by the structure of the memory and switching, i.e., by the fact that the contents of a cell (room) are fed to display board B distributed over time.

The OZU has a number of memory cells equal to the number of states of one room, i.e., 84.

The main tasks solved by the device are as follows:

1. Finding all free rooms at a specified hour simultaneously from the entire stock.

2. Finding free rooms for any specified combination of class times and days—again over the entire stock. For example, in response to the question which rooms are free on Monday from 3 to 5, Wednesday from 9 to 11 for an even week, and on Monday from 11 to 1, Saturday from 9 to 11 for an odd week. The corresponding “times” are entered on the register, and the answer is read on display board A, where the lamps of the rooms free at that time light up. The problem is solved practically instantaneously.

3. Determining the state (load) of any of the 350 rooms over the course of two weeks for 7 pairs of class hours per day.

4. By whom a particular room is occupied and for how long (flags on plug connectors—the memory elements—of external display boards).

It should be noted that the installation does not solve the problem of drawing up a timetable, but facilitates the process of drawing one up and automates the subsequent work with it; it increases the efficiency of the dispatcher’s work, makes it possible to make maximum use of the university’s room stock, and raises the culture of labor. In addition, it makes it possible to monitor rooms that are temporarily occupied.

An automatic dispatching installation for allocating the classroom stock can be recommended for universities that have a large number of classrooms and are therefore interested in making maximum use of classrooms.

Below are some calculated characteristics of the installation for a stock of 350 classrooms.

1. Determination of vacant classrooms at a given time (within the limits of 2 weeks and 7 class periods per day).

2. Determination of the workload of a single classroom (in the same interval).

3. Polling the states of all classrooms in the university’s stock (the state of each classroom is automatically displayed on display panel B in no more than 20 minutes).

4. The time for solving the combinatorial problem is on the order of 5 sec. (i.e., finding the answer to the question of which classrooms are free on such-and-such days of an even week, at such-and-such hours, and analogously for an odd week, with the classrooms satisfying this condition immediately being illuminated on display panel B).

5. Power consumption no more than 600 W.

6. Approximate development cost: 15–20 thousand.

REFERENCES

1. N. A. Krinitskii, G. A. Mironov, G. D. Frolov. Programming. Fizmat, Moscow, 1963.

2. Proceedings of the Scientific-Technical Conference, 1964–1965. Section of Automation, subsection of automation and telemechanics. MEI, Moscow, 1965.