SIMULATION ALGORITHM FOR ONE CLASS OF QUEUEING SYSTEMS

L. V. PERFIL'EV

(Presented by the Scientific and Technical Seminar of the Research Institute of Nuclear Electric Power Plants at TPI)

The article is devoted to questions of qualitative and quantitative investigation of elevator-control systems.

Such systems may be classified as single-phase, multi-line, unordered queueing systems with waiting, with a limited number of service devices, a random input stream, and arbitrary service time.

In this case the input stream (the stream of calls from floor landings) is considered as Poisson, under the condition that each request is characterized not only by the time of its occurrence, but also by its route of movement. The route of movement of a request is characterized by a certain initial point (floor number) at which the request enters, and by an endpoint at which the request leaves the system. The initial and final points belong to a finite set of natural numbers. The distribution law of route lengths, as well as the distribution of routes in space, may in the general case be arbitrary.

The specific nature of the service discipline—the method of organizing group operation of elevators—allows such systems to be classified as unordered.

Requests waiting in the queue may be served in groups, not exceeding some specified number limited by the capacity of the service device.

The moments of the beginning and end of service of requests by one and the same device, in the general case, may not coincide. The service of some request by a device may be interrupted for a time depending on the number of requests leaving the device and entering it.

The device (elevator) that is to begin serving a request or a group of requests, as well as the requests themselves, are determined in each particular situation on the basis of the technological requirements of the elevator-control system (the method of organizing elevator operation).

The service time depends on the length of the route of movement and on the number of stops of the service device and is thus connected with the characteristics of the service discipline and the incoming stream of requests.

The distribution law of the service time in elevator-control systems is unknown. Great difficulties arise when attempting to make any assumptions and suppositions concerning the form of this law.

The Monte Carlo method makes it possible to simulate the process of operation of elevators in a group on the basis of a formalized representation of the technological requirements of the system, formulated during design and opera-

of such systems. In this case, the distribution law of the service time and its parameters, as well as the system’s service-quality indicators, can be determined as a result of computing the simulation algorithm.

The structure of the simulation algorithm depends on the assumptions made concerning the flow of demands, the queue discipline for demands, and the procedure for selecting devices for service.

As indicated above, the passenger flow in elevator-control systems is characterized not only by the arrival instant \(t_j\) \((j = 1, 2, \ldots)\), but also by the values of the parameters \(a_j^{(k)}(t)\), where

\(a_j^{(1)}(t)\) — the floor on which the \(j\)-th call (demand) appeared;

\(a_j^{(2)}(t)\) — the floor on which service of the \(j\)-th call will end;

\(a_j^{(3)}(t)\) — the direction of the \(j\)-th call.

The parameters \(a_j^{(k)}(t)\) are realizations of random functions \(A_j^{(k)}(t)\) with specified distribution laws.

The servicing devices at each discrete instant of time are characterized by the values of the parameters \(\beta_i^{(r)}(t)\) \((i = 1, 2, \ldots n)\):

\(\beta_i^{(1)}(t)\) — the floor on which the \(i\)-th elevator is located;

\(\beta_i^{(2)}(t)\) — the direction of motion of the \(i\)-th elevator;

\(\beta_i^{(3)}(t)\) — the degree of readiness of the \(i\)-th elevator (the elevator is standing with doors open or closed; accelerating or braking, etc.);

\(\beta_i^{(4)}(t)\) — the number of demands in the \(i\)-th elevator.

The values of the parameters \(\beta_i^{(r)}(t)\) are determined as functions of the parameters \(a_j^{(k)}(t)\) in accordance with the technological requirements of the system.

The technological requirements of the system determine the structure of the functional \(D\), as a result of whose solution a demand is selected from the queue and a device is selected for service. In this case, the selection of demands and devices is performed at discrete instants of time, depending on the particular values of the parameters \(a_j^{(k)}(t)\) and \(\beta_i^{(r)}(t)\). The set of combinations of values of the parameters \(a_j^{(k)}(t)\) and \(\beta_i^{(r)}(t)\) is relatively large, and in practice it does not appear possible to analyze all possible states characterized by the values of these parameters. Therefore, classes (subsets) of system states are distinguished, for which the technological requirements are formulated and the functional \(D\) is constructed.

The values of the parameters \(a_j^{(k)}(t)\), \(\beta_i^{(r)}(t)\), as well as the value of the output signal of the functional \(D\), are computed at discrete instants of time corresponding to special states of the system. The set of instants of time of special states of the system \(t_\pi\) consists of the elements \(t_j\), \(t_h^i\), \(t_x^i\), \(t_{ls}\),

