Mathematical models of queuing systems for solving economic problems. Before starting work, make sure that there is no visible damage to the equipment and wires

Picture 0 - 2 Event streams (a) and the simplest stream (b)

10.5.2.1. stationarity

The flow is called stationary , if the probability of hitting one or another number of events in an elementary period of time length τ (

Figure 0-2 , a) depends only on the length of the section and does not depend on where exactly on the axis t this area is located.

The stationarity of the flow means its uniformity in time; the probabilistic characteristics of such a flow do not change with time. In particular, the so-called intensity (or "density") of the flow of events, the average number of events per unit time for a stationary flow, must remain constant. This, of course, does not mean that the actual number of events appearing per unit of time is constant; the flow can have local concentrations and rarefactions. It is important that for a stationary flow these concentrations and rarefaction are not of a regular nature, and the average number of events falling on a single time interval remains constant for the entire period under consideration.

In practice, there are often flows of events that (at least for a limited period of time) can be considered as stationary. For example, the flow of calls arriving at the telephone exchange, say, in the interval from 12 to 13 hours can be considered stationary. The same flow will no longer be stationary for a whole day (at night, the intensity of the flow of calls is much less than during the day). Note that the same is the case with most of the physical processes that we call "stationary" in fact, they are stationary only for a limited period of time, and the extension of this period to infinity is just a convenient trick used for simplification.

10.5.2.2. No aftereffect

The flow of events is called a flow without aftereffect , if for any non-overlapping time intervals the number of events falling on one of them does not depend on how many events fell on the other (or others, if more than two sections are considered).

In such streams, the events that form the stream appear at successive points in time independently of each other. For example, the flow of passengers entering the metro station can be considered a flow without aftereffect, because the reasons that caused the arrival of an individual passenger at this particular moment, and not at another, as a rule, are not related to similar reasons for other passengers. If such a dependence appears, the condition for the absence of an aftereffect is violated.

Consider, for example, the flow of freight trains going along a railway line. If, for safety reasons, they cannot follow one another more often than at intervals of time t0 , then there is a dependency between the events in the stream, and the condition of no aftereffect is violated. However, if the interval t0 is small compared to the average interval between trains, then such a violation is insignificant.

Picture 0 - 3 Poisson distribution

Consider on the axis t the simplest flow of events with intensity λ. (Figure 0-2 b) . We will be interested in a random time interval T between adjacent events in this stream; find its distribution law. First, let's find the distribution function:

F(t) = P(T ( 0-2)

i.e. the probability that the value of T will have a value less thant. Set aside from the beginning of the interval T (points t0) segment t and find the probability that the interval T will be less t . To do this, it is necessary that for a section of length t , adjacent to a point t0 , at least one thread event hit. Let's calculate the probability of this F(t) through the probability of the opposite event (per segment t no stream events will hit):

F (t) \u003d 1 - P 0

Probability P 0 we find by formula (1), assumingm = 0:

whence the distribution function of the value T will be:

(0-3)

To find the distribution density f(t) random variable T, it is necessary to differentiate the expression (0‑1) byt:

0-4)

The distribution law with density (0-4) is called exponential (or exponential ). The value λ is called the parameter exemplary law.

Figure 0 - 4 Exponential Distribution

Find numerical characteristics of a random variable T- mathematical expectation (average value) M[t]=mt , and dispersion D t . We have

( 0-5)

(integrating by parts).

The dispersion of the value of T is:

(0-6)

Extracting the square root of the variance, we find the standard deviation of the random variable T.

So, for an exponential distribution, the mathematical expectation and standard deviation are equal to each other and are inverse to the parameter λ, where λ. flow intensity.

Thus, the appearance m events in a given time interval corresponds to the Poisson distribution, and the probability that the time intervals between events will be less than some predetermined number corresponds to the exponential distribution. All these are just different descriptions of the same stochastic process.

QS Example-1 .

As an example, consider a real-time banking system serving a large number of customers. During peak hours, requests from bank tellers who work with clients form a Poisson flow and arrive on average two per 1 s (λ = 2). The flow consists of requests arriving at a rate of 2 requests per second.

Calculate the probability P ( m ) occurrences m messages in 1 s. Since λ = 2, from the previous formula we have

Substituting m = 0, 1, 2, 3, we obtain the following values ​​(up to fourdecimal places):

Figure 0 - 5 Simplest flow example

More than 9 messages in 1 s are also possible, but the probability of this is very small (about 0.000046).

The resulting distribution can be represented as a histogram (shown in the figure).

Example of CMO-2.

A device (server) that processes three messages in 1s.

Let there be equipment that can process three messages in 1 s (µ=3). On average, two messages are received in 1s, and in accordance c Poisson distribution. What proportion of these messages will be processed immediately upon receipt?

The probability that the arrival rate will be less than or equal to 3 s is given by

If the system can process a maximum of 3 messages in 1 s, then the probability that it will not be overloaded is

In other words, 85.71% of messages will be served immediately and 14.29% with some delay. As you can see, a delay in processing one message for a time greater than the processing time of 3 messages will rarely occur. The processing time of 1 message is on average 1/3 s. Therefore, a delay of more than 1s will be rare, which is quite acceptable for most systems.

CMO example 3

· If a bank teller is busy during 80% of his working time, and he spends the rest of the time waiting for customers, then he can be considered as a device with a utilization factor of 0.8.

· If the communication channel is used to transmit 8-bit symbols at a rate of 2400 bps, i.e. a maximum of 2400/8 symbols are transmitted in 1 s, and we are building a system in which the total amount of data is 12000 symbols sent from various devices through channel per busy minute (including synchronization, end-of-message characters, control characters, etc.), then the utilization rate of the equipment of the communication channel during this minute is equal to

· If the busy hour file access engine makes 9000 file accesses, and the time per access is 300 ms on average, then the busy hour access engine hardware utilization is

The concept of equipment utilization will be used quite often. The closer the equipment utilization is to 100%, the greater the delay and the longer the queue.

Using the previous formula, you can compile tables of Poisson function values, from which you can determine the probability of receivingm or more messages in a given period of time. For example, if an average of 3.1 messages per second [i.e. e. λ = 3.1], then the probability of receiving 5 or more messages in a given second is 0.2018 (form = 5 in the table). Or in analytic form

Using this expression, the systems analyst can calculate the probability that the system will not meet a given load criterion.

Often initial calculations can be made for equipment load values.

p ≤ 0.9

These values ​​can be obtained using Poisson tables.

Let again the average message arrival rate λ = 3.1 messages/s. It follows from the tables that the probability of receiving 6 or more messages in 1 s is 0.0943. Therefore, this number can be taken as a load criterion for initial calculations.

10.6.2. Design Challenges

With the random nature of the arrival of messages at the device, the latter spends part of the time processing or servicing each message, resulting in the formation of queues. The queue at the bank is waiting for the release of the cashier and his computer (terminal). The message queue in the computer's input buffer is waiting to be processed by the processor. The queue of requests for data arrays is waiting for the release of channels, etc. Queues can form in all bottlenecks of the system.

The higher the utilization rate of the equipment, the longer the resulting queues. As will be shown below, it is possible to design a system that works satisfactorily with a utilization factor of ρ = 0.7, but a factor greater than ρ > 0.9 may result in poor quality of service. In other words, if a bulk data link has a 20% load, it is unlikely to have a queue on it. If loading; is 0.9, then, as a rule, queues will form, sometimes very large ones.

The coefficient of equipment utilization is equal to the ratio of the load on the equipment to the maximum load that this equipment can withstand, or is equal to the ratio of the time the equipment is occupied to the total time of its operation.

When designing a system, it is common to estimate the utilization factor for various types of equipment; relevant examples will be given in subsequent chapters. Knowing these coefficients allows you to calculate the queues for the corresponding equipment.

· What is the length of the queue?

· How much time will it take?

Questions of this type can be answered using queuing theory.

10.6.3. Queuing systems, their classes and main characteristics

For QS, event flows are flows of requests, flows of "servicing" requests, etc. If these flows are not Poisson (Markov process), the mathematical description of the processes occurring in QS becomes incomparably more complex and requires a more cumbersome apparatus, bringing it to analytic formulas are possible only in the simplest cases.

However, the apparatus of the “Markovian” queuing theory can also be useful in the case when the process occurring in the QS is different from the Markov one; with its help, the QS efficiency characteristics can be estimated approximately. It should be noted that the more complex the QS, the more service channels it contains, the more accurate are the approximate formulas obtained using the Markov theory. In addition, in a number of cases, in order to make informed decisions on managing the operation of the QS, it is not at all necessary to have exact knowledge of all its characteristics, often quite approximate, indicative.

QS are classified into systems with:

failures (with losses). In such systems, a request that arrives at the moment when all channels are busy receives a "refusal", leaves the QS and does not participate in the further service process.

waiting (with queue). In such systems, a request that arrives when all channels are busy gets queued and waits until one of the channels becomes free. When the channel is free, one of the applications in the queue is accepted for service.

Service (queue discipline) in a waiting system can be

orderly (applications are served in the order of receipt),

· disordered(applications are served in random order) or

stack (the last application is selected first from the queue).

Priority

o with static priority

o with dynamic priority

(in the latter case priori tet may, for example, increase with the waiting time for the request).

Systems with a queue are divided into systems

· with unlimited waiting and

· with limited waiting.

In systems with unlimited waiting, each request that arrives at the moment when there are no free channels gets into the queue and "patiently" waits for the release of the channel that will accept it for service. Any application received by the CMO will sooner or later be served.

In systems with limited waiting, certain restrictions are imposed on the stay of the application in the queue. These restrictions may apply

· queue length (the number of applications simultaneously in the queue system with a limited queue length),

· the time the application stays in the queue (after a certain period of stay in the queue, the application leaves the queue and the system leaves with a limited waiting time),

· total time spent by the application in the QS

etc.

Depending on the type of QS, when evaluating its effectiveness, certain values ​​(performance indicators) can be used. For example, for a QS with failures, one of the most important characteristics of its productivity is the so-called absolute bandwidth the average number of requests that the system can serve per unit of time.

Along with the absolute is often considered relative throughput CMO is the average share of incoming requests served by the system (the ratio of the average number of requests served by the system per unit of time to the average number of requests received during this time).

In addition to the absolute and relative throughputs in the analysis of QS with failures, we may, depending on the task of the study, be interested in other characteristics, for example:

· average number of busy channels;

· average relative downtime of the system as a whole and an individual channel

etc.

