input stream. Typical mathematical models

24. Incoming demand flow

24.1 Structure of the QS

The study of QS begins with the analysis of the incoming flow of requirements. Incoming demand flow is a set of requirements that enter the system and need to be serviced. The incoming flow of requirements is studied in order to establish the patterns of this flow and further improve the quality of service.

In most cases, the incoming flow is uncontrollable and depends on a number of random factors. The number of requests arriving per unit of time, a random variable. A random variable is also the time interval between adjacent incoming requests. However, the average number of requests received per unit of time and the average time interval between neighboring incoming requests are assumed to be given.

The average number of customers entering the queuing system per unit of time is called demand intensity and is determined by the following relation:

where T - the average value of the interval between the arrival of successive requests.

For many real processes, the flow of requirements is described quite well by the Poisson distribution law. Such a flow is called the simplest.

The simplest flow has the following important properties:

Stationarity property, which expresses the invariance of the probabilistic flow regime over time. This means that the number of customers entering the system at regular intervals must be constant on average. For example, the number of wagons arriving for loading on average per day should be the same for different time periods, for example, at the beginning and at the end of a decade.

no aftereffect, which determines the mutual independence of the receipt of one or another number of requests for service in non-overlapping time intervals. This means that the number of requests arriving in a given time interval does not depend on the number of requests served in the previous time interval. For example, the number of cars that arrived for materials on the tenth day of the month does not depend on the number of cars serviced on the fourth or any other previous day of that month.

property of ordinariness, which expresses the practical impossibility of the simultaneous receipt of two or more requirements (the probability of such an event is immeasurably small in relation to the considered period of time, when the latter tends to zero).

Since the purpose of the operation of any service system is to satisfy applications (requirements) for service, the flow of applications (requirements) is one of the basic and most important concepts of the theory queuing. You need to learn how to quantify the incoming flow of requirements, but for this you need to find out its nature and structure.

Almost any flow of requirements entering the service system is a random process. Indeed, if we take t=0 per initial moment, then in many flows (except for the case when the requirements arrive strictly on schedule) it is either impossible or rather difficult to accurately predict the moment of arrival of the next requirement, as well as the moments of arrival of subsequent requirements. For example, it is impossible to accurately indicate the moments when clients arrive at the studio, patients at the hospital, calls arrive at the PBX, equipment at the repair shop, etc.

Consequently, the moments of receipt of applications, as well as the intervals between them, are, generally speaking, independent random variables. Then the process of receipt of requirements in the queuing system should be considered as a probabilistic or random process. Let's denote this process as X(t). This function determines the number of requests received by the system during a period of time . For every fixed t, the function X(t) is a random variable. Indeed, if we choose time intervals even of the same duration, then in this case one cannot be sure that the same number of requirements will arrive in each of these intervals.

For a period of time there may not be a single application, or there may be 1, 2, ... applications. But no matter how long the time intervals we choose, the number of applications will be only an integer.

The flow of requirements can be represented as a graph of one of the implementations of the random variable of the function X(t), take only non-negative integer values. In this case, the graph (Fig. 24.2) is a stepped line with jumps equal to either one or several units, depending on whether the requirements arrive one at a time or in groups. So the random process X(t), has the following features.

1. For every fixed t function X(t), takes non-negative integer values ​​0, 1, 2,...,R,... and does not decrease with increasing.

2. The number of claims received during the period of time , depends on the length of this interval, i.e., on the value of t.

3. Process implementations are stepped lines, somewhat different from one another. It is known from the theory of random processes that a process will be completely determined from a probabilistic point of view if all its multidimensional distribution laws are known:

However, finding such a function in the general case is a very difficult and sometimes unsolvable problem. Therefore, in practice, they try to use processes that have properties that make it possible to find simpler ways to describe them. These properties include:

Stationarity (better uniformity in time);

Lack of aftereffect (Markovian), sometimes they say about the absence of memory;

Ordinariness.

The listed properties were considered above in the study of stationary and Markov processes, so here we only recall the essence of these properties in terms of queuing theory.