where

\(t_j\) — the instant of arrival of a demand;

\(t_h^i\) — the instant at which service of a demand or group of demands by the \(i\)-th device begins;

\(t_x^i\) — the instant at which service of a demand or group of demands by the \(i\)-th device ends.

At the instants of time \(t_{ls}(s = 1, 2, \ldots)\), such changes in the system are recorded without which it is difficult or impossible to construct the simulation algorithm.

The physical meaning of these instants and their number are determined by the particular system for controlling a group of elevators. In particular, this may be the instant at which an elevator reaches the extreme floors, the instant at which elevators reach the boundaries of zones if the building is divided into service zones, etc. The practice of simulating elevator-control systems shows that the presence of the time instants \(t_{ls}\) greatly facilitates the algorithmization of such systems.

The functioning of the queueing system proceeds as follows.

In the system, which is in one of the possible states, the current (or, initially, specified) values of the parameters \(a_j^{(k)}(t)\) and \(\beta_i^{(r)}(t)\) are recorded.

With the aid of the functional \(D\), as a function of \(a_j^{(k)}(t)\) and \(\beta_i^{(r)}(t)\), it is determined whether there are groups of requests that may be candidates for service. A group of requests includes requests with equal parameters \(a_j^{(1)}(t)\) and \(a_j^{(3)}(t)\). The maximum possible number of such groups is equal to the number of service devices.

If such candidate groups exist, they are stored.

With the aid of the functional \(D\), as a function of \(a_j^{(k)}(t)\) and \(\beta_i^{(r)}(t)\), the devices for servicing the candidate groups are determined.

Then \(t_h^i\) is determined—the moment at which service of the candidate groups begins—as a function of \(a_j^{(1)}(t)\), \(\beta_i^{(1)}(t)\), and \(\beta_i^{(3)}(t)\); the value \(t_j\) is simulated—the moment of arrival of a request—and the time moments \(t_{b3}\) are also determined. If a request or a group of requests is being served by some device, then \(t_x^i\) is determined—the moment at which service of the requests ends—as a function of \(a_j^{(2)}(t)\), \(\beta_i^{(1)}(t)\), and \(\beta_i^{(3)}(t)\).

Thus,

\[ t_\pi = f\,[a_j^{(k)}(t), \beta_i^{(r)}(t)]. \]

The computed values \(t_j,\ t_h^i,\ t_x^i,\ t_{ls}\) are compared, and the smallest of them is determined.

If \(t_j = \min\), then \(t_{j+1}\) is simulated—the moment of arrival of the next request—and the values of the parameters \(a_{j+1}^{k}(t)\) of this request are simulated; also, the current values of the parameters \(\beta_i^{(r)}(t)\) are computed in accordance with the result of solving the functional \(D\).

In the event that any other element of the set \(t_\pi \ne t_j\) is minimal, only the current values of the parameters \(\beta_i^{(r)}(t)\) are computed. Here the equality \(t_h^i = \min\) means that the \(i\)-th device has begun servicing a request or a group of requests; the equality \(t_x^i = \min\) means that the \(i\)-th device has completed servicing one of the requests or a group of requests.

The candidate groups are determined again, the values of the elements of the set \(t_\pi\) are computed, and so on.

The number of cycles is determined by the accuracy with which it is necessary to compute the values of the service-quality indicators (the mathematical expectation of the waiting time before the start of execution of requests, and the coefficients of idle running and downtime of the devices).

In the memory cells of the electronic digital computer, in each cycle, information is recorded that is necessary for computing the values of the service-quality indicators. In particular, such information is the moment of arrival and the moment of beginning of service of a request; the travel time of an empty device, etc.

Below is the operational scheme of the algorithm described:

\[ {}^{12}\Phi_1 A_2 A_3^{3,14,15,16} A_4 A_5 P_6 {}^{\uparrow 7}_{\downarrow 9} A_7 A_8^{6,8} P_9{}^{\uparrow 10}_{\downarrow 11} A_{10}^{9,10} A_{11} P_{12}{}^{\uparrow 1}_{\downarrow 13} P_{13}{}^{\uparrow 15}_{\downarrow 14} P_{14}{}^{\uparrow 16}_{\downarrow 4} \]