Expectant QSs have slightly different characteristics. Obviously, for a QS with unlimited waiting time, both absolute and relative throughput lose their meaning, since each claim arrives early.or later will be served. For such a QS, the important characteristics are:

· the average number of applications in the queue;

· the average number of applications in the system (in the queue and under service);

· average waiting time for an application in the queue;

· average time spent by an application in the system (in the queue and under service);

as well as other characteristics of expectation.

For a QS with limited waiting, both groups of characteristics are of interest: both absolute and relative throughput, and waiting characteristics.

To analyze the process occurring in the QS, it is essential to know the main parameters of the system: the number of channels P, application flow intensityλ , the performance of each channel (the average number of requests μ serviced by the channel per unit time), the conditions for the formation of the queue (restrictions, if any).

Depending on the values ​​of these parameters, the characteristics of the QS operation efficiency are expressed.

10.6.4. Formulas for calculating QS characteristics for the case of service with one device

Figure 0 - 6 Model of a queuing system with a queue

Such queues can be created by messages at the input of the processor waiting to be processed. They can occur during the operation of subscriber stations connected to a multipoint communication channel. Similarly, queues of cars are formed at gas stations. However, if there is more than one entrance to the service, we have a queue with many devices and the analysis becomes more complicated.

Consider the case of the simplest flow of service requests.

The purpose of the queuing theory presented here is to approximate the average queue size, as well as the average time spent by messages waiting in queues. It is also desirable to estimate how often the queue exceeds a certain length. This information will allow us to calculate, for example, the required amount of buffer memory for storing message queues and related programs, the required number of communication lines, the required buffer sizes for hubs, etc. It will be possible to estimate response times.

Each of the characteristics varies depending on the means used.

Consider a queue with a single server. When designing a computing system, most queues of this type are calculated using the above formulas. service time variation factor

The Khinchin-Polachek formula is used to calculate queue lengths in the design of information systems. It is applied in the case of an exponential distribution of the arrival time for any distribution of service time and any control discipline, so long as the choice of the next message for service does not depend on the service time.

When designing systems, there are such situations when queues arise when the control discipline undoubtedly depends on the service time. For example, in some cases, we may choose to use shorter messages for service first in order to get a faster average service time. When managing a communication line, it is possible to assign a higher priority to input messages than to output messages, because the former are shorter. In such cases, it is no longer necessary to use the Khinchin equation

Most service times in information systems lie somewhere between these two cases. Service times that are constant are rare. Even the access time to the hard disk is not constant due to the different position of the data arrays on the surface. One example illustrating the case of constant service time is the occupation of the communication line for the transmission of messages of a fixed length.

On the other hand, the spread of service time is not as large as in the case of an arbitrary or exponential distribution, i.e.,σs rarely reaches valuest s. This case is sometimes considered the "worst case" and therefore formulas are used that refer to the exponential distribution of service times. Such a calculation may give somewhat overestimated queue sizes and waiting times, but this error is at least not dangerous.

The exponential distribution of service times is certainly not the worst case that one has to deal with in reality. However, if the service times obtained from the calculation of the queues turn out to be worse distributed than the exponentially distributed times, this is often a warning signal for the developer. If the standard deviation is greater than the mean value, then there is usually a need to correct the calculations.

Consider the following example. There are six message types with service times of 15, 20, 25, 30, 35, and 300. The number of messages for each type is the same. The standard deviation of these times is somewhat higher than their average. The last service time value is much larger than the others. This will cause messages to be in the queue much longer than if the service times were of the same order. In this case, when designing, it is advisable to take measures to reduce the length of the queue. For example, if these numbers are related to message lengths, then perhaps very long messages should be split into parts.

10.6.6. Calculation example

When designing a banking system, it is desirable to know the number of customers who will have to wait in line for one cashier during peak hours.

The system response time and its standard deviation are calculated taking into account the time of data entry from the workstation, printing and document processing.

The actions of the cashier were timed. The service time ts is equal to the total time spent by the cashier on the client. The cashier's utilization rate ρ is proportional to the time of his employment. If λ is the number of customers during peak hours, then ρ for the cashier is

Let's say there are 30 customers per hour during peak hours. On average, a cashier spends 1.5 minutes per customer. Then

ρ = (1.5 * 30) / 60 = 0.75

i.e. the cashier is used by 75%.

The number of people in line can be quickly estimated using graphs. It follows from them that if ρ = 0.75, then the average number nq of peoplein line at the checkout lies between 1.88 and 3.0 depending on the standard deviation for t s .

Assume that the measurement of the standard deviation for ts gave a value of 0.5 min. Then

σ s = 0.33 t s

From the graph in the first figure, we find that nq = 2.0, i.e., on average, two customers will be waiting at the checkout.

The total time a customer spends at the checkout can be found as

t ∑ = t q + t s = 2.5 min + 1.5 min = 4 min

where t s is calculated using the Khinchin-Polachek formula.

10.6.7. gain factor

Analyzing the curves in the figures, we see that when the equipment serving the queue is used more than 80%, the curves begin to grow at an alarming rate. This fact is very important in the design of data transmission systems. If we are designing a system with more than 80% hardware utilization, then a slight increase in traffic can lead to a drastic drop in system performance or even cause it to crash.

An increase in incoming traffic by a small number of x%. leads to an increase in the queue size by approximately

If the equipment utilization rate is 50%, then this increase is equal to 4ts% for the exponential distribution of service time. But if the equipment utilization is 90%, then the increase in the queue size is 100ts%, which is 25 times more. A slight increase in load at 90% equipment utilization leads to a 25-fold increase in queue sizes compared to the case of 50% equipment utilization.

Similarly, the queue time increases by

With an exponentially distributed service time, this value has the value 4 t s2 for equipment utilization equal to 50% and 100 t s2 for a coefficient of 90%, i.e. again 25 times worse.

In addition, for small equipment utilization factors, the effect of changes in σs on the queue size is insignificant. However, for large coefficients, the change σ s greatly affects the size of the queue. Therefore, when designing systems with high equipment utilization, it is desirable to obtain accurate information about the parameterσ s. Inaccuracy of the assumption regarding the exponentiality of the distribution of tsis most noticeable at large values ​​of ρ. Moreover, if the service time suddenly increases, which is possible in communication channels when transmitting long messages, then in the case of a large ρ, a significant queue is formed.

Considered in the previous lecture, a Markov random process with discrete states and continuous time takes place in queuing systems (QS).

Queuing systems - these are systems in which service requests are received at random times, while the received requests are serviced using the service channels available to the system.

Examples of queuing systems are:

• settlement and cash nodes in banks, enterprises;
• personal computers that serve incoming applications or requirements for solving certain problems;
• car service stations; gas station;
• audit firms;
• departments of tax inspections involved in the acceptance and verification of the current reporting of enterprises;
• telephone exchanges, etc.

	Knots	Requirements
Hospital	Orderlies	Patients
Production
The airport	Runway exits Registration points	Passengers

Consider the scheme of QS operation (Fig. 1). The system consists of a request generator, a dispatcher and a service node, a failure accounting node (terminator, request destroyer). A service node can generally have several service channels.

Rice. one

1. Application Generator – an object that generates applications: a street, a workshop with installed units. The input is application flow(the flow of customers to the store, the flow of broken units (cars, machine tools) for repairs, the flow of visitors to the wardrobe, the flow of cars to gas stations, etc.).
2. Dispatcher – a person or device that knows what to do with the ticket. A node that regulates and directs requests to service channels. Dispatcher:

• accepts applications;
• forms a queue if all channels are busy;
• directs them to service channels, if any;
• refuses applications (for various reasons);
• receives information from the service node about free channels;
• keeps track of system time.

1. Turn - request accumulator. The queue may not exist.
2. Service node consists of a finite number of service channels. Each channel has 3 states: free, busy, idle. If all channels are busy, then you can come up with a strategy to whom to transfer the application.
3. Refusal from service occurs if all channels are busy (some of them may not work).

In addition to these basic elements in QS, some sources also distinguish the following components:

terminator - destroyer of transactions;

warehouse - storage of resources and finished products;

accounting account - for performing operations of the "posting" type;

manager - manager of resources;

CMO classification

The first division (by the presence of queues):

• CMO with failures;
• CMO with a queue.

AT CMO with failures a request that arrives at the moment when all channels are busy is rejected, leaves the QS, and is not served further.

AT CMO with a queue an application that arrives at a time when all channels are busy does not leave, but queues up and waits for an opportunity to be served.

QS with queues are divided into different types depending on how the queue is organized - limited or not limited. Restrictions can relate to both the length of the queue and the waiting time, "service discipline".

So, for example, the following QS are considered:

• QS with impatient requests (queue length and service time are limited);
• QS with priority service, i.e. some applications are served out of turn, etc.

Queue restriction types can be combined.

Another classification divides the CMO according to the source of applications. The system itself or some external environment that exists independently of the system can generate applications (requirements).

Naturally, the flow of requests generated by the system itself will depend on the system and its state.

In addition, SMOs are divided into open CMO and closed SMO.

In an open QS, the characteristics of the flow of applications do not depend on the state of the QS itself (how many channels are busy). In a closed QS, they depend. For example, if one worker services a group of machines that require adjustment from time to time, then the intensity of the flow of "requirements" from the machines depends on how many of them are already in good order and waiting for adjustment.

An example of a closed system: the issuance of a salary by a cashier at an enterprise.

By the number of channels, QS are divided into:

• single-channel;
• multichannel.

Characteristics of the queuing system

The main characteristics of a queuing system of any kind are:

• the input stream of incoming requirements or service requests;
• queue discipline;
• service mechanism.

Requirements input stream

To describe the input stream, you need to set a probabilistic law that determines the sequence of moments of receipt of service requirements, and indicate the number of such claims in each regular receipt. In this case, as a rule, they operate with the concept of "probabilistic distribution of the moments of receipt of requirements". Here you can act like single and group requirements (the number of such claims in each successive receipt). In the latter case, we are usually talking about a queuing system with parallel-group service.

A i– arrival time between requirements – independent identically distributed random variables;

E(A) is the mean (MO) arrival time;

λ=1/E(A)- the intensity of receipt of requirements;

Input stream characteristics:

1. A probabilistic law that determines the sequence of moments of receipt of service requirements.
2. The number of requests in each next arrival for multicast flows.

Queue discipline

Turn - a set of requirements waiting to be serviced.

The queue has a name.

Queue discipline determines the principle according to which the requests arriving at the input of the service system are connected from the queue to the service procedure. The most commonly used queue disciplines are defined by the following rules:

• first come - first served;