The flow of requirements is called stationary or homogeneous in time if the probability of receipt of a certain number of requirements during a certain period of time depends only on the length of the interval, and not on its time position (in other words, does not depend on the origin). Thus, for a stationary flow, the probability that over the interval will do exactly R requirements is equal to the probability of receipt R requirements for the interval [a, a +t] , where a>0, i.e.

This means that the probabilistic characteristics of the flow (parameters of the distribution law) should not change in time.

Many real demand flows have the stationarity property when viewed over short periods. Such flows include: the flow of calls to the PBX at certain intervals, the flow of customers to the store, the flow of radio equipment in need of repair, the intensity of passenger traffic, etc. However, some of the listed flows change during the day (probability of calls at night less than during the day, peak hours in public transport).

In some flows, the number of requests that entered the system after an arbitrary moment of time does not depend on the number of previously received requests and the moments of their arrival, i.e., the intervals between the arrivals of requests are considered independent values ​​and there is no connection between them. The future state of the system does not depend on its past state. A flow with this property is called a flow without aftereffect or a Markov flow. The property of no aftereffect (lack of memory) is inherent in many real threads. For example, the flow of calls to the PBX is a flow without aftereffect, since, as a rule, the next call comes regardless of when and how many calls have been made up to this moment.

In a number of cases, the nature of the flow of requirements is such that the simultaneous appearance of two or more requirements is impossible or nearly impossible. A stream with this property is called an ordinary stream.

If a R R >2 (h) -probability of occurrence for the interval h more than one requirement, then for an ordinary flow it should be:

,

i.e., the ordinariness of the flow requires that the probability of occurrences of more than one requirement in a small period of time h would be an infinitesimal quantity of a higher order than h. In some real flows this property is obvious, while in others we accept it with a fairly good approximation to reality. Classical examples of such a flow are the flow of calls to the PBX and the flow of customers in the studio.

A request flow that has these three properties is called the simplest. It can be shown that any simple flow is described by a Poisson process. To this end, we recall the definition of the Poisson process adopted in the theory of random functions.

random process X(t) (0≤ t<∞) integer values ​​is called a Poisson process if it is a process with independent increments or if any increment of the process over a time interval h is distributed according to the Poisson law with parameter λ h, where λ>0 those.

In particular, if t=0, X(0)=0, then (3) is rewritten as follows:

(4)

Here V r (h) means the probability that the event of interest to us will occur exactly R once in a period of time h(in terms of queuing theory V r (h) determines the probability that over a period of time h will enter the service system exactly R requirements).

Meaning of the parameter X it is easy to find out if you find the mathematical expectation of the Poisson process: M [X(t)]=M. At t=1 we get M[X(1)]=1. Therefore, there is an average number of applications per unit of time. Therefore, the value λ often referred to as intensity or flux density.

From the definition of the Poisson process, three properties immediately follow, identical to those above:

1) Independence of increments. In the independence of increments for the Poisson process, there is no aftereffect - the Markov process.

2) Uniformity in time. This means that the probabilities V r (h) do not depend on the initial moment t considered interval , but depend only on the length of the interval h:

3) Ordinariness. Ordinariness of the Poisson process means that it is practically impossible for a group of requirements to arrive at the same moment.

So, the simultaneous receipt of two or more claims in a small time interval h is unlikely, therefore

which indicates the ordinariness of the Poisson process.

Thus, we have established that the flow described by the Poisson process is the simplest. However, the converse assumption is also true, that the simplest flow is described by a Poisson process. As a result, the simplest flow is often also called the Poisson flow. The Poisson process in the theory of queuing occupies a special place, similar to that in the theory of probability, among other distribution laws, the normal law occupies. And the point is not that it is described mathematically most simply, but that it is the most common. The Poisson flow is a limit flow (an asymptotic flow when a large number of other flows are combined).

Definition 6.1. The input stream is called the simplest if:

1) the probability of the appearance of one or another number of applications in the time interval depends only on its duration and does not depend on its location on the time axis (stationarity of the input stream), moreover, applications arrive singly (ordinarity of the input stream) and independently of each other (no aftereffect in input stream);

2) the probability of the realization of a separate random event (appearance of an application) on a time interval of short duration is proportional to an infinitesimal higher order of smallness compared to i.e. is where