\[ {}^{13}A_{15}^{4}\quad {}^{14}A_{16}^{4} \]

\(\Phi_1\) — call to the random-number sensor;

\(A_2\) — computes the time moments \(t_j\);

\(A_3\) — computes the values of the parameters \(a_j^{(k)}(t)\);

\(A_4\) — computes the values of the parameters \(\beta_i^{(r)}(t)\);

\(A_5\) — enters into the memory cells the information necessary for computing the values of the service-quality indicators;

\(P_6\) — with the aid of the functional \(D\), as a function of \(a_j^{(k)}(t)\) and \(\beta_i^{(r)}(t)\), checks whether there exist groups of requests that may be candidates for service;

$A_7$ — with the aid of the functional $D$, as a function of $a_j^{(k)}(t)$ and $\beta_i^{(r)}(t)$, determines the server for servicing the claiming groups;

$A_8$ — computes the time instants $t_h^i$;

$P_9$ — checks for the presence of a server servicing a claim or a group of claims;

$A_{10}$ — computes the time instants $t_x^i$;

$A_{11}$ — computes the time instants $t_{ls}$;

$P_{12}$ — checks the fulfillment of the inequalities

\[ t_j < t_h^i;\quad t_j < t_x^i;\quad t_j < t_{ls}; \]

$P_{13}$ — checks the fulfillment of the inequalities

\[ t_h^i < t_j;\quad t_h^i < t_x^i;\quad t_h^i < t_{ls}; \]

$P_{14}$ — checks the fulfillment of the inequalities

\[ t_x^i < t_j;\quad t_x^i < t_h^i;\quad t_x^i < t_{ls}; \]

$A_{15}$ — erases the values $a_j^{(1)}(t)$ and $a_j^{(3)}(t)$ of the claim whose servicing has begun;

$A_{16}$ — erases $a_j^{(2)}(t)$ of the claim whose servicing has ended.

Fig. 1.

The principal difficulties in modeling elevator-control systems arise in the formalization of the technological requirements of the system. It is convenient (and sometimes necessary) to divide the structure of the functional $D$ into substructures. Thus, for example, the process of determining which claim is to be serviced by server $i$ may be divided into two stages:

1) determining the direction of motion of the server, depending on the specific technological situation;

2) determining which claims can be serviced by this server and which claim, in the given situation, can be serviced first.

In accordance with this, the functional $D$ is constructed from two substructures performing the functions of the stages described.

In addition, a feature of the functional $D$ is its relatively complex logical structure.

In accordance with the algorithm described, operator schemes and programs have been developed for computation on the M-20 digital computer of elevator-control systems, whose operation is organized in various ways.

In Fig. 1 are shown the dependences of $m$—the mathematical expectation of the waiting time until the beginning of the execution of a claim—as a function of $\lambda$—the inten-

...of the passenger-flow intensity for known elevator-control systems with the zonal method of organizing group operation of elevators with rigid assignment of elevators to zones, and with the zonal method using the principle of a sliding zone.

Fig. 2.

Figure 2 shows the dependences of \(k_x\)—the coefficients of idle runs—and \(k_n\)—the coefficients of equipment downtime—as functions of \(\lambda\).

Figure 3 gives, as an example, the polygon of relative frequencies of the waiting time until the start of fulfilling requests at \(\lambda = 0.125\).

Fig. 3.

In all figures, the curves for the zonal method with rigid assignment of elevators to zones are denoted by the number 1, and the curves for the zonal method using the principle of a sliding zone by the number 2.

All the results of the calculations of the simulation algorithms were obtained under the assumptions:

1) the occurrence of requests on any floor of the building is equally probable,
2) the length of a request route may be equal to any number of floors with equal probability.

References

1. N. P. Buslenko. Simulation of Complex Systems. “Nauka,” Moscow, 1968.

2. N. P. Buslenko, D. I. Golenko, I. M. Sobol, V. G. Sragovich, Yu. A. Shreider. The Method of Statistical Trials. Fizmatgiz, 1962.

3. V. Ya. Rozenberg, A. I. Prokhorov. What Is Queueing Theory? “Sovetskoe radio,” Moscow, 1965.

4. Development of a system for organizing the group operation of elevators in high-rise buildings. Report on a research topic. Stages I, II, III. Tomsk Polytechnic Institute, 1967.

5. Investigation of methods of construction and methods for designing systems for organizing the group operation of elevators. Report on a research topic. Tomsk Polytechnic Institute, 1968.