first in first out (FIFO)

the most common type of queue.

What data structure is suitable for describing such a queue? The array is bad (limited). You can use a LIST structure.

The list has a beginning and an end. The list consists of entries. An entry is a list cell. The application comes to the end of the list, and is selected for service from the beginning of the list. The entry consists of a description of the application and a link (an index of who is behind it). In addition, if the queue has a time limit, then the time limit must also be specified.

You, as programmers, should be able to make lists two-sided, one-sided.

List actions:

• insert into the tail;
• take from the beginning;
• remove from list after timeout.
• last come, first served LIFO (cartridge clip, dead end at the railway station, went into a full car).

A structure known as a STACK. Can be described by an array or list structure;

• random selection of applications;
• selection of applications by priority criterion.

Each application is characterized, among other things, by a priority level and, upon arrival, is placed not at the tail of the queue, but at the end of its priority group. The dispatcher sorts by priority.

Queue characteristics

• limitationwaiting time the moment of service occurrence (there is a queue with a limited waiting time for service, which is associated with the concept of “admissible queue length”);
• queue length.

Service mechanism

Service mechanism is determined by the characteristics of the service procedure itself and the structure of the service system. Maintenance procedures include:

• number of service channels ( N);
• the duration of the service procedure (probabilistic distribution of the service time of requirements);
• the number of requirements satisfied as a result of the implementation of each such procedure (for group applications);
• the probability of failure of the serving channel;
• service system structure.

For an analytical description of the characteristics of the service procedure, the concept of "probabilistic distribution of the service time of requirements" is used.

Si– service time i th requirement;

E(S)– average service time;

μ=1/E(S)- the speed of service requirements.

It should be noted that the time for servicing an application depends on the nature of the application itself or the requirements of the client and on the state and capabilities of the servicing system. In some cases it is also necessary to take into account service channel failure probability after a certain limited time interval. This characteristic can be modeled as a stream of failures entering the QS and having priority over all other applications.

QS utilization factor

Nμ – service rate in the system when all service devices are busy.

ρ=λ/( Nμ) is called QS utilization factor , shows how much system resources are being used.

Service system structure

The structure of the service system is determined by the number and mutual arrangement of service channels (mechanisms, devices, etc.). First of all, it should be emphasized that a service system may have not one service channel, but several; a system of this kind is able to serve several requirements simultaneously. In this case, all service channels offer the same services, and, therefore, it can be argued that there is parallel service .

Example. Cash registers in the store.

The service system can consist of several different types of service channels through which each serviced requirement must pass, i.e. in the service system requirements servicing procedures are implemented sequentially . The service mechanism defines the characteristics of the outgoing (served) stream of requests.

Example. Medical Commission.

Combined Service - servicing deposits in the savings bank: first the controller, then the cashier. As a rule, 2 controllers per cashier.

So, the functionality of any queuing system is determined by the following main factors :

• probabilistic distribution of the moments of receipt of service requests (single or group);
• requirements source capacity;
• probabilistic distribution of service duration time;
• service system configuration (parallel, serial or parallel-serial service);
• the number and performance of serving channels;
• queue discipline.

The main criteria for the effectiveness of the functioning of the QS

As the main criteria for the effectiveness of the functioning of queuing systems Depending on the nature of the problem being solved, there may be:

• the probability of immediate service of the received application (P service =K obs /K post);
• the probability of denial of service of the received application (P otk =K otk /K post);

It is obvious that R obl + P otk =1.

Flows, delays, service. Pollacek–Khinchin formula

Delay – one of the QS service criteria, the time spent by the request in anticipation of service.

D i– delay in the request queue i;

W i \u003d D i + S i– time spent in the system of the requirement i.

(with probability 1) is the established average delay of a request in the queue;

(with probability 1) is the steady-state average time the requirement spends in the QS (waiting).

Q(t) - the number of requests in the queue at a time t;