3) the probability of the realization of two or more random events (the appearance of two or more applications) on a short time interval is the value

The absence of aftereffect in the definition of the simplest input stream means that for any non-overlapping time intervals, the number of requests arriving in one of these intervals does not depend on the number of requests arriving in other intervals.

Despite the fact that the input and output streams of many real systems services do not fully satisfy the definition of the simplest flow, the concept of the simplest flow is widely used in the theory of queuing. This circumstance is connected not only with the fact that the simplest flows are quite often encountered in practice, but also with the fact that the sum of an unlimited number of stationary ordinary flows with almost any aftereffect is the simplest flow. In this regard, let us consider the main properties of the simplest flow.

Theorem 6.1. A discrete random variable that takes values ​​and characterizes, for the simplest input flow, the number of customers entering the queuing system on a time interval of duration t, is distributed according to the Poisson law with the parameter

Consider a scalar random process with discrete states (that is, for any fixed moment of time, its cross section ) is a discrete random variable with a set of possible values. Let its being in a state mean that there are k requests in the service system.

In accordance with the conditions of the theorem and the definition of the simplest flow, the random process , is a Markov homogeneous process with discrete states, and for any non-negative integers i and j, the probability density of the transition of the queuing system from the state , to the state at any time is determined by the equality

Therefore, in this case, the Kolmogorov system of equations has the following form:

where is the probability that, on a time interval of duration t, the service system under study will receive a number of requests. And since it follows from Definition 6.1 of the simplest flow of requests that

then we arrive at Cauchy problems with respect to the function

and functions

Sequentially solving the Cauchy problems (6.3), (6.4), in the case of the simplest input flow, we find the probability that the number of customers on a time interval of duration t will be equal to

Relations (6.5) mean that the random variable is distributed according to the Poisson law with the parameter

Corollary 6.1. If the input stream is the simplest, then the average number of customers entering the queuing system on a time interval of duration t is equal to

To determine the average number of applications, you need to find the mathematical expectation of a random variable. And since, according to (6.5), it is distributed according to the Poisson law with the parameter then

According to the proved corollary, the parameter Λ is the average number of applications arriving per unit of time. Therefore, it is called the intensity, or the density of the simplest flow.

Corollary 6.2. If the input stream of requests is the simplest, then the variance of a scalar random variable characterizing the dispersion of the number of requests entering the queuing system over a time interval of duration t, relative to their average value, is equal to

M If the input stream is the simplest, then, according to (6.5), the random variable is distributed according to the Poisson law with the parameter Therefore,

Let us pay attention to the fact that, according to (6.6) and (6.7), a random variable distributed according to the Poisson law has the same expectation and variance.

Example 6.1. The service bureau receives an average of 12 orders per hour. Considering the flow of orders to be the simplest, we determine the probability that: a) no orders will be received in 1 minute; b) no more than three orders will be received in 10 minutes.

Since the flow of orders is the simplest and the intensity, then, according to (6.5), we have:

In accordance with the definition 6.1 of the simplest flow, the duration of the time interval between two successively arriving requests is a random variable. To build mathematical models of queuing systems, it is necessary to know the distribution function of a random variable or its distribution density (probabilities)

Theorem 6.2. In the case of the simplest input flow with intensity A, the duration of the time interval between two consecutive requests has an exponential distribution with parameter A.

Input stream of information

The input stream of information is a sequence of documents and data coming to be entered into the information system.

See also: Information content

• - a device at the input of the system that converts input signals to coordinate the operation of the system with an external source. impact...

  Big encyclopedic polytechnic dictionary

• - a way signal protecting the way of a separate point. As V. with. traffic lights or semaphores may be used. The entrance semaphore is installed no closer than 50 m, the traffic light is no closer than 15 m from the wit of the input arrow ...

  Technical railway dictionary

• - "... Control of the supplier's products received by the consumer or customer and intended for use in the manufacture, repair or operation of products ..." Source: Order of Roskartografii dated 29.06 ...

  Official terminology

• - control of compliance with passport data of industrial products supplied for construction...

  Construction dictionary

• - the material flow entering the logistics system from the outside ...

  Glossary of business terms

• - a document drawn up in a specific form and containing data intended for entry into an information system. See also: Content  ...

  Financial vocabulary

• - a set of messages circulating in the system, necessary for the implementation of management processes ...

  Big Economic Dictionary

• - external material flow entering this logistics system from the external environment ...

  Big Economic Dictionary

• - a device at the input of a system or device that converts input actions into signals that are convenient for further processing, transmission and registration or for coordinating the operation of systems with different inputs -...

  Great Soviet Encyclopedia

• - ...

  Antonym Dictionary

• - INPUT, see enter and...

  Explanatory dictionary of Ozhegov

• - INPUT, input, input. adj. to the entrance. Entrance door. Entrance ticket. Inlet...

  Explanatory Dictionary of Ushakov

• - input I adj. initial, initial, initial. II adj. 1. Giving the right to enter 1. somewhere. 2. Serving as an entrance...

  Explanatory Dictionary of Efremova

• - input adj., use. comp. often 1. When you talk about a door, you mean the outside door leading into your house from the street. Someone stepped into the hallway and opened the front door. 2...

  Dictionary of Dmitriev

• - input "...

  Russian spelling dictionary

• - ...

  Word forms

"Input stream of information" in books

The flow of information in nature

author

The flow of information in nature

From the book Anthropology and Concepts of Biology author Kurchanov Nikolai Anatolievich

The flow of information in nature How is genetic information rewritten in a DNA cell? RNA? protein determines the flow of information in wildlife. This flow of information is realized in the vast majority of living systems. He got the definition of central dogma

"Input" VAT

From the book How to use "simplified" author Kurbangaleeva Oksana Alekseevna

"Input" VAT When purchasing a fixed asset, the purchasing organization pays its cost including value added tax. However, an enterprise applying the simplified taxation system cannot reimburse the amount of “input” VAT from the budget. This amount

Stop the flow of harmful information

From the book Why do princesses bite. How to understand and educate girls author Biddulph Steve

Stop the flow of harmful information Although we hate to admit it, we humans are essentially herd animals. We constantly seek recognition from others and constantly imitate those around us, trying to conform to some generally accepted norm; in our time

The flow of information coming from Africa about various forms of fossil man makes us take a fresh look at the process of isolating the most ancient human ancestors from the animal world and at the main stages of the formation of mankind.

From the book Ancient Civilizations author Bongard-Levin Grigory Maksimovich

The flow of information from Africa about various forms Fossil man makes us take a fresh look at the process of isolating the most ancient human ancestors from the animal world and at the main stages of the formation of mankind. The clarification of many problems contributes to

Input Converter

From the book Great Soviet Encyclopedia (VX) of the author TSB

Information flow for getint()

From the book The C Language - A Beginner's Guide author Prata Stephen

Information flow for getint() What output should our function have? First, there is no doubt that it would have to return the value of the number read. Of course, the scanf() function already does this. Secondly, and this is very important, we are going to create a function that

Consciousness is a flow of energy and information

From the book Mindsight. The New Science of Personal Transformation by Siegel Daniel

Consciousness is the flow of energy and information Energy is the ability to perform an action, such as moving limbs or forming thoughts. Physics explores it different kinds. We feel radiant energy while sitting in the sun, kinetic energy while walking on the beach or swimming,

Information flow

From the book Collection of short stories and novels the author Lukin Evgeny

The flow of information Immediately, as soon as Valery Mikhailovich Akhlomov appeared on the threshold of the editorial sector, it became clear that at the planning meeting he was hit hard by the main one. - Use the kindness of my character! he said in quiet fury. - The mind is incomprehensible: in

Chapter 2 DIPLOMACY OF CULTURAL IMPERIALISM AND THE FREE FLOW OF INFORMATION

From the author's book

CHAPTER 2 DIPLOMACY OF CULTURAL IMPERIALISM AND THE FREE FLOW OF INFORMATION For a quarter of a century, one doctrine—the idea that no barriers should impede the flow of information between countries—has dominated international thinking about communications and

The flow of information and your personal philosophy

From the book Think and Do! author Baranovsky Sergey Valerievich