L(t)– number of customers in the system at a time t(Q(t) plus the number of requirements that are in service at the time t.

Then exponents (if any)

(with probability 1) is the steady-state time-average number of requests in the queue;

(with probability 1) is the steady-state time-averaged number of requests in the system.

Note that ρ<1 – обязательное условие существования d, w, Q and L in the queuing system.

If we remember that ρ= λ/( Nμ), then it is clear that if the intensity of receipt of requests is greater than Nμ, then ρ>1, and it is natural that the system will not be able to cope with such a flow of applications, and therefore, one cannot speak of d, w, Q and L.

The most general and necessary results for queuing systems include the conservation equations

It should be noted that the above criteria for evaluating the performance of the system can be analytically calculated for queuing systems M/M/N(N>1), i.e., systems with Markov flows of customers and service. For M/G/ l for any distribution G and for some other systems. In general, the distribution of time between arrivals, the distribution of service time, or both must be exponential (or a kind of k-th order exponential Erlang distribution) for an analytic solution to be possible.

In addition, you can also talk about such characteristics as:

• absolute throughput of the system – А=Р service *λ;
• relative throughput of the system -

Another interesting (and illustrative) example of an analytical solution – calculation of steady-state average queue delay for a queuing system M/G/ 1 according to the formula:

.

In Russia, this formula is known as the Pollacek formula. – Khinchin, abroad this formula is associated with the name of Ross.

Thus, if E(S) has a greater value, then the overload (measured in this case as d) will be larger; which is to be expected. The formula also reveals a less obvious fact: congestion also increases when the variability in the service time distribution increases, even if the average service time remains the same. Intuitively, this can be explained as follows: the variance of the service time random variable can take on a large value (since it must be positive), i.e. the only service device will be busy for a long time, which will lead to an increase in the queue.

The subject of queuing theory is to establish the relationship between the factors that determine the functionality of the queuing system, and the efficiency of its functioning. In most cases, all parameters that describe queuing systems are random variables or functions, so these systems are referred to as stochastic systems.

The random nature of the flow of applications (requirements), as well as, in the general case, the duration of service leads to the fact that a random process occurs in the queuing system. By the nature of the random process occurring in a queuing system (QS) are distinguished Markov and non-Markov systems . In Markov systems, the incoming flow of requests and the outgoing flow of serviced requests (claims) are Poisson. Poisson flows make it easy to describe and build a mathematical model of a queuing system. These models have fairly simple solutions, so most of the well-known applications of queuing theory use the Markov scheme. In the case of non-Markovian processes, the problems of studying queuing systems become much more complicated and require the use of statistical modeling, numerical methods using a computer.

A large class of systems that are difficult to study analytically, but which are well studied by statistical modeling methods, is reduced to queuing systems (QS).

The SMO implies that there is sample paths(service channels) through which applications. It is customary to say that applications served channels. Channels can be different in purpose, characteristics, they can be combined in different combinations; applications can be in queues and waiting for service. Part of the applications can be served by channels, and some may refuse to do so. It is important that requests, from the point of view of the system, are abstract: this is what wants to be served, that is, to go through a certain path in the system. Channels are also an abstraction: they are what serve requests.

Applications can come unevenly, channels can serve different applications at different times, and so on, the number of applications is always very large. All this makes such systems difficult to study and manage, and it is not possible to trace all the causal relationships in them. Therefore, the notion that maintenance in complex systems is random is accepted.

Examples of QS (see Table 30.1) are: bus route and passenger transportation; production conveyor for processing parts; a squadron of aircraft flying into foreign territory, which is “served” by air defense anti-aircraft guns; the barrel and horn of the machine gun, which "serve" the cartridges; electric charges moving in some device, etc.

Table 30.1. Examples of queuing systems

Applications Channels Bus route and transportation of passengers Passengers Buses Production conveyor for parts processing Details, knots Machine tools, warehouses A squadron of aircraft flying into foreign territory, which is “served” by air defense anti-aircraft guns Aircraft Anti-aircraft guns, radars, arrows, shells The barrel and horn of the machine gun, which "serve" the cartridges Barrel, horn Electric charges moving in some device Technical device cascades

But all these systems are combined into one class of QS, since the approach to their study is the same. It consists in the fact that, firstly, with the help of a random number generator, random numbers are played, which imitate the RANDOM moments of the appearance of applications and the time of their service in the channels. But taken together, these random numbers are, of course, subject to statistical patterns.

For example, let's say: "applications come in on average in the amount of 5 pieces per hour." This means that the times between arrivals of two neighboring claims are random, for example: 0.1; 0.3; 0.1; 0.4; 0.2, as shown in Fig. 30.1, but in total they give an average of 1 (note that in the example this is not exactly 1, but 1.1 - but in another hour this sum, for example, can be equal to 0.9); but only for a long enough time the average of these numbers will become close to one hour.

The result (for example, the throughput of the system), of course, will also be a random variable on separate time intervals. But measured over a long period of time, this value will already, on average, correspond to the exact solution. That is, to characterize QS, they are interested in answers in a statistical sense.

So, the system is tested with random input signals subject to a given statistical law, and as a result, statistical indicators are taken averaged over the time of consideration or by the number of experiments. Earlier, in lectures 21(cm. rice. 21.1), we have already developed a scheme for such a statistical experiment (see Fig. 30.2).

Secondly, all QS models are assembled in a typical way from a small set of elements (channel, request source, queue, request, service discipline, stack, ring, and so on), which allows simulating these tasks. typical way. To do this, the system model is assembled from the constructor of such elements. It does not matter what particular system is being studied, it is important that the system diagram is assembled from the same elements. Of course, the structure of the circuit will always be different.

Let us list some basic concepts of QS.

Channels are what serves; are hot (they start servicing the request at the moment it enters the channel) and cold (the channel needs time to prepare to start servicing). Request sources - generate requests at random times, according to a user-specified statistical law. Applications, they are also clients, enter the system (generated by the sources of applications), pass through its elements (served), leave it served or unsatisfied. There are impatient applications - those who are tired of waiting or being in the system and who leave the CMO of their own free will. Applications form streams - a stream of applications at the system input, a stream of serviced applications, a stream of rejected applications. The flow is characterized by the number of applications of a certain type, observed in some place of the QS per unit of time (hour, day, month), that is, the flow is a statistical value.

Queues are characterized by queuing rules (service discipline), the number of places in the queue (how many customers can be in the queue at most), the structure of the queue (the connection between the places in the queue). There are limited and unlimited queues. Let's list the most important disciplines of service. FIFO (First In, First Out - first in, first out): if the application is the first to enter the queue, then it will be the first to leave for service. LIFO (Last In, First Out - last in, first out): if the application was the last one in the queue, then it will be the first to go for service (for example, cartridges in the horn of the machine). SF (Short Forward - short forward): those applications from the queue that have the shortest service time are served first.

Let's give a striking example showing how the right choice of one or another service discipline allows you to get tangible time savings.

Let there be two shops. In store No. 1, service is carried out on a first-come, first-served basis, that is, the FIFO service discipline is implemented here (see Figure 30.3).

Service time t service in fig. 30.3 shows how much time the seller will spend on servicing one buyer. It is clear that when buying piece goods, the seller will spend less time on service than when buying, say, bulk products that require additional manipulations (pick up, weigh, calculate the price, etc.). Waiting time t expected shows, after what time the next buyer will be served by the seller.

Store #2 implements the SF discipline (see Figure 30.4), which means that piece goods can be bought out of turn, since the service time t service such a purchase is small.

As can be seen from both figures, the last (fifth) buyer is going to purchase a piece goods, so the time of its service is small - 0.5 minutes. If this customer comes to store number 1, he will be forced to stand in line for a full 8 minutes, while in store number 2 he will be served immediately, out of turn. Thus, the average service time for each of the customers in a store with a FIFO service discipline will be 4 minutes, and in a store with a FIFO service discipline, it will be only 2.8 minutes. And the public benefit, time savings will be: (1 - 2.8/4) · 100% = 30 percent! So, 30% of the time saved for society - and this is only due to the correct choice of the service discipline.

The systems specialist must have a good understanding of the performance and efficiency resources of the systems he designs, hidden in the optimization of parameters, structures and maintenance disciplines. Modeling helps to reveal these hidden reserves.

When analyzing simulation results, it is also important to indicate the interests and the degree of their implementation. Distinguish between the interests of the client and the interests of the owner of the system. Note that these interests do not always coincide.

You can judge the results of the work of the CMO by indicators. The most popular of them:

the probability of customer service by the system;

throughput of the system;

the probability of denial of service to the client;

the probability of occupancy of each channel and all together;

average busy time of each channel;

probability of occupancy of all channels;

average number of busy channels;

downtime probability of each channel;

the probability of downtime of the entire system;

the average number of applications in the queue;

average waiting time for an application in the queue;

average time of service of the application;

average time spent by the application in the system.

It is necessary to judge the quality of the resulting system by the totality of the values ​​of the indicators. When analyzing the simulation results (indicators), it is also important to pay attention to the interests of the client and the interests of the system owner, that is, it is necessary to minimize or maximize this or that indicator, as well as the degree of their implementation. Note that most often the interests of the client and the owner do not coincide with each other or do not always coincide. The indicators will be denoted further H = { h 1 , h 2 , …} .

QS parameters can be: the intensity of the flow of applications, the intensity of the flow of service, the average time during which the application is ready to wait for service in the queue, the number of service channels, the discipline of service, and so on. Parameters are what affect the performance of the system. The parameters will be denoted below as R = { r 1 , r 2 , …} .

Example. Filling station (gas station).

1. Statement of the problem. On fig. 30.5 shows the plan of the gas station. Let's consider the QS modeling method on its example and the plan of its research. Drivers driving past gas stations on the road may want to fill up their car. Not all motorists in a row want to be serviced (refuel the car with gasoline); Let's say that out of the entire flow of cars, 5 cars per hour, on average, come to the gas station.

There are two identical dispensers at the gas station, the statistical performance of each of which is known. The first column serves on average 1 car per hour, the second on average - 3 cars per hour. The owner of the gas station paved a place for the cars where they can wait for service. If the columns are occupied, then other cars can wait for service at this place, but no more than two at a time. The queue will be considered general. As soon as one of the columns becomes free, the first car from the queue can take its place on the column (in this case, the second car moves to the first place in the queue). If a third car appears, and all the places (two of them) in the queue are occupied, then it is denied service, since it is forbidden to stand on the road (see road signs near gas stations). Such a car leaves the system forever and, as a potential client, is lost for the gas station owner. You can complicate the task by considering the cash register (another service channel, where you need to get after serving in one of the columns) and the queue to it, and so on. But in the simplest version, it is obvious that the flow paths of requests through the QS can be depicted as an equivalent diagram, and by adding the values ​​and designations of the characteristics of each element of the QS, we finally obtain the diagram shown in Fig. 30.6.

2. Research method of QS. In our example, we will apply the principle of sequential posting of requests (for details on the principles of modeling, see Fig. lecture 32). His idea is that the application is carried through the entire system from entry to exit, and only after that they start modeling the next application.

For clarity, we will build a timing diagram of the QS operation, reflecting on each ruler (the time axis t) the state of an individual element of the system. There are as many timelines as there are different places in the QS, streams. In our example, there are 7 of them (the flow of requests, the flow of waiting in the first place in the queue, the flow of waiting in the second place in the queue, the service flow in channel 1, the service flow in channel 2, the flow of requests served by the system, the flow of refused requests).

To generate the arrival time of requests, we use the formula for calculating the interval between the moments of arrival of two random events (see Fig. lecture 28):

In this formula, the amount of flow λ must be specified (before that, it must be determined experimentally on the object as a statistical average), r- random evenly distributed number from 0 to 1 from RNG or tables, in which random numbers must be taken in a row (without choosing specially).

A task. Generate a stream of 10 random events with an event rate of 5 events per hour.

The solution of the problem. Let's take random numbers uniformly distributed in the interval from 0 to 1 (see Fig. table), and calculate their natural logarithms (see Table 30.2).

Table 30.2. Fragment of a table of random numbers and their logarithms

r pp ln(r pp )

The Poisson flow formula defines the distance between two random events as follows: t= –Ln(r рр)/ λ . Then, considering that λ = 5 , we have the distances between two random neighboring events: 0.68, 0.21, 0.31, 0.12 hours. That is, events occur: the first - at a point in time t= 0 , the second - at the moment of time t= 0.68 , the third - at the time t= 0.89 , fourth - at time t= 1.20 , fifth - at time t= 1.32 and so on. Events - the arrival of applications will be reflected on the first line (see Fig. 30.7).

Rice. 30.7. Timing diagram of QS operation

The first request is taken and, since the channels are free at this moment, it is set for service in the first channel. Application 1 is transferred to the "1 channel" line.

The service time in the channel is also random and is calculated using a similar formula:

where the role of intensity is played by the magnitude of the service flow μ 1 or μ 2 , depending on which channel serves the request. We find the moment of the end of the service on the diagram, postponing the generated service time from the moment the service began, and lower the request to the “Served” line.

The application went through the CMO all the way. Now it is possible, according to the principle of sequential posting of orders, to also simulate the path of the second order.

If at some point it turns out that both channels are busy, then the request should be placed in the queue. On fig. 30.7 is the request with number 3. Note that, according to the conditions of the task, in the queue, unlike the channels, the requests are not randomly located, but are waiting for one of the channels to become free. After the release of the channel, the request is moved to the line of the corresponding channel and its servicing is organized there.

If all places in the queue at the moment when the next application arrives are occupied, then the application should be sent to the “Refused” line. On fig. 30.7 is bid number 6.

The procedure for simulating the service of requests is continued for some time of observation T n. The longer this time, the more accurate the simulation results will be in the future. In reality, for simple systems choose T n, equal to 50-100 or more hours, although sometimes it is better to measure this value by the number of considered applications.

Analytical study of queuing systems (QS) is an alternative approach to simulation modeling and consists in obtaining formulas for calculating the output parameters of QS with subsequent substitution of argument values ​​into these formulas in each individual experiment.

In QS models, the following objects are considered:

1) service requests (transactions);

2) service devices (OA), or devices.

The practical task of queuing theory is related to the study of operations by these objects and consists of separate elements that are influenced by random factors.

As an example of the problems considered in the theory of queuing, one can cite: matching the throughput of a message source with a data transmission channel, analyzing the optimal flow of urban transport, calculating the capacity of a waiting room for passengers at an airport, etc.

The request can be either in the service state or in the service pending state.

The service device can be either busy with service or free.

The QS state is characterized by a set of states of service devices and requests. The change of states in QS is called an event.

QS models are used to study the processes occurring in the system, when applying to the inputs of application flows. These processes are a sequence of events.

The most important output parameters of the QS

Performance

Bandwidth

Denial of Service Probability

Average service time;

Equipment load factor (OA).

Applications can be orders for the production of products, tasks solved in a computer system, customers in banks, goods arriving for transportation, etc. It is obvious that the parameters of applications entering the system are random variables and only their parameters can be known during research or design. distribution laws.

In this regard, the analysis of functioning at the system level, as a rule, is of a statistical nature. It is convenient to take the theory of queuing as a mathematical modeling tool, and use queuing systems as models of systems at this level.

The simplest QS models

In the simplest case, the QS is a device called a service device (OA), with queues of applications at the inputs.

M o d e l o n s e r e n t e r e s s e n c a t i o n (Fig. 5.1)

Rice. 5.1. QS model with failures:

0 – request source;

1 - service device;

a– input stream of requests for service;

in is the output stream of serviced requests;

With is the output stream of unserved requests.

In this model, there is no claim accumulator at the input of the OA. If a claim arrives from source 0 at the moment when the AA is busy servicing the previous claim, then the newly arrived claim exits the system (because it was denied service) and is lost (the flow With).

M o d e l o f C a n d i n g s e c r i o n s (Fig. 5.2)

Rice. 5.2. QS Model with Expectation

(N– 1) - the number of applications that can fit in the accumulator

This model has a claim accumulator at the input of the OA. If a customer arrives from source 0 at the moment when the CA is busy servicing the previous customer, then the newly arrived customer enters the accumulator, where it waits indefinitely until the CA becomes free.

LIMITED TIME SERVICE MODEL

w i d a n y (Fig. 5.3)

Rice. 5.4. Multichannel QS model with failures:

n- the number of identical service devices (devices)

In this model, there is not one OA, but several. Applications, unless otherwise stated, may be submitted to any non-servicing AB. There is no storage, so this model includes the properties of the model shown in Fig. 5.1: denial of service of the application means its irretrievable loss (this happens only if at the time of arrival of this application all OA are busy).

w a t h i n t h o m e (Fig. 5.5)

Rice. 5.6. Multi-channel QS model with waiting and recovery OA:

e- service devices that are out of order;

f– restored service vehicles

This model has the properties of the models presented in Figs. 5.2 and 5.4, as well as the properties that allow to take into account possible random failures of the OA, which in this case enter the repair block 2, where they stay for random periods of time spent on their restoration, and then return to the service block 1 again.

M i n o n a l m o l l Q O

OA w aiting time and recovery (Fig. 5.7)