The flow of information and your personal philosophy Our age is good if only because it contains a lot of information. The Internet alone opens hundreds of new doors for us. Do not listen to those who call the Network garbage! The Internet is not a dump, but a badly cleaned library. Tens of thousands of diverse

author Gosstandart of Russia

From the book SOFTWARE OF EMBEDDED SYSTEMS. General requirements to development and documentation author Gosstandart of Russia

5.1 Flow of information between system and software life cycle processes

From the book SOFTWARE OF EMBEDDED SYSTEMS. General requirements for development and documentation author Gosstandart of Russia

5.1 Information flow between processes life cycle systems and software 5.1.1 Information flow from system processes to software processes The system safety assessment process should identify possible failure situations for the system and establish their categories,

12.37 Software input/output information guide

From the book SOFTWARE OF EMBEDDED SYSTEMS. General requirements for development and documentation author Gosstandart of Russia

12.37 Software input/output information input/output information manual The software explains to the user how to present, enter input information and how to interpret output information, in what mode (batch or interactive) the system operates

Elements of queuing theory

§ 1. Introduction

The queuing theory is otherwise known as Queuing Theory. Indeed, queuing theory is largely devoted to the study of queues that arise in various systems.

The main characteristics of queuing systems are the following random variables:

average time a customer spends in a queue;

the percentage of time the system is idle (due to a lack of clients).

The functionality of queuing systems is determined by the following factors:

distribution of customer distribution moments;

service duration distribution;

service system configuration (serial, parallel or parallel-serial service);

discipline in the queue (service in the order of arrival, service in the reverse order, random selection of customers);

waiting block capacity (limited or unlimited);

capacity or power of the demand source (limited and unlimited);

some other characteristics of the system (the ability of clients to move from one queue to another, non-zero probability of failure, etc.).

The main factors are the first two.

Any queuing system consists of the following main elements:

incoming customer flow;

service device;

discipline in line.

§ 2 . Customer input stream

Consider sequences of random variables

Let's pretend that t o = 0 is the initial moment of the system operation; t 1 = t o + τ 1 , t 2 = t 1 + τ 2 , …, t k = t k -1 + τ k , …., where τ k are independent random variables with exponential distribution with parameter λ.

W here t 1 - the moment of arrival of the first client, τ 1 - the time interval between the start of the system and the arrival of the first client, τ 2 - the time interval between the arrival of the first and second clients, etc.

Subsequence
, defined in the above way is called the simplest (Poisson) flow. A constant is called the parameter of the simplest flow.

Properties of a simple stream

1. Flow shift by T

Let there be a simple flow
with parameter λ.

By shifting the flow by T, we get the stream
, which will also be the simplest flow with the same parameter λ. For example, if T is between and , then the new stream looks like this:

, ….

2. Merging two threads

P
Let there be two independent elementary flows

With
parameters λ (1) , λ (2) respectively. We will say that the flow was formed as a result of the merger of two flows, if the set ( t k) is the union of the sets ( t k (1) }, {t k ( 2) ) and elements of the set ( t k) are sorted in ascending order.

P
the outflow resulting from the merger of two independent elementary flows is also the elementary flow with the parameter λ = λ(1) + λ(2) , where λ(j)– flow parameter

3. Splitting the simplest stream

Let there be a simple flow with a parameter λ,

and a sequence of independent random variables
, taking two values:

P(ξ i = 1) = p, P(ξ i = 0) = q, p  0, q  0, p + q = 1.

Such random variables are called Bernoulli(with parameter p). Flow splitting procedure ( t k) is as follows: number t i refer to the first flow if ξ i= 1; if ξ i= 0, then the number t i refer to the second stream. We call such an operation of splitting a stream into two Bernoulli(with parameter p).

The flows obtained as a result of the Bernoulli separation of the simplest flow are independent simplest flows with parameters λ (1) = λp, λ (2) = λq, respectively.

Note that proofs of these properties of the simplest flow can be found in .

H
herez X(t) In what follows, we will denote the number of clients in the system at the moment t, i.e.

Properties of Poisson Processes

Poisson process increment is homogeneous.

Denote by X((a,b])= X(b) – X(a) process increment, which can be interpreted as the number of clients entering the system in the interval ( a,b]. Homogeneity means the fulfillment of the condition:

P( X((a,b]) = k) = P( X((0,b-a]) = k) = P( X(b-a) = k),

those. the probability distribution of the number of clients entering the system in the interval ( a,b], depends only on the length of this interval.

Poisson process increments are independent.

Consider the interval (0, b] and suppose that it is divided into non-intersecting intervals (0, b 1 ], (b 1 , b 2 ], , ( b N-1, b N]. Let b 0 = 0. Then X((b 0 , b 1 ]), X((b 1 , b 2]), , X((b N-1, b N ]) is the number of clients entering the system in the corresponding time periods. These quantities are independent, i.e.

P( X((b 0 , b 1 ]) = i 1 , , X((b N-1, b N ]) = i N) =

P( X((b 0 , b 1 ]) = i 1)  P( X((b N-1, b N ]) = i N).

Evidence for these properties can be found in .

Tasks for § 2.

2.1. There are two random variables  1 and  2. They are independent and have an exponential distribution with parameters  1 and  2 respectively. We introduce the following random variable:  = min(  1 ,  2). Prove that this quantity has an exponential distribution with parameter = 1 + 2 .

2.2. Given two independent random variables  1 and  2 having a Poisson distribution with parameter  1 and  2 respectively. Let the random variable  = 1 + 2. Prove that this quantity has a Poisson distribution with parameter  = 1 + 2 .

2.3. Let  is the number of customers in stores and has a Poisson distribution with the parameter  . Let each client with probability p makes a purchase in this store. It is required to prove that the number of customers who made a purchase in this store has a Poisson distribution with the parameter p.

2.4. Customers come to the restaurant according to the Poisson flow with an average frequency of 20 customers per hour. The restaurant opens at 11.00.

a) the probability that at 11.12 there will be 20 customers in the restaurant, given that at 11.07 there were 18 customers in the restaurant;

b) the probability that a new visitor will arrive at the restaurant between 11.28 and 11.30, if it is known that the previous visitor arrived at the restaurant at 11.25.

2.5. Products are taken from a warehouse with a capacity of 80 items in stock, in accordance with the Poisson flow at a rate of 5 items per day.

a) the probability that during the first two days 10 units of products will be taken from the warehouse;

b) the probability that by the end of the fourth day there will not be a single unit of product left in the warehouse.

§

3. The process of death and reproduction

Let's build the process of death and reproduction X(t) "constructively".

Consider two sequences and. The first one is responsible for the entry of clients into the system (reproduction), and the second one is for servicing clients (death):

In addition, let two independent sequences be given
independent random variables with exponential distribution with parameter =1.

Process X(t) is constructed as follows. Let
, where
. Then on the interval
process X(t) will keep its value , where
,

.

In the moment t 1 process value X(t) will either increase or decrease by one according to which of the two moments
comes before:

We have thus put the meaning of the process X(t) at the point t 1 equal ; then the evolution of the process X(t) on the interval
, where
and
, obeys the same law: X(t) does not change on this interval at the moment t 2

incremented by one if
, and decreases by one otherwise.

If
, then the value of the process X(t) increases by one at a random moment
.

The process built in this way
, is called a time-uniform process of death and reproduction; its distributions are completely determined by the set of parameters, and the initial distribution X(0):

It is convenient to use the following diagram to represent process development X(t):

The arrows above correspond to the dynamics of the reproduction process: from i th state, the process goes to ( i+1)-th state with intensity ; the arrows below correspond to the dynamics of the death process: with intensity process from i th state goes to ( i-1)-th state.

Feature set

describes the process distribution X(t); below we present a system of equations that these functions satisfy.

Note that not every set of parameters
responds to a "non-degenerate" process X(t); the fact is that if the numbers grow very quickly at
, then the process X(t) at the final moment t can "explode", i.e. with a positive probability to exceed any level and increase to
. This is how, for example, a population of bacteria in favorable environment. The processes describing the chemical reactions leading to an explosion are similarly arranged.

Processes X(t), for which all
, belong to the so-called pure breeding processes. Processes for which
, called processes of pure death.

The following lemma gives necessary and sufficient conditions on the parameters
, which guarantee the finiteness of the process of pure reproduction
with parameters.