Rice. 5.7. Multichannel QS Model with Limited Waiting Time and OA Recovery

This model is quite complex, since it simultaneously takes into account the properties of two not the simplest models (Figures 5.5 and 5.6).

Send your good work in the knowledge base is simple. Use the form below

Students, graduate students, young scientists who use the knowledge base in their studies and work will be very grateful to you.

Posted on http://allbest.ru

INTRODUCTION

CHAPTER 1. THEORETICAL PART

1.1 Queuing systems with failures

1.2 Modeling of queuing systems

1.3 The simplest QS with failures

1.4 Single-channel QS with failures

1.5 Multi-channel QS with failures

1.6 Single-channel QS with limited queue length

1.7 Single-channel QS with unlimited queue

1.8 Multichannel QS with limited queue length

1.9 Multi-channel QS with unlimited queue

1.10 QS modeling algorithm

CHAPTER 2. PRACTICAL PART

CHAPTER 3. SAFETY REGULATIONS

CONCLUSION

LIST OF USED LITERATURE

INTRODUCTION

Recently, in various areas of practice, it has become necessary to solve various probabilistic problems related to the operation of so-called queuing systems (QS).

Examples of such systems are: telephone exchanges, repair shops, ticket offices, taxi ranks, hairdressers, etc.

The theme of this course project is precisely the solution of such a problem.

However, in the proposed problem, a QS will be investigated, in which 2 flows of applications are considered, one of which has a priority.

Also, the considered processes are non-Markovian, since time factor is important.

Therefore, the solution of this problem is based not on the analytical description of the system, but on statistical modeling.

The purpose of the course work is to model the production process based on the representation of the main equipment as a queuing system.

To achieve the goal, the following tasks were set: - To analyze the features of the production process management; - Consider the organization of the production process in time; - Give the main options for reducing the duration of the production cycle;

To analyze the methods of managing the production process at the enterprise;

Consider the features of modeling the production process using the theory of QS;

Develop a model of the production process and evaluate the main characteristics of the QS, present the prospects for its further software implementation.

Consolidation of theoretical knowledge and obtaining skills for their practical application;

The report contains an introduction, three chapters, a conclusion, a list of references, applications.

The second chapter deals with the theoretical materials of the queuing system. And in the third we calculate the problem of queuing systems.

CHAPTER 1. THEORETICAL PART

1.1 Queuing systemscfailures

A queuing system (QS) is any system designed to service any requests (requirements) arriving at it at random times. Any device that is directly involved in servicing requests is called a service channel (or “device”). CMOs are both single- and multi-channel.

There are QS with failures and QS with a queue. In a QS with denials, a request that arrives at the moment when all channels are busy receives a refusal, leaves the QS, and then does not participate in its operation. In a QS with a queue, a claim that arrives at the moment when all channels are busy does not leave the QS, but enters the queue and waits until a channel becomes free. The number of places in the queue m can be both limited and unlimited. When m=0, a QS with a queue turns into a QS with failures. A queue can be limited not only by the number of requests standing in it (the length of the queue), but also by the waiting time (such QSs are called “systems with impatient clients”).

An analytical study of a QS is the simplest if all the flows of events that transfer it from state to state are the simplest (stationary Poisson). This means that the time intervals between events in streams have an exponential distribution with a parameter equal to the intensity of the corresponding stream. For QS, this assumption means that both the flow of requests and the flow of service are the simplest. A service flow is understood as a flow of requests served one after another by one continuously busy channel. This flow turns out to be the simplest only if the service time of the request tservice is a random variable with an exponential distribution. The parameter of this distribution m is the reciprocal of the average service time:

Instead of the phrase “service flow is the simplest”, they often say “service time is indicative”. Any QS in which all flows are simple is called a simple QS.

If all event flows are simple, then the process occurring in the QS is a Markov random process with discrete states and continuous time. Under certain conditions for this process, there is a final stationary regime, in which both the probabilities of states and other characteristics of the process do not depend on time.

QS models are convenient for describing individual subsystems of modern computing systems, such as the processor-main memory subsystem, the input-output channel, etc.

The computing system as a whole is a set of interconnected subsystems, the interaction of which is of a probabilistic nature. An application for solving a certain problem that enters the computing system goes through a sequence of stages of counting, accessing external storage devices and input-output devices.

After completing a certain sequence of such stages, the number and duration of which depend on the complexity of the program, the request is considered serviced and leaves the computing system.

Thus, the computing system as a whole can be represented by a set of QS, each of which displays the process of functioning of a separate device or a group of devices of the same type that are part of the system.

The tasks of the queuing theory are to find the probabilities of various states of the QS, as well as to establish the relationship between the given parameters (the number of channels n, the intensity of the flow of requests l, the distribution of service time, etc.) and the performance characteristics of the QS. Such characteristics can be considered, for example, the following:

The average number of applications A served by the QS per unit of time, or the absolute throughput of the QS;

The probability of servicing the incoming request Q or the relative throughput of the QS; Q \u003d A / l;

Rothk failure probability, i.e. the probability that the received application will not be served and will be rejected; Rotk = 1 - Q;

The average number of applications in the QS (served or waiting in line) ;

The average number of applications in the queue;

Average time spent by an application in the CMO (in queue or under service) ;

The average time an application spends in the queue;

Average number of busy channels.

In the general case, all these characteristics depend on time. But many QSs operate under constant conditions for quite a long time, and therefore a regime close to stationary has time to be established for them.

We are here everywhere, without stipulating this each time specifically, we will calculate the final probabilities of states and the final characteristics of the QS efficiency related to the limiting stationary mode of its operation.

A QS is called open if the intensity of the incoming flow of applications does not depend on the state of the QS itself.

For any open QS in the limiting stationary mode, the average residence time of a customer in the system is expressed in terms of the average number of customers in the system using the Little formula:

where l is the intensity of the flow of applications.