Lemma. Let the process of pure reproduction with parameters . Then for the finiteness of the process it is necessary and sufficient that the series diverges

Let X(t) the process of death and reproduction with the same parameters process , as well as the parameters
. It's obvious that

P( X(t)  )  P( X + (t)  ) .

Therefore, we obtain a corollary from the lemma.

Consequence. If for an arbitrary process of death of reproduction X(t) the condition
, then for any
fair P( X(t)  ) = 1, i.e. the process is finished.

The proof of the lemma can be found in .

Tasks for § 3

3.1. Consider the process of death and reproduction, for which

It is required to draw a diagram corresponding to this process.

3.2. Let the customers who want to get help by phone form the simplest flow with the parameter . Let every conversation last - indicative time. Let X(t) is the number of clients in the system at time t. Draw a diagram corresponding to the process X(t).

3.3. Let under the conditions of problem 3.2

the phone has a memory for one client: if the client calls and the phone is busy, but the phone memory is free, then the machine offers to hang up and wait for a call. When the phone is free, the bell will ring;

there is an automatic switch and two telephones, each telephone has its own operator: if at the time of the client's call there is a free telephone, the switch automatically addresses the client to this telephone;

the switch (see item 2)) has memory for one client;

each phone (see item 2)) has a memory for one client.

For all of the above cases, draw a diagram corresponding to the process X(t).

3.4. Determine whether the final processes of pure reproduction are with the following reproduction rates:

a)  k =k +  ,  >0,  >0, k= 0, 1, ...

b)  0 = 1,  k +1 = (k+1) k , k = 0, 1, ...

in)  k =  k , k = 0, 1, ...  > 0.

§ 4. Differential equations corresponding to the process of death and reproduction

Let's pretend that X(t) is the process of death and reproduction with characteristics and. Let for some finite numbers A and B there are inequalities  i  A + Bi, i= 0, 1, ...This condition guarantees the end of the process X(t). In this case, we will agree that the upper arrow on the left comes to each state (even to state 0), while the birth rate λ may be equal to zero (for example, λ –1 = = 0); from each state there is a bottom arrow to the left, and the intensity of death μ can also be zero (for example, λ –1 = 0). Extending the definition of the diagram in this way does not change the essence of the matter, however, it will be useful in further reasoning. Consider a diagram corresponding to our process X(t):

Denote, as before, by

P k (t) = P(X(t) = k), k = 0,1,…,

the probability that at a given moment t number of clients X(t) will be equal to k.

Theorem 1.CharacteristicsprocessX(t), defined above, satisfies the following system of differential equations

where k = 0,1,…, and initial conditions

It is not out of place to explain that the first line (when k= 0) system of equations (1) has the form

Proof. Denote by P k ( t +Δ) = P(X(t+ Δ) = k).

Let's use the definition of the derivative of a function of one variable:

.

Consider these events:

A 0 (t, Δ) = (on the interval [ t, t+Δ] process X(t) did not make a single jump);

A 1 (t, Δ) = (on the interval [ t, t+Δ] process X(t) made exactly one jump);

A 2 (t, Δ) = (on the interval [ t, t+Δ] process X(t) made two jumps or more).

Then it is obvious that

Denote further by

; through
three exponential random variables with parameters
. Let all these quantities be independent. Then true Then it is obvious that the stationary (steady) mode. P k (t) = P(in the system at the moment t located k clients).

Find the solution to the system of differential equations, as well as the stationary probabilities.

4.2. For the processes of death and reproduction from problem 3.3 write out differential equations relating the probabilities P k (t) = P(in the system at the moment t located k clients).

Find stationary probabilities.

The main task of the TSMO is to establish the relationship between the nature of the flow of applications at the entrance of the QS, the performance of one channel, the number of channels and the efficiency of service.

Various functions and quantities can be used as an efficiency criterion:

• average system downtime;
• average waiting time in the queue;
• the law of distribution of the duration of waiting for a requirement in the queue;
• average % of applications rejected; etc.

The choice of criterion depends on the type of system. For example, for systems with failures the main characteristic is the absolute throughput CMO; less important criteria are the number of busy channels, the average relative idle time of one channel and the system as a whole. For lossless systems(with unlimited waiting) the most important are the average idle time in the queue, the average number of requests in the queue, the average residence time of the requests in the system, the idle factor and the load factor of the serving system.

Modern TSMO is a set of analytical methods for studying the listed types of QS. In what follows, of all rather complex and interesting methods for solving queuing problems, methods described in the class of Markov processes of the “death and reproduction” type will be presented. This is due to the fact that these methods are most often used in the practice of engineering calculations.

2. Mathematical models of event flows.

2.1. Regular and random streams.

One of the central questions of the QS organization is the elucidation of the regularities that govern the moments when service requirements enter the system. Consider the most used mathematical models input streams.

Definition: The flow of requirements is called homogeneous if it satisfies the following conditions:

1. all applications of the flow are equal in terms of service;

instead of the requirements (events) of the flow, which by their nature can be different, only at the time of their arrival.

Definition: A stream is called regular if the events in the stream follow one after the other at strict time intervals.

Function f (x) of the probability distribution density of the random variable T - the time interval between events has the form:

Where - delta function, M t - mathematical expectation, and M t \u003d T, variance Dm = 0 and the intensity of the occurrence of events in the flow \u003d 1 / M t \u003d 1 / T.

Definition: The flow is called random if its events occur at random times.

A random flow can be described as a random vector, which, as is known, can be uniquely defined by the distribution law in two ways:

Where, zi- values ​​Ti(i=1,n),In this case, the moments of occurrence of events can be calculated as follows

t 1 \u003d t 0 +z1

t 2 \u003d t 1 +z2

………,

where, t 0 - the moment of the beginning of the flow.

2.2. The simplest Poisson flow.

To solve a large number of applied problems, it is sufficient to apply mathematical models of homogeneous flows that satisfy the requirements of stationarity, without aftereffect and ordinariness.

Definition: A flow is said to be stationary if the probability of occurrence nevents on the time interval (t,t + T) depends on its location on the time axis t.

Definition: A stream of events is called ordinary if the probability of the occurrence of two or more events during an elementary time interval D tis an infinitesimal value compared to the probability of occurrence of one event in this interval, i.e. at n=2.3,…

Definition: The stream of events is called flow without consequences, if for any non-overlapping time intervals the number of events falling on one of them does not depend on the number of events falling on the other.

Definition: If the flow satisfies the requirements of stationarity, ordinariness and without consequences, it is called the simplest Poisson flow.

It is proved that for the simplest flow the number nevents falling on any interval zdistributed according to Poisson's law:

(1)

The probability that no event will appear on the time interval z is equal to:

(2)

then the probability of the opposite event is:

where by definition P(T is the probability distribution function T.From here we get that the random variable T is distributed according to the exponential law:

(3)

parameter is called flux density. Moreover,

For the first time, the description of the simplest flow model appeared in the works of outstanding physicists of the beginning of the century - A. Einstein and Yu. Smolukhovsky, devoted to Brownian motion.

2.3. Properties of the simplest Poisson flow.

There are two properties of the simplest flow that can be used in solving practical problems.

2.3.1. We introduce the quantity a= X. In accordance with the properties of the Poisson distribution forit tends to be normal. Therefore, for large a, to calculate P(X(a) is less than or equal to n), where X(a) is a Poisson random variable with expectation a, you can use the following approximate equality:

2.3.2. Another property of the simplest flow is related to the following theorem:

Theorem: With an exponential distribution of the time interval between requirements T, regardless of how long it lasted, the remaining part of it has the same distribution law.

Proof: let T be distributed according to the exponential law: Suppose that the interval a has already lasted some time a< T. Let us find the conditional law of distribution of the remaining part of the interval T 1 = T-a

F a (x)=P(T-a x)

According to the probability multiplication theorem:

P((T>a)(T-a z) P(T-a a)=P(T>a) F a (z).

From here,

is equivalent to the event a , for which P(a ; on the other hand

P(T>a)=1-F(a), thus

F a (x)=(F(z+a)-F(a))/(1-F(a))

Hence, taking into account (3):

This property has only one type of flow - the simplest Poisson.