A similar formula (also called Little's formula) relates the average time a ticket spends in a queue and the average number of tickets in a queue:

Little's formulas are very useful, because they allow you to calculate not both efficiency characteristics (average residence time and average number of customers), but only one of them.

We specially emphasize that formulas (1) and (2) are valid for any open QS (single-channel, multi-channel, for any types of request flows and service flows); the only requirement for customer flows and services is that they be stationary.

Similarly, the formula expressing the average number of occupied channels through the absolute bandwidth A has a universal value for open QS:

where is the intensity of the service flow.

Very many problems of the theory of queuing, concerning the simplest QS, are solved using the scheme of death and reproduction.

The final probabilities of the states are expressed by the formulas:

Scroll characteristics of queuing systems can be represented as follows:

· average service time;

average waiting time in the queue;

The average time spent in the SMO;

The average queue length

· the average number of applications in the CMO;

the number of service channels;

the intensity of the input flow of applications;

service intensity;

load intensity;

Load factor

Relative throughput;

The absolute throughput

share of QS downtime;

the share of serviced applications;

the proportion of lost applications;

average number of busy channels;

average number of free channels;

channel load factor;

average idle time of channels.

1 . 2 Modeling of queuing systems

QS transitions from one state to another occur under the influence of well-defined events - the receipt of applications and their servicing. The sequence of occurrence of events following one after another at random moments of time forms the so-called stream of events. Examples of such flows in commercial activities are flows of various nature - goods, money, documents, transport, customers, customers, phone calls, negotiations. The behavior of the system is usually determined not by one, but by several streams of events at once. For example, customer service in a store is determined by customer flow and service flow; in these flows, the moments of appearance of buyers, the time spent in the queue and the time spent on serving each buyer are random.

In this case, the main characteristic feature of flows is the probabilistic distribution of time between neighboring events. There are various streams that differ in their characteristics.

A stream of events is called regular if events in it follow one after another at predetermined and strictly defined intervals of time. Such a flow is ideal and is very rare in practice. More often there are irregular flows that do not have the property of regularity.

A stream of events is called stationary if the probability of any number of events falling into a time interval depends only on the length of this interval and does not depend on how far this interval is from the beginning of time. The stationarity of a flow means that its probabilistic characteristics are independent of time, in particular, the intensity of such a flow is the average number of events per unit of time and remains constant. In practice, flows can usually be considered stationary only for a certain limited time interval. Typically, the flow of customers, for example, in a store changes significantly during the working day. However, it is possible to single out certain time intervals within which this flow can be considered as stationary, having a constant intensity.

A stream of events is called a stream without consequences if the number of events that fall on one of the arbitrarily chosen time intervals does not depend on the number of events that fall on another, also arbitrarily chosen interval, provided that these intervals do not intersect. In a flow with no consequence, events appear at successive times independently of each other. For example, the flow of customers entering a store can be considered a flow without consequences, because the reasons that led to the arrival of each of them are not related to similar reasons for other customers.

A stream of events is called ordinary if the probability of hitting two or more events at once for a very short period of time is negligible compared to the probability of hitting only one event. In an ordinary stream, events occur one at a time, rather than two or more times. If a flow simultaneously possesses the properties of stationarity, ordinariness, and the absence of a consequence, then such a flow is called the simplest (or Poisson) flow of events. The mathematical description of the impact of such a flow on systems is the simplest. Therefore, in particular, the simplest flow plays a special role among other existing flows.

Consider some time interval t on the time axis. Let us assume that the probability of a random event falling into this interval is p, and the total number of possible events is n. In the presence of the property of an ordinary flow of events, the probability p must be a sufficiently small value, and i a sufficiently large number, since mass phenomena are considered.

Under these conditions, to calculate the probability of hitting a certain number of events t in a time interval t, you can use the Poisson formula:

Pm, n= am_e-a; (m=0,n),

where the value a \u003d pr is the average number of events falling on the time interval t, which can be determined through the intensity of the flow of events X as follows: a \u003d l f

The dimension of the flow intensity X is the average number of events per unit time. Between p and l, p and f there is the following relationship:

n= l t; p= f/t

where t is the entire period of time on which the action of the flow of events is considered.

It is necessary to determine the distribution of the time interval T between events in such a stream. Since this is a random variable, let's find its distribution function. As is known from probability theory, the integral distribution function F(t) is the probability that the value T will be less than the time t.

F(t)=P(T

According to the condition, no events should occur during the time T, and at least one event should appear on the time interval t. This probability is calculated using the probability of the opposite event on the time interval (0; t), where no event fell, i.e. m = 0, then

F(t)=1-P0=1-(a0*e-a)0!=1-e-Xt,t?0

For small?t, you can get an approximate formula obtained by replacing the function e-Xt, with only two terms of the expansion in a series in powers?t, then the probability of hitting at least one event in a small time interval?t is

P(T

The distribution density of the time interval between two successive events is obtained by differentiating F(t) with respect to time,

f(t)= l e- l t ,t?0

Using the obtained distribution density function, one can obtain the numerical characteristics of the random variable T: the mathematical expectation M (T), the variance D (T) and the standard deviation y (T).

M(T)= l??0 t*e-lt*dt=1/ l; D(T)=1/ l2 ; y(T)=1/l.

From this we can draw the following conclusion: the average time interval T between any two neighboring events in the simplest flow is on average 1/l, and its standard deviation is also 1/l, where, is the flow intensity, i.e. the average number of events occurring per unit of time. The law of distribution of a random variable with such properties M(T) = T is called exponential (or exponential), and the value l is a parameter of this exponential law. Thus, for the simplest flow, the mathematical expectation of the time interval between neighboring events is equal to its standard deviation. In this case, the probability that the number of requests arriving for servicing in a time interval t is equal to k is determined by the Poisson law:

Pk(t)=(lt)k/ k! *e-l t,

where l - the intensity of the flow of applications, the average number of events in the QS per unit of time, for example [person / min; rub./hour; checks/hour; documents/day; kg./hour; tons/year] .

For such a flow of applications, the time between two neighboring applications T is distributed exponentially with a probability density:

ѓ(t)= l e-l t.

The random waiting time in the service start queue t can also be considered exponentially distributed:

? (toch)=V*e-v toch,

where v is the intensity of the queue passage flow, determined by the average number of applications passing for service per unit of time:

v=1/Point,

where To is the average waiting time for service in the queue.

The output flow of requests is associated with the service flow in the channel, where the service duration tobs is also a random variable and in many cases obeys an exponential distribution law with a probability density:

?(t obs)=µ*e µ t obs,

where µ is the intensity of the service flow, i.e. average number of requests served per unit of time:

µ=1/ t obs[people/min; rub./hour; checks/hour; documents/day; kg./hour; tons/year] ,

where t obs is the average time for servicing requests.

An important characteristic of the QS, which combines the indicators l and µ , is the intensity of the load: с= l/ µ, which shows the degree of coordination of the input and output flows of service channel requests and determines the stability of the queuing system.

In addition to the concept of the simplest flow of events, it is often necessary to use the concepts of flows of other types. A stream of events is called a Palm stream when in this stream the time intervals between successive events T1, T2, ..., Tk ..., Tn are independent, equally distributed, random variables, but unlike the simplest stream, they are not necessarily distributed according to an exponential law. The simplest flow is a special case of the Palm flow.

An important special case of the Palm stream is the so-called Erlang stream.

This stream is obtained by "thinning" the simplest stream. Such "thinning" is performed by selecting events from a simple stream according to a certain rule.

For example, if we agree to take into account only every second event from the elements of the simplest flow, we get a second-order Erlang flow. If we take only every third event, then an Erlang flow of the third order is formed, and so on.

It is possible to obtain Erlang streams of any k-th order. Obviously, the simplest flow is the Erlang flow of the first order.

Any study of a queuing system begins with a study of what needs to be served, and therefore with an examination of the incoming stream of customers and its characteristics.

Since the time moments t and the time intervals of receipt of requests φ, then the duration of service operations t obs and the waiting time in the queue toch, as well as the length of the queue lch are random variables, then, therefore, the characteristics of the QS state are of a probabilistic nature, and their description should be apply methods and models of queuing theory.

The characteristics k, f, l, Loch, Toch, v, tobs, µ, p, Pk listed above are the most common for QS, which are usually only some part of the objective function, since it is also necessary to take into account the indicators of commercial activity.

1 . 3 The simplest QS with failures

An n-channel QS with failures receives the simplest flow of applications with intensity l; service time - indicative with a parameter. The QS states are numbered according to the number of requests in the QS (due to the absence of a queue, it coincides with the number of busy channels):

S0 - QS is free;

S1 - one channel is occupied, the rest are free;

...;

S k- busy k channels, the rest are free (1 kn);

…;

S n- everyone is busy n channels.

The final state probabilities are expressed by the Erlang formulas:

where s=l/m.

Performance characteristics:

A=(1-p n); Q=1-p n; Pp = p n; =(1-p n).

For large values P state probabilities (1*) can be conveniently calculated using tabulated functions:

(Poisson distribution) and

,

of which the first can be expressed in terms of the second:

Using these functions, the Erlang formulas (1*) can be rewritten as

.

1.4 Single-channel QS with failures

Let us analyze a simple single-channel QS with denials of service, which receives a Poisson flow of requests with intensity l, and service occurs under the action of a Poisson flow with intensity m.

The operation of a single-channel QS n=1 can be represented as a labeled state graph (3.1).

QS transitions from one state S0 to another S1 occur under the action of an input flow of requests with intensity l, and the reverse transition occurs under the action of a service flow with intensity m.

Let us write the system of Kolmogorov differential equations for state probabilities according to the above rules:

From where we get the differential equation for determining the probability p0(t) of the state S0:

This equation can be solved under initial conditions under the assumption that the system at the moment t=0 was in the state S0, then р0(0)=1, р1(0)=0.

In this case, the solution of the differential equation allows us to determine the probability that the channel is free and not busy with service:

Then it is not difficult to obtain an expression for the probability of determining the probability of the channel being busy:

The probability p0(t) decreases with time and in the limit at t>? tends to size

and the probability p1(t) at the same time increases from 0, tending to the limit as t>? to the value

These probability limits can be obtained directly from the Kolmogorov equations under the condition

The functions p0(t) and p1(t) determine the transient process in a single-channel QS and describe the process of exponential approximation of the QS to its limit state with a time constant characteristic of the system under consideration.

With sufficient accuracy for practice, we can assume that the transient process in the QS ends within a time equal to 3f.

The probability p0(t) determines the relative throughput of the QS, which determines the proportion of serviced requests in relation to the total number of incoming requests, per unit of time.

Indeed, p0(t) is the probability that a claim arriving at time t will be accepted for service. In total, l requests arrive on average per unit of time, and lp0 requests are serviced from them.

Then the share of serviced requests in relation to the entire flow of requests is determined by the value

In the limit at t>? practically already at t>3f the value of the relative throughput will be equal to

The absolute throughput, which determines the number of requests served per unit of time in the limit for t>?, is equal to:

Accordingly, the share of applications that were refused is, under the same limiting conditions:

and the total number of unserved requests is equal to

Examples of single-channel QS with denial of service are: the order desk in the store, the control room of a trucking company, the warehouse office, the management office of a commercial company, with which communication is established by telephone.

1.5 Multichannel QS with failures

In commercial activities, examples of multi-channel CMOs are offices of commercial enterprises with several telephone channels, a free reference service for the availability of the cheapest cars in auto stores in Moscow has 7 telephone numbers, and, as you know, it is very difficult to get through and get help.

Consequently, auto shops are losing customers, the opportunity to increase the number of cars sold and sales revenue, turnover, profit.

Tourist tour companies have two, three, four or more channels, such as Express-Line.

Let us consider a multi-channel QS with denials of service, which receives a Poisson flow of requests with intensity l.

The service flow in each channel has an intensity m. Based on the number of QS requests, its states Sk are determined, represented as a labeled graph:

S0 - all channels are free k=0,

S1 - only one channel is occupied, k=1,

S2 - only two channels are occupied, k=2,

Sk - k channels are occupied,

Sn - all n channels are occupied, k= n.

The states of a multichannel QS change abruptly at random times. The transition from one state, for example, S0 to S1, occurs under the influence of the input flow of requests with intensity l, and vice versa - under the influence of the flow of servicing requests with intensity m.

For the transition of the system from the state Sk to Sk-1, it does not matter which of the channels is released, therefore the flow of events that transfers the QS has an intensity km, therefore, the flow of events that transfers the system from Sn to Sn-1 has an intensity nm.

This is how the classical Erlang problem is formulated, named after the Danish engineer - mathematician - founder of the theory of queuing.

A random process occurring in a QS is a special case of the “birth-death” process and is described by a system of Erlang differential equations, which allow one to obtain expressions for the limiting probabilities of the state of the system under consideration, called the Erlang formulas:

.

Having calculated all the probabilities of the states of the n-channel QS with failures p0, p1, p2, ..., pk, ..., pn, we can find the characteristics of the service system.

The probability of denial of service is determined by the probability that an incoming service request will find all n channels busy, the system will be in state Sn:

k=n.

In systems with failures, failure and maintenance events constitute a complete group of events, so:

Rothk+Robs=1

On this basis, the relative throughput is determined by the formula

Q \u003d Pobs \u003d 1-Rotk \u003d 1-Pn

The absolute throughput of the QS can be determined by the formula

A=L*Robs

The service probability, or the proportion of serviced requests, determines the relative throughput of the QS, which can also be determined by another formula:

From this expression, you can determine the average number of applications under service, or, what is the same, the average number of channels occupied by servicing

The channel occupancy rate is determined by the ratio of the average number of busy channels to their total number

The probability of channel occupancy by the service, which takes into account the average time of occupancy tload and idle time tpr of channels, is determined as follows:

From this expression, you can determine the average idle time of the channels

The average residence time of the application in the system in the steady state is determined by Little's formula

Tsmo \u003d nz / l.

1.6 Single-channel QS with limited queue length

In commercial activities, QS with waiting (queue) are more common.

Consider a simple single-channel QS with a limited queue, in which the number of places in the queue m is a fixed value. Consequently, an application that arrives at the moment when all places in the queue are occupied is not accepted for service, does not enter the queue, and leaves the system.

The graph of this QS is shown in Fig. 3.4 and coincides with the graph in Fig. 2.1 describing the process of "birth - death", with the difference that in the presence of only one channel.

The labeled graph of the process of "birth - death" of service, all intensities of service flows are equal

QS states can be represented as follows:

S0 - service channel is free,

S, - the service channel is busy, but there is no queue,

S2 - the service channel is busy, there is one request in the queue,

S3 - the service channel is busy, there are two requests in the queue,

Sm+1 - the service channel is busy, all m places in the queue are occupied, any next request is rejected.

To describe the random process of QS, one can use the previously stated rules and formulas. Let us write the expressions defining the limiting probabilities of the states:

The expression for p0 can be written in this case in a simpler way, using the fact that the denominator is a geometric progression with respect to p, then after the appropriate transformations we get:

c= (1- With)

This formula is valid for all p other than 1, but if p = 1, then p0 = 1/(m + 2), and all other probabilities are also equal to 1/(m + 2).

If we assume m = 0, then we pass from consideration of a single-channel QS with waiting to the already considered single-channel QS with denials of service.

Indeed, the expression for the marginal probability p0 in the case m = 0 has the form:

po \u003d m / (l + m)

And in the case of l \u003d m, it has the value p0 \u003d 1 / 2.

Let us define the main characteristics of a single-channel QS with waiting: the relative and absolute throughput, the probability of failure, as well as the average queue length and the average waiting time for an application in the queue.

The request is rejected if it arrives at the moment when the QS is already in the state Sm + 1 and, therefore, all places in the queue are occupied and one channel serves

Therefore, the probability of failure is determined by the probability of occurrence

Sm+1 states:

Potc = pm+1 = cm+1 * p0

The relative throughput, or the proportion of serviced requests arriving per unit of time, is determined by the expression

Q \u003d 1- potk \u003d 1- cm + 1 * p0

the absolute bandwidth is:

The average number of applications L standing in the service queue is determined by the mathematical expectation of the random variable k - the number of applications standing in the queue

the random variable k takes the following only integer values:

1 - there is one application in the queue,

2 - there are two applications in the queue,

t-all places in the queue are occupied

The probabilities of these values ​​are determined by the corresponding state probabilities, starting from the state S2. The distribution law of a discrete random variable k is depicted as follows:

Table 1. Law of distribution of a discrete random variable

The mathematical expectation of this random variable is:

Loch = 1* p2 +2* p3 +...+ m* pm+1

In the general case, for p ? 1, this sum can be transformed, using geometric progression models, to a more convenient form:

Loch = p2 * 1-pm * (m-m*p+1)*p0

In the particular case at p = 1, when all the probabilities pk turn out to be equal, one can use the expression for the sum of the terms of the number series

1+2+3+ m = m(m+1)

Then we get the formula

L "och \u003d m(m+1)* p0 = m(m+1)(p=1).

Applying similar reasoning and transformations, it can be shown that the average waiting time for servicing a request and a queue is determined by Little's formulas

Point \u003d Loch / A (at p? 1) and T1och \u003d L "och / A (at p \u003d 1).

Such a result, when it turns out that Tox ~ 1/l, may seem strange: with an increase in the intensity of the flow of requests, it seems that the queue length should increase and the average waiting time should decrease. However, it should be borne in mind that, firstly, the value of Loch is a function of l and m and, secondly, the QS under consideration has a limited queue length of no more than m applications.

A request that arrives at the QS at a time when all channels are busy is rejected, and, consequently, its “waiting” time in the QS is zero. This leads in the general case (for p? 1) to a decrease in Tochrostom l, since the proportion of such applications increases with the growth of l.

If we abandon the restriction on the length of the queue, i.e. aspire m--> >?, then cases p< 1 и р?1 начинают существенно различаться. Записанные выше формулы для вероятностей состояний преобразуются в случае р < 1 к виду

For sufficiently large k, the probability pk tends to zero. Therefore, the relative throughput will be Q \u003d 1, and the absolute throughput will be equal to A - l Q - l, therefore, all incoming requests are serviced, and the average queue length will be equal to:

Loch = p2 1-p

and the average waiting time according to Little's formula

Point \u003d Loch / A

In the limit p<< 1 получаем Точ = с / м т.е. среднее время ожидания быстро уменьшается с увеличением интенсивности потока обслуживания. В противном случае при р? 1 оказывается, что в СМО отсутствует установившийся режим. Обслуживание не успевает за потоком заявок, и очередь неограниченно растет со временем (при t >?). Therefore, the limiting probabilities of states cannot be determined: for Q= 1 they are equal to zero. In fact, the CMO does not fulfill its functions, since it is not able to service all incoming applications.

It is easy to determine that the proportion of serviced requests and the absolute throughput, respectively, average c and m, however, an unlimited increase in the queue, and hence the waiting time in it, leads to the fact that after a while, requests begin to accumulate in the queue for an unlimited time.

As one of the characteristics of the QS, the average time Tsmo of the stay of the application in the QS is used, including the average time spent in the queue and the average service time. This value is calculated by Little's formulas: if the queue length is limited, the average number of applications in the queue is equal to:

Lmo= m+1 ;2

tsmo= Lsmo; at p?1

And then the average residence time of the request in the queuing system (both in the queue and under service) is equal to:

tsmo= m+1 at p ?1 2m

1.7 Single-channel QS with unlimited queue

In commercial activities, for example, a commercial director is a single-channel QS with unlimited waiting, since he, as a rule, is forced to service applications of a different nature: documents, telephone conversations, meetings and conversations with subordinates, representatives of the tax inspectorate, police, commodity experts, marketers, product suppliers and solve problems in the commodity and financial sphere with a high degree of financial responsibility, which is associated with the obligatory fulfillment of requests that are sometimes eagerly awaiting the fulfillment of their requirements, and improper service errors are usually very tangible economically. Markov failure maintenance model

At the same time, goods imported for sale (service), while in the warehouse, form a queue for service (sale).

The length of the queue is the number of items to be sold. In this situation, sellers act as channels serving goods.

If the quantity of goods intended for sale is large, then in this case we are dealing with a typical case of QS with expectation.

Let us consider the simplest single-channel QS with service waiting, which receives a Poisson flow of requests with intensity l and service intensity λ.

Moreover, the request received at the moment when the channel is busy with servicing is queued and awaits servicing.

The labeled state graph of such a system is shown in fig. 3.5

The number of possible states of it is infinite:

The channel is free, there is no queue, ;

The channel is busy with service, there is no queue, ;

The channel is busy, one request in the queue, ;

The channel is busy, the application is in the queue.

Models for estimating the probability of states of a QS with an unlimited queue can be obtained from formulas isolated for a QS with an unlimited queue by passing to the limit when m>?:

It should be noted that for a QS with a limited queue length in the formula

there is a geometric progression with the first term 1 and the denominator.

Such a sequence is the sum of an infinite number of terms at.

This sum converges if the progression, infinitely decreasing at, which determines the steady-state operation of the QS, with at , the queue at over time can grow to infinity.

Since there is no limit on the queue length in the considered QS, then any application can be served, therefore, therefore, the relative throughput, respectively, and the absolute throughput

The probability of being in the queue for k applications is equal to:

Average number of applications in the queue -

Average number of applications in the system -

Average residence time of an application in the system -

Average residence time of an application with the system -

If in a single-channel QS with waiting, the intensity of receipt of requests is greater than the intensity of service, then the queue will constantly increase. In this regard, of greatest interest is the analysis of stable QS operating in a stationary mode at.

1.8 Multichannel QS with limited queue length

Let us consider a multi-channel QS, the input of which receives a Poisson flow of requests with intensity, and the service intensity of each channel is, the maximum possible number of places in the queue is limited by m. Discrete states of the QS are determined by the number of applications that have entered the system, which can be recorded.

All channels are free, ;

Only one channel is occupied (any), ;

Only two channels are occupied (any), ;

All channels are busy.

While the QS is in any of these states, there is no queue. After all service channels are busy, subsequent requests form a queue, thereby determining the further state of the system:

All channels are busy and one application is in the queue,

All channels are busy and two applications are in the queue,

All channels are occupied and all places in the queue are occupied,

The transition of the QS to a state with large numbers is determined by the flow of incoming requests with intensity, while, by condition, these requests are served by the same channels with the intensity of the service flow equal for each channel. In this case, the total intensity of the service flow increases with the connection of new channels up to such a state when all n channels are busy. With the advent of the queue, the service intensity increases more, since it has already reached the maximum value equal to.

Let us write expressions for the limiting probabilities of states:

The expression for can be transformed using the geometric progression formula for the sum of terms with a denominator:

The formation of a queue is possible when a newly received request finds no less than requirements in the system, i.e. when there will be requirements in the system.

These events are independent, so the probability that all channels are busy is equal to the sum of the respective probabilities

Therefore, the probability of forming a queue is equal to:

The probability of denial of service occurs when all channels and all places in the queue are occupied:

The relative throughput will be equal to:

Absolute bandwidth -

Average number of busy channels -

Average number of idle channels -

Occupancy (use) coefficient of channels -

Channel downtime ratio -

The average number of applications in queues -

If this formula takes a different form -

The average waiting time in a queue is given by Little's formulas -

The average residence time of an application in the QS, as for a single-channel QS, is greater than the average waiting time in the queue by the average service time, which is equal to, since the application is always served by only one channel:

1.9 Multi-channel QS with unlimited queue

Let us consider a multi-channel QS with waiting and an unlimited length of the queue, which receives a flow of requests with intensity and which has a service intensity of each channel.

The labeled state graph is shown in Figure 3.7. It has an infinite number of states:

S - all channels are free, k=0;

S - one channel is occupied, the rest are free, k=1;

S - two channels are occupied, the rest are free, k=2;

S - all n channels are occupied, k=n, there is no queue;

S - all n channels are occupied, one request is in the queue, k=n+1,

S - all n channels are occupied, r requests are in the queue, k=n+r,

We obtain the probabilities of states from the formulas for a multichannel QS with a limited queue when passing to the limit at m.

It should be noted that the sum of the geometric progression in the expression for p diverges at the load level p/n>1, the queue will increase indefinitely, and at p/n<1 ряд сходится, что определяет установившийся стационарный режим работы СМО.

no queue

Since there can be no denial of service in such systems, the throughput characteristics are:

average number of applications in the queue -

average waiting time in queue -

average number of applications in CMO -

The probability that the QS is in a state where there are no requests and no channel is occupied is determined by the expression

This probability determines the average fraction of service channel downtime. Probability of being busy with servicing k requests -

On this basis, it is possible to determine the probability, or the proportion of time that all channels are busy with the service

If all channels are already occupied by service, then the probability of the state is determined by the expression

The probability of being in the queue is equal to the probability of finding all channels already busy with service

The average number of requests in the queue and waiting for service is equal to:

The average waiting time for an application in the queue according to Little's formula:

and in the system

average number of channels occupied by service:

average number of free channels:

service channel occupancy rate:

It is important to note that the parameter characterizes the degree of coordination of the input flow, for example, customers in a store with the intensity of the service flow. The service process will be stable at If, however, the average queue length and the average waiting time for customers to start service will increase in the system and, therefore, the QS will work unstably.

1.10 QS modeling algorithm

The QS considered in the problem is a QS with:

Dual channel service;

A two-channel input stream (it has 2 inputs, one of which receives a random stream of Requests I, the other input receives a stream of Requests II).

Determining the times of receipt and service of applications:

· The times of receipt and service of requests are generated randomly with a given exponential distribution law;

· Intensity of receipt and service of requests are set;

The functioning of the considered QS:

Each channel serves one request at a time;

If at least one channel is free at the time a new request arrives, then the incoming request enters the service;

If there are no Applications, then the system is idle.

Service discipline:

Priority of Requests I: if the system is busy (both channels serve requests), and one of the channels is occupied by Request II, Request I preempts Request II; Application II leaves the system unserved;

If both channels are busy by the time Request II arrives, Request II is not served;

If by the moment of arrival of the Request I both channels serve the Requests I, the received Request I leaves the system unserved;

Modeling task: knowing the parameters of the input flows of applications, simulate the behavior of the system and calculate its main characteristics of its efficiency. By changing the value of T from smaller values ​​to large ones (the time interval during which a random process of receipt of applications of the 1st and 2nd streams in the QS for service takes place), one can find changes in the criterion of efficiency of functioning and choose the optimal one.

Criteria for the effectiveness of the functioning of the QS:

· Probability of failure;

· Relative throughput;

· Absolute throughput;

Modeling principle:

We introduce the initial conditions: the total time of the system, the values ​​of the intensities of the flows of applications; the number of implementations of the system;

We generate the moments of time at which requests arrive, the sequence of arrival of Requests I of Requests II, the service time of each incoming request;

We count how many applications were served, and how many were rejected;

We calculate the efficiency criterion of QS;

CHAPTER2 . PRACTICAL PART

Figure 1. Dependence of OPSS on time

PROGRAM CAN_SMO;

CHANNAL = (FREE, CLAIM1, CLAIM2);

INTENSITY = word;

STATISTICS = word;

CHANNAL1, CHANNAL2: CHANNAL;(Channels)

T_, t, tc1, tc2: TIME; (Time)

l1, l2, n1, n2: INTENSITY;(Intensities)

served1, not_served1,

served2, not_served2,

S: STATISTICS; (Statistics)

M,N:INTEGER;(number of implementations)

FUNCTION W(t: TIME; l: INTENSITY) : boolean;(Determines if an order has appeared)

Begin (by flow intensity l)

if random< l/60 then W:= TRUE else W:= FALSE;

FUNCTION F(t: TIME; n: INTENSITY) : TIME;(Determines how long the request will be processed)

Begin (according to the intensity of servicing requests n)

F:= t+round(60/(n));

Figure 2. The dependence of OPPS on time

WRITELN("ENTER THE NUMBER OF QS WORK IMPLEMENTATIONS");

writeln(M, "th implementation");

CHANNAL1:= FREE; CHANNAL2:= FREE;

l1:= 3; l2:= 1; n1:= 2; n2:= 1;

server1:= 0; not_served1:= 0;

server2:= 0; not_served2:= 0;

write("Enter QS study time - T: "); readln(_T_);

if CHANNAL1 = CLAIM1 then inc(served1) else inc(served2);

CHANNAL1:= FREE;

writeln("Channel1 completed the request");

if CHANNAL2 = CLAIM1 then inc(served1) else inc(served2);

CHANNAL2:= FREE;

writeln("Channel2 completed the request");

Figure 3. Graph of the probability of failure in the system from time to time

writeln("Request received1");

if CHANNAL1 = FREE then

begin CHANNAL1:= CLAIM1; tc1:= F(t,n1); writeln("Channel1 has received request1"); end

else if CHANNAL2 = FREE then

begin CHANNAL2:= CLAIM1; tc2:= F(t,n1); writeln("Channel2 accepted request1"); end

else if CHANNAL1 = CLAIM2 then

begin CHANNAL1:= CLAIM1; tc1:= F(t,n1); inc(not_served2); writeln("Channel1 accepted ticket1 instead of ticket2"); end

else if CHANNAL2 = CLAIM2 then

begin CHANNAL2:= CLAIM1; tc2:= F(t,n1); inc(not_served2); writeln("Channel2 accepted ticket1 instead of ticket2"); end

else begin inc(not_served1); writeln("request1 not served"); end;

Figure 4. Dependence of the number of applications on time

writeln("Request2 received");

if CHANNAL1 = FREE then

begin CHANNAL1:= CLAIM2; tc1:= F(t,n2); writeln("Channel1 has accepted request2");end

else if CHANNAL2 = FREE then

begin CHANNAL2:= CLAIM2; tc2:= F(t,n2); writeln("Channel2 accepted request2");end

else begin inc(not_served2); writeln("request2 not served"); end;

S:= served1 + not_served1 + served2 + not_served2;

writeln("QS operation time",_T_);

writeln("served by channel1: " ,served1);

writeln("served by channel2: ",served2);

writeln("Requests received: ",S);

writeln("Orders served: ",served1+served2);

writeln("No requests served: ",not_served1+not_served2);

(writeln("Intensity of requests entering the system: ",(served1+served2)/_T_:2:3);)

writeln("Absolute system throughput: ",(served1+served2)/T:2:3);

writeln("Probability of failure: ",(not_served1+not_served2)/S*100:2:1,"%");

writeln("Relative system throughput: ",(served1+served2)/S:2:3);

writeln("simulation finished");

Table 2. Results of the QS work

Characteristics of the QS

Hours of operation

Received applications

Applications served

Applications not served

Absolute System Throughput

Relative system throughput

CHAPTER 3SAFETY REGULATIONS

General provisions

· Persons who are familiar with the safety instructions and the rules of conduct are allowed to work in the computer class.

· In case of violation of the instructions, the student is suspended from work and is allowed to study only with the written permission of the teacher.

· Work of students in a computer class is allowed only in the presence of a teacher (engineer, laboratory assistant).

· Remember that each student is responsible for the condition of his workplace and the safety of the equipment placed on it.

Before starting work:

· Before starting work, make sure that there is no visible damage to the equipment and wires. Computers and peripherals should be placed on tables in a stable position.

· Students are strictly prohibited from getting inside the devices. You can turn on devices only with the permission of the teacher.

When working in a computer class, it is prohibited:

1. Entering and leaving the classroom without the permission of the teacher.

2. Being late for class.

3. To enter the classroom in dirty and wet shoes, dusty clothes, in the cold season in outerwear.

4. Work on the computer with wet hands.

5. Put foreign objects on the workplace.

6. Get up during work, turn around, talk to a neighbor.

7. Turn on and off the equipment without the permission of the teacher.

8. Violate the order of turning on and off the equipment.

9. Touch the keyboard and mouse when the computer is turned off, move furniture and equipment.

10. Touch the display screen, cables, connecting wires, connectors, plugs and sockets.

11. Approach the teacher's workplace without permission

The main threat to human health when working with a PC is the threat of electric shock. Therefore, it is prohibited:

1. Work on equipment that has visible defects. Open the system block.

2. Connect or disconnect cables, touch connectors of connecting cables, wires and sockets, grounding devices.

3. Touch the screen and the back of the monitor, keyboard.

4. Try to troubleshoot the equipment on your own.

5. Work with wet clothes and wet hands

6. Fulfill the requirements of the teacher and laboratory assistant; Maintain silence and order;

7. While online, work only under your own name and password;

8. Observe the mode of operation (according to the Sanitary Rules and Regulations);

9. Start and finish work only with the permission of the teacher.

10. In case of a sharp deterioration in health (the appearance of pain in the eyes, a sharp deterioration in visibility, the inability to focus or focus on sharpness, pain in the fingers and hands, increased heart rate), immediately leave the workplace, report the incident to the teacher and consult a doctor;

11. Keep the workplace clean.

12. Finish the work with the permission of the teacher.

13. Hand over completed work.

14. Quit all active programs and gracefully shut down the computer.

15. Put the workplace in order.

16. To the duty officer to check the readiness of the office for the next lesson.

During the operation of the equipment it is necessary to beware of: - electric shock;

- mechanical damage, trauma

In case of emergencies:

1. If sparking, a burning smell or other problems are detected, stop work immediately and inform the teacher about it.

2. If someone is struck by an electric current, it is necessary: ​​stop working and move to a safe distance; turn off the voltage (on the switchboard of the cabinet); inform the teacher start first aid and call a doctor.

3. In case of fire, it is necessary to: stop work and start evacuation; inform the teacher and call the fire brigade (tel. 01); turn off the voltage (on the switchboard of the cabinet); start extinguishing the fire with a fire extinguisher (it is forbidden to extinguish the fire with water.

Similar Documents

Mathematical theory of queuing as a branch of the theory of random processes. Queuing systems for applications arriving at intervals. Open Markov network, its non-Markovian case, finding stationary probabilities.

term paper, added 09/07/2009


The concept of a queuing system, its essence and features. Queuing theory as one of the sections of probability theory, the issues under consideration. The concept and characteristics of a random process, its types and models. Service with expectation.

term paper, added 02/15/2009


Optimization of customer flow control in queuing networks. Methods for establishing dependencies between the nature of requirements, the number of service channels, their productivity and efficiency. graph theory; Kolmogorov equation, event flows.

test, added 07/01/2015


Queuing theory is an area of ​​applied mathematics that analyzes processes in production systems in which homogeneous events are repeated many times. Determination of the parameters of the queuing system with unchanged characteristics.

term paper, added 01/08/2009


Definition of a random process and its characteristics. Basic concepts of queuing theory. The concept of a Markov random process. Event streams. Kolmogorov's equations. Limit probabilities of states. The processes of death and reproduction.

abstract, added 01/08/2013


Stationary probability distribution. Construction of mathematical models, graphs of transitions. Obtaining an equilibrium equation for queuing systems with a different number of servers, different types of requirements, and limited queues at the servers.

thesis, added 12/23/2012


Analysis of the effectiveness of the simplest queuing systems, calculation of their technical and economic indicators. Comparison of system performance with failures with a corresponding mixed system. Advantages of transition to a system with mixed properties.

term paper, added 02/25/2012


Drawing up a simulation model and calculating the performance indicators of the queuing system according to the given parameters. Comparison of performance indicators with those obtained by numerical solution of the Kolmogorov equations for the probabilities of the system states.

term paper, added 12/17/2009


Examples of the processes of reproduction and death in the case of the simplest queuing systems. Mathematical expectation for a queuing system. Additional flow and an infinite number of devices. System with a limit on the time of stay of the application.

term paper, added 01/26/2014


Some mathematical problems in the theory of maintenance of complex systems. Organization of service with limited information about the reliability of the system. Algorithms for fail-safe operation of the system and finding the time for planned preventive maintenance of systems.