Any more or less advanced Internet user has repeatedly come across terms such as SMO and SMM. They are easily operated by insiders, however, most people have a somewhat vague idea of ​​what SMO and SMM really are, and even more so - what is their difference.

First, let's define that SMO and SMM are not the same thing. We can say that SMO is part of SMM, but these concepts should be separated in order to more fully understand all the information.

• This is social media marketing, which consists in holding a set of events on other people's sites (forums, blogs, websites, chats, news resources, etc.) in order to promote goods, services, advertise services and highlight events.
• SMM is not open advertising. This is a hidden, unobtrusive advertising that attracts the target audience to the promoted product. Users should not understand that they are being offered a product openly - they should themselves want to purchase / order a service due to the information presented.
• SMM encourages the posting of promoted information on social networks or other resources by other users and targeted audience attacked by SMM. The more competently the information is presented, the more people will want to tell their friends about it, that is, potential buyers.
• SMM provides information about the promoted product to the target audience in the form of reviews, communication between the user and sharing his own opinion.
• In order for SMM to be successful, it is important to establish a trusting atmosphere between users. This increases the level of trust in unobtrusive ads, and the user begins to believe the suggested tips and tricks.
• Provocative headlines, bright thoughts and ideas attract the attention of the audience to the promoted product and thanks to this, SMM wins the attention of the audience.
• Having gained attention, SMM envisions uniting the audience. This is what creates an atmosphere of trust and understanding, in which users lose their vigilance and do not realize that they are being offered a product. They only hear personal opinions and experiences that are shared with them. And they appreciate it.

• SMO is social media optimization, but it is not a social media job. SMO is work on a personal site, with the content that is posted on this site.
• The aim of SMO is to make the site attractive to social media users, they should be interested in visiting the site and exploring the content.
• SMO assumes the desire of users of social networks to share a link to the promoted resource with their friends.
• SMO helps transform its resource in such a way that content and technical characteristics are interesting and convenient for users of social networks.
• An important part of SMO is website transformation. It is necessary that the proposed content is filled with interesting videos and colorful illustrations for the text. Any text should be bright and attractive. This is the only way to achieve the irresistible desire of the user of the social network to bookmark this site for himself and tell his friends about it.
• Interesting content isn't the only SMO rule. It is very important that the site welcomes its visitors with a pleasant color scheme, user-friendly interface, and well-chosen fonts. The text should make you want to read it - it should be structured. Hardly anyone will read the “sheets” of the text without structuring, and SMO specialists know this.
• SMO builds the infrastructure of the site. Content should not only be easy to understand. Users of social networks need to be able to conveniently export it (the "share" button for social networks, subscription to the mailing list, bookmarking the site, "rating" the text, the ability of the user to place a link to the promoted site on his resource).
• One of the goals of SMO is to reduce user abandonment. Entering the site, the user does not close it on the first open page, but continues to explore other pages of the site. This can be achieved thanks to high-quality content and a user-friendly interface. Conveniently located announcements allow the user to navigate through the pages of the site with ease, which attracts his attention. The call for transitions to other pages is not excluded.
• The ability to comment and exchange views is a hallmark of SMO. Users are happy to join the discussions that unfold on the site. This increases traffic and brings in new visitors. If the site provides protection against spam and supports the best commentators, the popularity of the site increases significantly.

Introduction ................................................. .................................................. ........ 3

1 Markov chains with a finite number of states and discrete time 4

2 Markov chains with a finite number of states and continuous time 8

3 Processes of birth and death ............................................. ....................... eleven

4 Basic concepts and classification of queuing systems ... 14

5 The main types of open queuing systems .................... 20

5.1 Single-channel queuing system with failures .............. 20

5.2 Multichannel queuing system with failures ... 21

5.3 Single-channel queuing system with limited queue length ......................................... .................................................. ............................. 23

5.4 Single-channel queuing system with unlimited queue .......................................... .................................................. ............................ 26

5.5 Multichannel queuing system with limited queue .......................................... .................................................. ............................ 27

5.6 Multichannel queuing system with unlimited queue .......................................... .................................................. ............................ thirty

5.7 Multichannel queuing system with limited queue and limited waiting time in the queue .................................... ......... 32

6 Monte Carlo Method ............................................. ...................................... 36

6.1 The main idea of ​​the method .............................................. ............................... 36

6.2 Playing a continuous random variable ................................ 36

6.3 Random variable with exponential distribution ................. 38

7 Investigation of the queuing system ..................................... 40

7.1 Testing the hypothesis about the exponential distribution ............................ 40

7.2 Calculation of the main indicators of the queuing system ........ 45

7.3 Conclusions on the work of the investigated QS ............................................ ......... 50

8 Study of the modified QS .............................................. .......... 51

Conclusion................................................. .................................................. .53

List of sources used ............................................... ............. 54

Introduction

The topic of my thesis is the study of the queuing system. In its initial state, the CMO I am considering is one of the classic cases, namely M / M / 2/5 according to the accepted designation of Kendall. After studying the system, conclusions were made about the inefficiency of its work. Methods for optimizing the work of the QS have been proposed, but with these changes the system ceases to be classical. The main problem in the study of queuing systems is that in reality they can be investigated using the classical theory of queuing only in rare cases. The flows of incoming and outgoing claims may not be the simplest, therefore, finding the limiting probabilities of states using the Kolmogorov system of differential equations is impossible, the system may contain priority classes, then the calculation of the main indicators of the QS is also impossible.

To optimize the work of the QS, a system of two priority classes was introduced and the number of service channels was increased. In this case, it is advisable to apply simulation methods, for example, the Monte Carlo method. The main idea of ​​the method is that instead of an unknown random variable, its mathematical expectation is taken in a sufficiently large series of tests. A random variable is played out (in this case, these are the intensities of the incoming and outgoing flows), initially uniformly distributed. Then the transition from uniform distribution to exponential distribution is carried out by means of transition formulas. A program was written in the VisualBasic language that implements this method.

1 Markov chains with a finite number of states and discrete time

Let some system S be in one of the states of a finite (or countable) set of possible states S 1, S 2, ..., S n, and the transition from one state to another is possible only at certain discrete times t 1, t 2, t 3, called steps.

If a system passes from one state to another by chance, then they say that a random process with discrete time takes place.

A random process is called Markov if the probability of a transition from any state S i to any state S j does not depend on how and when the system S entered the state S i (i.e., there is no consequence in the system S). In this case, it is said that the functioning of the system S is described by a discrete Markov chain.

It is convenient to depict the transitions of the system S to various states using the state graph (Fig. 1).

Figure 1 - An example of a labeled state graph

The vertices of the graph S 1, S 2, S 3 denote the possible states of the system. An arrow directed from the vertex S i to the vertex S j denotes a transition; the number next to the arrow indicates the likelihood of this transition. An arrow that closes at the i-th vertex of the graph means that the system remains in the state S i with the probability of the arrow.

The graph of the system containing n vertices can be associated with the matrix NxN, the elements of which are the probabilities of transitions p ij between the vertices of the graph. For example, the graph in Fig. 1 is described by the matrix P:

called the transition probability matrix. The elements of the matrix p ij satisfy the conditions:

Matrix elements p ij - give the probabilities of transitions in the system in one step. Transition

S i - S j in two steps can be considered as occurring at the first step from S i to some intermediate state S k and at the second step from S k to S i. Thus, for the elements of the matrix of probabilities of transitions from S i to S j in two steps, we obtain:

In the general case of transition in m steps for the elements of the transition probability matrix, the following formula is valid:

(3)

We get two equivalent expressions for:

Let the system S be described by the transition probability matrix P:

If we denote by Р (m) a matrix whose elements are рi probabilities of transitions from S i to S j in m steps, then the following formula holds:

where the matrix P m is obtained by multiplying the matrix P by itself m times.

The initial state of the system is characterized by the state vector of the system Q (q i) (also called the stochastic vector).

where q j is the probability that the initial state of the system is S j state. Similarly to (1) and (2), the following relations hold:

Let us denote by

the state vector of the system after m steps, where q j is the probability that after m steps the system is in the S i state. Then the following formula is valid

If the transition probabilities P ij remain constant, then such Markov chains are called stationary. Otherwise, the Markov chain is called nonstationary.

2. Markov chains with a finite number of states and continuous time

If the system S can move to another state in a random way at an arbitrary moment of time, then we speak of a random process with continuous time. In the absence of aftereffect, such a process is called a continuous Markov chain. In this case, the transition probabilities for any i and j at any time instant are equal to zero (due to the continuity of time). For this reason, instead of the transition probability, a quantity is introduced - the probability density of the transition from state to state, defined as the limit:

If the quantities do not depend on t, then the Markov process is called homogeneous. If during the time the system can change its state at most once, then they say that the random process is ordinary. The value is called the intensity of the transition of the system from S i to S j. On the graph of system states, numerical values ​​are placed next to the arrows showing transitions to the vertices of the graph.

Knowing the intensity of the transitions, we can find the values ​​p 1 (t), p 2 (t),…, p n (t) - the probabilities of finding the system S in the states S 1, S 2,…, S n, respectively. In this case, the following condition is fulfilled:

The probability distribution of system states, which can be characterized by a vector, is called stationary if it does not depend on time, i.e. all components of the vector are constants.

The states S i and Sj are called communicating if transitions are possible.

A state S i is called essential if every S j reachable from S i is communicating with S i. The state S i is called insignificant if it is not essential.

If there are limiting probabilities of system states:

,

independent of the initial state of the system, then it is said that at, a stationary regime is established in the system.

A system in which the limiting (final) probabilities of the states of the system exist is called ergodic, and the random process proceeding in it is called ergodic.

Theorem 1. If S i is an inessential state, that is, when the system leaves any insignificant state.

Theorem 2. For a system with a finite number of states to have a unique limiting probability distribution of states, it is necessary and sufficient that all its essential states communicate with each other.

If a random process occurring in a system with discrete states is a continuous Markov chain, then for the probabilities p 1 (t), p 2 (t),…, p n (t), one can compose a system of linear differential equations called the Kolmogorov equations. When drawing up equations, it is convenient to use the system state graph. On the left side of each of them is the derivative of the probability of some (j-th) state. On the right side - the sum of the products of the probabilities of all states, from which a transition to a given state is possible, by the intensities of the corresponding flows, minus the total intensity of all flows that take the system out of the given (j-th) state, multiplied by the probability of a given (j-th) state ...

3 Processes of birth and death

This is the name for a wide class of random processes occurring in the system, the labeled state graph of which is shown in Fig. 3.

Figure 2 - The graph of states for the processes of death and reproduction

Here, the quantities,,…, are the intensities of system transitions from state to state from left to right, can be interpreted as the intensity of the creation (occurrence of claims) in the system. Similarly, the values ​​,, ..., are the intensities of system transitions from state to state from right to left, can be interpreted as the intensity of death (execution of orders) in the system.

Since all states are communicating and essential, there is (by virtue of Theorem 2) a limiting (final) probability distribution of states. Let us obtain formulas for the final probabilities of the states of the system.

In stationary conditions, for each state, the flow entering the given state must be equal to the flow leaving the given state. Thus, we have:

For state S 0:

Hence:

For state S 1:

Hence:

Given that :

(4)

, ,…, (5)

4. Basic concepts and classification of queuing systems

An application (or requirement) is a demand for the satisfaction of any need (hereinafter, the needs are assumed to be of the same type). Executing a request is called servicing a request.

A queuing system (QS) is any system for fulfilling claims arriving at it at random times.

The receipt of an application in the QS is called an event. The sequence of events involving the arrival of applications in the QS is called the incoming flow of applications. The sequence of events involving the execution of applications in the QS is called the outgoing flow of applications.

The flow of applications is called the simplest if it satisfies the following conditions:

1) no aftereffect, i.e. applications are received independently of each other;

2) stationarity, i.e. the probability of a given number of requests arriving at any time interval depends only on the value of this interval and does not depend on the value of t 1, which allows us to speak about the average number of requests per unit time, λ, called the intensity of the flow of requests;

3) ordinariness, i.e. at any moment of time, only one request arrives at the QS, and the arrival of two or more requests simultaneously is negligible.

For the simplest flow, the probability p i (t) of exactly i requests arriving at the QS in time t is calculated by the formula:

(6)

those. the probabilities are distributed according to Poisson's law with the parameter λt. For this reason, the simplest stream is also called a Poisson stream.

The distribution function F (t) of a random time interval T between two successive claims is, by definition, equal to ... But, where is the probability that the next one after the last request will arrive at the QS after the time t, i.e. in time t, the QS will not receive a single request. But the probability of this event is found from (6) at i = 0. Thus:

The probability density f (t) of a random variable T is determined by the formula:

,

The mathematical expectation, variance and standard deviation of the random variable T are equal, respectively:

A service channel is a device in a QS that serves a request. A QS containing one service channel is called single-channel, and one containing more than one service channel is called multi-channel.

If a request arriving at the QS can receive a denial of service (due to the busyness of all service channels) and in case of refusal is forced to leave the QS, then such a QS is called a QS with refusals.

If, in the event of a refusal in service, applications can enter the queue, then such QS are called QS with a queue (or with waiting). At the same time, a distinction is made between QS with limited and unlimited queues. The queue can be limited both by the number of seats and by the waiting time. Distinguish between open and closed type CMOs. In an open-type QS, the flow of applications does not depend on the QS. In a closed-type QS, a limited number of customers are served, and the number of applications can significantly depend on the state of the QS (for example, a team of fitters - adjusters serving machine tools at the plant).

CMOs may also differ in service discipline.

If there is no priority in the QS, then applications are selected from the queue to the channel according to different rules.

First come - first served (FCFS - First Came - First Served)

· Last Came - First Served (LCFS - Last Came - First Served)

Priority service for requests with the shortest duration of service (SPT / SJE)

First-priority service for requests with the shortest time to service (SRPT)

First-priority service for claims with the shortest average service time (SEPT)

Priority service requirements with the shortest average maintenance time (SERPT)

There are two types of priorities - absolute and relative.

If a request in the process of servicing can be removed from the channel and returned to the queue (or leaves the QS altogether) when a request with a higher priority arrives, then the system operates with absolute priority. If the service of any request in the channel cannot be interrupted, then the QS operates with relative priority. There are also priorities enforced by a specific rule or set of rules. An example would be priority that changes over time.

QS are described by some parameters that characterize the efficiency of the system.

- the number of channels in the system;

- the intensity of receipt of applications in the CMO;

- the intensity of service requests;

- load factor of the system;

- the number of places in the queue;

- the likelihood of refusal to service the request received by the CMO;

- the probability of servicing the request received by the QS (relative throughput of the QS);

Wherein:

(8)

A is the average number of applications served in the QS per unit of time (the absolute throughput of the QS)

- the average number of applications in the CMO

Is the average number of channels in the QS, busy with servicing applications. At the same time, this is the average number of applications served in the QS per unit of time. The value is defined as the mathematical expectation of a random number of n channels occupied by servicing.

, (10)

where is the probability of finding the system in the S k state.

- channel occupancy ratio

- average waiting time for a request in the queue

- the intensity of requests leaving the queue

Is the average number of applications in the queue. It is defined as the mathematical expectation of a random variable m - the number of applications in the queue

(11)

Here is the probability that i applications are in the queue;

Is the average time spent by an application with the QS

- the average time of a request being in the queue

For open QS, the following ratios are valid:

(12)

These relations are called Little formulas and apply only to stationary flows of claims and services.

Let's consider some specific types of CMOs. In this case, it will be assumed that the distribution density of the time interval between two successive events in the QS has an exponential distribution (7), and all flows are the simplest.

5. The main types of open queuing systems

5.1 Single-channel queuing system with failures

A labeled state graph of a single-channel QS is shown in Figure 3.

Figure 3 - Graph of states of a single-channel QS

Here and are the intensity of the flow of applications and the execution of applications, respectively. The state of the system S o means that the channel is free, and S 1 - that the channel is busy serving a claim.

The system of Kolmogorov differential equations for such a QS has the form:

where p o (t) and p 1 (t) are the probabilities of finding the QS in the states So and S1, respectively. The equations for the final probabilities p o and p 1 will be obtained by equating to zero the derivatives in the first two equations of the system. As a result, we get:

(14)

(15)

The probability p 0 in its meaning is the probability of servicing the customer p obs, since the channel is free, and the probability p 1 in its meaning is the probability of refusal to service the customer arriving in the QS, p ot, since the channel is busy serving the previous customer.

5.2 Multichannel queuing system with failures

Let the QS contain n channels, the intensity of the incoming flow of claims is equal, and the intensity of service of the claim by each channel is. The labeled system state graph is shown in Figure 4.

Figure 4 - State graph of a multichannel QS with failures

The state S 0 means that all channels are free, the state S k (k = 1, n) means that k channels are busy with servicing claims. The transition from one state to another adjacent right one occurs abruptly under the influence of the incoming flow of requests with intensity regardless of the number of working channels (upper arrows). For the transition of the system from one state to the adjacent left one, it does not matter which channel is released. The quantity characterizes the intensity of servicing requests when working in the QS of k channels (lower arrows).

Comparing the graphs in Fig. 3 and fig. 5 it is easy to see that a multichannel QS with failures is a special case of the birth and death system, if in the latter we accept and

(16)

In this case, to find the final probabilities, one can use formulas (4) and (5). Taking into account (16), we get from them:

(17)

(18)

Formulas (17) and (18) are called formulas of Erlang, the founder of the queuing theory.

The probability of denial of service for a claim p ot is equal to the probability that all channels are busy, i.e. the system is in the state S n. Thus,

(19)

We find the relative throughput of the QS from (8) and (19):

(20)

We find the absolute throughput from (9) and (20):

The average number of channels occupied by servicing can be found by formula (10), but we will make it easier. Since each busy channel per unit of time serves on average requests, it can be found by the formula:

5.3 Single-channel queuing system with limited queue length

In a queuing system with a limited queue, the number of places m in the queue is limited. Consequently, the application arriving at the time when all the places in the queue are occupied is rejected and leaves the QS. The graph of such a QS is shown in Figure 5.

S 0

Figure 5 - State graph of a single-channel QS with a limited queue

The states of the QS are represented as follows:

S 0 - the service channel is free,

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

S 2 - the service channel is busy, there is one customer in the queue,

S k +1 - the service channel is busy, there are k customers in the queue,

S m +1 - the service channel is busy, all m places in the queue are occupied.

To obtain the necessary formulas, one can use the fact that the QS in Figure 5 is a special case of the birth and death system shown in Figure 2, if in the latter we accept and

(21)

Expressions for the final probabilities of states of the considered QS can be found from (4) and (5) taking into account (21). As a result, we get:

For p = 1 formulas (22), (23) take the form

For m = 0 (there is no queue), formulas (22), (23) transform into formulas (14) and (15) for a single-channel QS with failures.

A request received by the QS receives a denial of service if the QS is in the state S m +1, i.e. the probability of denial of service is:

The relative throughput of the CMO is:

The average number of applications in the queue L och is found by the formula

and can be written as:

(24)

For, formula (24) takes the form:

- the average number of applications in the QS is found by the formula (10)

and can be written as:

(25)

For, from (25) we get:

The average residence time of an application in the QS and in the queue is found by formulas (12) and (13), respectively.

5.4 Single-channel queuing system with unlimited queue

An example of such a CMO is the director of an enterprise, sooner or later forced to resolve issues related to his competence, or, for example, a queue in a bakery with one cashier. The graph of such a QS is shown in Figure 6.

Figure 6 - The state graph of a single-channel QS with an unlimited queue

All the characteristics of such a QS can be obtained from the formulas of the previous section, assuming in them. In this case, it is necessary to distinguish between two essentially different cases: a); b). In the first case, as can be seen from formulas (22), (23), p 0 = 0 and p k = 0 (for all finite values ​​of k). This means that at, the queue grows indefinitely, i.e. this case is of no practical interest.

Consider the case when. Formulas (22) and (23) will be written in the form:

Since there is no restriction on the queue length in the QS, any request can be serviced, i.e.

The absolute bandwidth is:

We obtain the average number of requests in the queue from formula (24) for:

The average number of serviced applications is:

The average residence time of an application in the QS and in the queue is determined by formulas (12) and (13).

5.5 Multichannel queuing system with limited queue

Let a Poisson flow of claims with intensity arrive at the input of a QS with service channels. The intensity of service of the claim by each channel is equal, and the maximum number of places in the queue is equal to.

The graph of such a system is shown in Figure 7.

Figure 7 - State graph of a multichannel QS with a limited queue

- all channels are free, there is no queue;

- busy l channels ( l= 1, n), there is no queue;

All n channels are busy, there is a queue i applications ( i= 1, m).

Comparison of the graphs in Figure 2 and Figure 7 shows that the latter system is a special case of the birth and death system if the following changes are made in it (the left-hand notation refers to the birth and death system):

Expressions for the final probabilities are easy to find from formulas (4) and (5). As a result, we get:

(26)

The formation of a queue occurs when, at the time of the next request to the QS, all channels are busy, i.e. the system contains either n, or (n + 1),…, or (n + m– 1) customers. Because these events are inconsistent, then the probability of queuing p och is equal to the sum of the corresponding probabilities :

(27)

The relative throughput is:

The average number of applications in the queue is determined by formula (11) and can be written as:

(28)

Average number of applications in the CMO:

The average residence time of an application in the QS and in the queue is determined by formulas (12) and (13).

5.6 Multichannel queuing system with unlimited queue

The graph of such a QS is shown in Figure 8 and is obtained from the graph in Figure 7 for.

Figure 8 - State graph of a multichannel QS with an unlimited queue

The formulas for the final probabilities can be obtained from the formulas for the n-channel QS with a limited queue at. It should be borne in mind that for the probability p 0 = p 1 = ... = p n = 0, i.e. the queue grows indefinitely. Consequently, this case is not of practical interest, and only the case is considered below. For from (26) we get:

The formulas for the remaining probabilities have the same form as for the QS with a limited queue:

From (27) we obtain an expression for the probability of the formation of a queue of applications:

Since the queue is not limited, the probability of refusal to service the request is:

Absolute bandwidth:

From formula (28) at we obtain an expression for the average number of requests in the queue:

The average number of serviced requests is determined by the formula:

The average time spent in the QS and in the queue is determined by formulas (12) and (13).

5.7 Multichannel queuing system with limited queue and limited waiting time in the queue

The difference between such a QS and the QS considered in Subsection 5.5 is that the waiting time for service when the customer is in the queue is considered a random variable distributed according to the exponential law with the parameter, where is the average waiting time for a customer in the queue, and it makes sense the intensity of the flow of applications leaving the queue. The graph of such a QS is shown in Figure 9.

Figure 9 - Graph of a multichannel QS with a limited queue and a limited waiting time in the queue

The rest of the notation here has the same meaning as in the subsection.

Comparison of the graphs in Fig. 3 and 9 shows that the last system is a special case of the birth and death system, if the following changes are made in it (the left notation refers to the birth and death system):

Expressions for the final probabilities are easy to find from formulas (4) and (5), taking into account (29). As a result, we get:

,

where . The probability of queuing is determined by the formula:

A request is denied service when all m places in the queue are occupied, i.e. denial of service probability:

Relative bandwidth:

Absolute bandwidth:

The average number of applications in the queue is found by formula (11) and is equal to:

The average number of applications served in the QS is found by formula (10) and is equal to:

The average time spent by an application in the QS is the sum of the average waiting time in the queue and the average time of service of the application:

6. Monte Carlo method

6.1 The main idea of ​​the method

The essence of the Monte Carlo method is as follows: it is required to find the value a some studied quantity. To do this, choose such a random variable X, the mathematical expectation of which is equal to a: M (X) = a.

In practice, they do the following: make n tests, as a result of which n possible values ​​of X are obtained; calculate their arithmetic mean and take as an estimate (approximate value) a * the required number a:

Because the Monte Carlo method requires a large number of tests, it is often referred to as the statistical test method.

6.2 Playing a continuous random variable

Let it be necessary to obtain the values ​​of a random variable distributed in an interval with density. Let us prove that the values ​​can be found from the equation

where is a random variable uniformly distributed over the interval.

Those. choosing the next value, it is necessary to solve the equation (30) and find the next value. For proof, consider the function:

We have general properties of the probability density:

It follows from (31) and (32) that and the derivative .

This means that the function monotonically increases from 0 to 1. And any straight line, where, intersects the graph of the function at a single point, the abscissa of which we take as. Thus, equation (30) always has one and only one solution.

Let's choose now an arbitrary interval contained inside. The points of this interval correspond to the ordinates of the curve, which satisfy the inequality ... Therefore, if it belongs to an interval, then

Belongs to an interval and vice versa. Means: . Because uniformly distributed in, then

, and this just means that the random variable that is the root of equation (30) has a probability density.

6.3 Random variable with exponential distribution

The simplest flow (or Poisson flow) is a flow of customers when the time interval between two successive customers is a random variable distributed over an interval with density

Let's calculate the mathematical expectation:

After integration by parts, we get:

.

The parameter is the intensity of the flow of applications.

The formula for the drawing will be obtained from equation (30), which in this case will be written as follows:.

Calculating the integral on the left, we get the relation. From here, expressing, we get:

(33)

Because the quantity is distributed in the same way as and, therefore, formula (33) can be written in the form:

7 Investigation of the queuing system

7.1 Testing the exponential distribution hypothesis

The enterprise I am researching is a two-channel queuing system with a limited queue. The input receives a Poisson flow of claims with intensity λ. The intensity of servicing claims by each of the channels μ, and the maximum number of places in the queue is m.

Initial parameters:

The service time of claims has the empirical distribution indicated below and has an average value.

I carried out control measurements of the processing time of applications received by this CMO. To start the research, it is necessary to establish the law of distribution of the processing time of applications based on these measurements.

Table 6.1 - Grouping requests by processing time

A hypothesis is put forward about the exponential distribution of the general population.

In order, at a level of significance, to test the hypothesis that a continuous random variable is distributed according to an exponential law, it is necessary:

1) Find the sample mean for a given empirical distribution. To do this, we replace each i-th interval with its middle and compose a sequence of equally spaced variants and the corresponding frequencies.

2) Take as parameter estimate λ the exponential distribution is the reciprocal of the sample mean:

3) Find the probabilities of hitting X in partial intervals by the formula:

4) Calculate theoretical frequencies:

where is the sample size

5) Compare empirical and theoretical frequencies using Pearson's criterion, taking the number of degrees of freedom, where S is the number of intervals in the initial sample.

Table 6.2 - Grouping of requests by processing time with an average time interval

Let's find the sample mean:

2) Let us take as an estimate of the parameter λ of the exponential distribution a value equal to ... Then:

()

3) Find the probabilities of hitting X in each of the intervals using the formula:

For the first interval:

For the second interval:

For the third interval:

For the fourth interval:

For the fifth interval:

For the sixth interval:

For the seventh interval:

For the eighth interval:

4) Let's calculate the theoretical frequencies:

The calculation results are entered into the table. Compare empirical and theoretical frequencies using Pearson's criterion.

To do this, we calculate the differences, their squares, then the ratios. Summing up the values ​​of the last column, we find the observed value of the Pearson test. According to the table of critical distribution points at the level of significance and the number of degrees of freedom, we find the critical point

Table 6.3 - Calculation results

i
1	22	0,285	34,77	-12,77	163,073	4,690
2	25	0,204	24,888	0,112	0,013	0,001
3	23	0,146	17,812	5,188	26,915	1,511
4	16	0,104	12,688	3,312	10,969	0,865
5	14	0,075	9,15	4,85	23,523	2,571
6	10	0,053	6,466	3,534	12,489	1,932
7	8	0,038	4,636	3,364	11,316	2,441
8	4	0,027	3,294	0,706	0,498	0,151
122

Because , then there is no reason to reject the hypothesis of the distribution of X according to the exponential law. In other words, the observational data are consistent with this hypothesis.

7.2 Calculation of the main indicators of the queuing system

This system is a special case of the death and reproduction system.

The graph of a given system:

Figure 10 - Graph of states of the studied QS

Since all states are communicating and essential, there is a limiting probability distribution of states. Under stationary conditions, the flow entering a given state must be equal to the flow leaving this state.

(1)

For state S 0:

Hence:

For state S 1:

Hence:

Given that :

Similarly, we obtain the equations for the remaining states of the system. As a result, we get a system of equations:

The solution to this system will look like:

; ; ; ; ;

; .

Or, taking into account (1):

Coefficient of workload of CMO:

Taking this into account, we rewrite the limiting probabilities in the form:

The most probable state is that both QS channels are busy and all the places in the queue are occupied.

The likelihood of queuing:

A request is denied service when all m places in the queue are occupied, i.e.:

The relative throughput is:

The probability that a newly arrived application will be served is 0.529

Absolute bandwidth:

CMO serves an average of 0.13225 applications per minute.

Average number of queued applications:

The average number of applications in the queue is close to the maximum queue length.

The average number of requests served in the QS can be written as:

On average, all SMO channels are constantly busy.

Average number of applications in the CMO:

For open QS, Little's formulas are valid:

Average time spent by an application with the CMO:

Average time spent by an application in the queue:

7.3 Conclusions on the work of the investigated QS

The most probable state of this QS is the busyness of all channels and places in the queue. Approximately half of all incoming applications leave the CMO unprocessed. Approximately 66.5% of the waiting time is spent waiting in line. Both channels are constantly busy. All this suggests that, on the whole, this QS scheme is unsatisfactory.

To reduce channel load, reduce queuing time and reduce the likelihood of rejection, it is necessary to increase the number of channels and introduce a system of priorities for requests. It is advisable to increase the number of channels to 4. It is also necessary to change the service discipline from FIFO to a system with priorities. All applications will now belong to one of two priority classes. Class I applications have relative priority over Class II applications. To calculate the main indicators of this modified QS, it is advisable to apply any of the methods of simulation. A program was written in the VisualBasic language that implements the Monte Carlo method.

8 Study of the modified QS

When working with the program, the user must set the main parameters of the QS, such as the flow rates, the number of channels, priority classes, places in the queue (if the number of seats in the queue is zero, then the QS with failures), as well as the modulation time interval and the number of tests. The program converts the generated random numbers according to the formula (34), thus, the user receives a sequence of time intervals, exponentially distributed. Then the application with the minimum is selected and placed in the queue, according to its priority. During the same time, the queue and channels are recalculated. Then this operation is repeated until the end of the modulation time set initially. In the body of the program there are counters, on the basis of the readings of which the main indicators of the CMO are formed. If several tests were specified to increase the accuracy, then the evaluation for a series of experiments is taken as the final results. The program turned out to be quite universal, with its help one can study CMOs with any number of priority classes, or without any priorities at all. To check the correctness of the algorithm, the initial data of the classical QS studied in Section 7 were introduced into it. The program simulated a result close to that obtained using the methods of queuing theory (see Appendix B). The error that occurred during the simulation can be explained by the fact that not enough tests were carried out. The results obtained using the software for QS with two priority classes and an increased number of channels show the feasibility of these changes (see Appendix B). Higher priority has been given to "faster" tickets, allowing shorter assignments to be examined quickly. The average length of the queue in the system is reduced, and, accordingly, the means for organizing the queue is minimized. As the main disadvantage of this organization, one can single out the fact that "long" applications are in the queue for a long time or are refused altogether. The introduced priorities can be reassigned after evaluating the usefulness of a particular type of applications for the QS.

Conclusion

In this work, a two-channel QS was investigated using the methods of queuing theory, and the main indicators characterizing its operation were calculated. It was concluded that this mode of operation of the QS is not optimal, and methods were proposed that reduce the workload and increase the throughput of the system. To test these methods, a program was created that simulates the Monte Carlo method, with the help of which the results of calculations for the original model of the QS were confirmed, and the main indicators for the modified one were calculated. The algorithm error can be estimated and reduced by increasing the number of tests. The versatility of the program allows you to use it in the study of various CMOs, including classical ones.

1 Wentzel, E.S. Operations Research / E.S. Wentzel. - M .: "Soviet radio", 1972. - 552 p.

2 Gmurman, V.E. Probability theory and mathematical statistics / V.E. Gmurman. - M .: "High school", 2003. - 479 p.

3 Lavrus, O.E. Queuing theory. Methodical instructions / O.E. Lavrus, F.S. Mironov. - Samara: SamGAPS, 2002. - 38 p.

4 Sahakyan, G.R. Queuing theory: lectures / G.R. Sahakyan. - Mines: YURGUES, 2006 .-- 27 p.

5 Avsievich, A.V. Queuing theory. Streams of requirements, queuing systems / A.V. Avsievich, E.N. Avsievich. - Samara: SamGAPS, 2004 .-- 24 p.

6 Chernenko, V.D. Higher mathematics in examples and problems. In 3.vol. T. 3 / V.D. Chernenko. - St. Petersburg: Polytechnic, 2003 .-- 476 p.

7 Kleinrock, L. Queuing Theory / L. Kleinrock. Translated from English / Transl. I.I. Grushko; ed. IN AND. Neumann. - M .: Mashinostroenie, 1979 .-- 432 p.

8 Olzoeva, S.I. Modeling and calculation of distributed information systems. Textbook / S.I. Olzoeva. - Ulan-Ude: VSSTU, 2004 .-- 66 p.

9 Sobol, I.M. Monte Carlo method / I.M. Sable. - M .: "Science", 1968. - 64 p.

When researching operations, one often has to deal with systems designed for reusable use for solving the same type of problems. The resulting processes are called service processes, and systems - queuing systems (QS)... Examples of such systems are telephone systems, repair shops, computer systems, ticket offices, shops, hairdressers, and the like.

Each QS consists of a certain number of service units (devices, devices, points, stations), which we will call service channels... Channels can be communication lines, operating points, computers, sellers, etc. According to the number of channels, CMOs are subdivided into single-channel and multichannel.

Applications are usually received by the CMO not regularly, but by accident, forming the so-called random stream of applications (requirements)... Generally speaking, the servicing of claims also continues for some random time. The random nature of the flow of requests and the service time leads to the fact that the QS is loaded unevenly: at some time periods a very large number of requests accumulates (they either enter the queue or leave the QS unserved), at other periods the QS works with underload or idle.

The subject of queuing theory is the construction of mathematical models linking the given operating conditions of the QS (the number of channels, their performance, the nature of the flow of applications, etc.) with the efficiency indicators of the QS, which describe its ability to cope with the flow of applications.

As indicators of efficiency of health care organizations used: the average number of requests served per unit of time; the average number of applications in the queue; average waiting time for service; the likelihood of denial of service without waiting; the probability that the number of applications in the queue will exceed a certain value, etc.

CMOs are divided into two main types (classes): CMO with refusals and CMO with waiting (queue)... In a QS with refusals, an application received at the moment when all channels are busy gets a refusal, leaves the QS and does not participate in the further servicing process (for example, a request for a telephone conversation at the moment when all channels are busy, receives a refusal and leaves the QS unserved). In the queuing system with waiting, a request that arrives at a time when all channels are busy does not leave, but becomes a queue for service.

Waiting queuing systems are divided into different types depending on how the queue is organized: with a limited or unlimited queue length, with a limited waiting time, etc.

For the classification of CMOs, it is important service discipline, which determines the order of selection of applications from among those received and the order of their distribution between free channels. On this basis, the service of the request can be organized according to the principle "first came - first served", "last arrived - first served" (this procedure can be used, for example, when removing products from a warehouse for servicing, since the latter are often more accessible) or priority service (where the most important tickets are served first). The priority can be either absolute, when a more important request "displaces" the usual request from service (for example, in the event of an emergency, the planned work of repair crews is interrupted until the accident is eliminated), or relative, when a more important request receives only the "best" place queue.

The concept of a Markov stochastic process

The process of work of the CMO is random process.

Under random (probabilistic or stochastic) process the process of change in time of the state of any system in accordance with probabilistic laws is understood.

The process is called discrete state process, if its possible states can be enumerated in advance, and the transition of the system from state to state occurs instantly (in a jump). The process is called continuous time process if the moments of possible transitions of the system from state to state are not fixed in advance, but are random.

The QS operation process is a random process with discrete states and continuous time. This means that the state of the QS changes abruptly at random moments of the appearance of some events (for example, the arrival of a new request, the end of service, etc.).

The mathematical analysis of the work of the QS is greatly simplified if the process of this work is Markovian. The random process is called Markov or a random process without consequence if for any moment of time the probabilistic characteristics of the process in the future depend only on its state at the moment and do not depend on when and how the system came to this state.

An example of a Markov process: the system is a counter in a taxi. The state of the system at the moment is characterized by the number of kilometers (tenths of kilometers) traveled by the car up to this moment. Let the counter show at the moment. The probability that at the moment the counter will show a certain number of kilometers (more precisely, the corresponding number of rubles) depends on, but does not depend on, at what moments in time the counter readings changed until the moment.

Many processes can be considered approximately Markovian. For example, the process of playing chess; system - a group of chess pieces. The state of the system is characterized by the number of opponent's pieces remaining on the board at the moment. The probability that at the moment a material advantage will be on the side of one of the opponents depends primarily on the state of the system at the moment, and not on when and in what sequence the pieces disappeared from the board until the moment.

In a number of cases, the history of the processes under consideration can be simply neglected and Markov models can be used to study them.

When analyzing random processes with discrete states, it is convenient to use a geometric scheme - the so-called state graph... Usually, the states of the system are depicted by rectangles (circles), and possible transitions from state to state - by arrows (oriented arcs) connecting the states.

Example 1. Construct the state graph of the following random process: the device consists of two nodes, each of which can fail at a random moment of time, after which you instantly start "repairing the node, continuing in a previously unknown random time.

Solution. Possible states of the system: - both nodes are in good working order; - the first unit is being repaired, the second is operational; - the second unit is being repaired, the first is operational; - both units are being repaired. The system graph is shown in Fig. 1.

An arrow directed, for example, from to, means the transition of the system at the moment of failure of the first node, from to - the transition at the moment of completion of the repair of this node.

The graph lacks arrows from to and from to. This is due to the fact that node failures are assumed to be independent of each other and, for example, the probability of simultaneous failure of two nodes (transition from to) or simultaneous completion of repairs of two nodes (transition from to) can be neglected.

For a mathematical description of a Markov random process with discrete states and continuous time, proceeding in the QS, we will get acquainted with one of the important concepts of the theory of probability - the concept of the flow of events.

Streams of events

Under stream of events is understood as a sequence of homogeneous events following one after another at some random moments in time (for example, the flow of calls at the telephone exchange, the flow of computer failures, the flow of buyers, etc.).

The stream is characterized intensity- the frequency of occurrence of events or the average number of events entering the QS per unit of time.

The stream of events is called regular if events follow one another at regular intervals. For example, the flow of products on an assembly line conveyor (at a constant speed) is regular.

The stream of events is called stationary if its probabilistic characteristics do not depend on time. In particular, the intensity of a stationary flow is a constant value:. For example, the flow of cars on the city avenue is not stationary during the day, but this flow can be considered stationary during the day, say, during rush hours. Please note that in the latter case, the actual number of passing cars per unit of time (for example, per minute) may differ significantly from each other, but their average number will be constant and will not depend on time.

The stream of events is called flow without aftereffect if for any two non-overlapping time segments and - the number of events falling on one of them does not depend on the number of events falling on the others. For example, the flow of passengers entering the metro has practically no aftereffect. And, say, the flow of customers leaving the counter with purchases already has an aftereffect (if only because the time interval between individual customers cannot be less than the minimum service time for each of them).

The stream of events is called ordinary if the probability of two or more events hitting a small (elementary) time interval is negligible compared to the probability of hitting one event. In other words, the flow of events is ordinary if events appear in it singly, and not in groups. For example, the flow of trains approaching the station is ordinary, and the flow of cars is not ordinary.

The flow of events is called the simplest (or stationary Poisson), if it is simultaneously stationary, ordinary, and has no aftereffect. The name "simplest" is explained by the fact that the QS with the simplest flows has the simplest mathematical description. Note that a regular stream is not "simple", since it has an aftereffect: the moments of occurrence of events in such a stream are rigidly fixed.

The simplest flow as a limiting one arises in the theory of random processes just as naturally as in probability theory the normal distribution is obtained as a limiting one for a sum of random variables: upon superposition (superposition) of a sufficiently large number of independent, stationary and ordinary flows (comparable in intensity, a flow is obtained that is close to the simplest one with an intensity equal to the sum of the intensities of the incoming flows, that is, Consider on the time axis (Fig. 1) the simplest stream of events as an unlimited sequence of random points.

It can be shown that for the simplest flow, the number of m events (points) falling on an arbitrary time interval is distributed over Poisson's law

for which the mathematical expectation of a random variable is equal to its variance:.

In particular, the probability that no event will occur in a time is

Let us find the distribution of the time interval between arbitrary two neighboring events of the simplest flow.

In accordance with (2), the probability that none of the subsequent events will appear on a time section of length is equal to

and the probability of the opposite event, i.e. distribution function of a random variable, is

The probability density of a random variable is the derivative of its distribution function (Fig. 3), ie

The distribution given by the probability density (5) or the distribution function (4) is called indicative(or exponential). Thus, the time interval between two adjacent arbitrary events has an exponential distribution, for which the mathematical expectation is equal to the standard deviation of the random variable

and back in magnitude of the flow rate.

The most important property of the exponential distribution (inherent only to the exponential distribution) is as follows: if the time interval distributed according to the exponential law has already lasted for some time, then this does not in any way affect the distribution law of the remaining part of the interval: it will be the same as the distribution law for everything interval.

In other words, for a time interval between two consecutive adjacent events of a stream having an exponential distribution, any information about how long this interval has elapsed does not affect the distribution law of the remaining part. This property of the exponential law is, in essence, another formulation for "no aftereffect" - the main property of the simplest flow.

For the simplest flow with intensity, the probability of hitting

(Note that this approximate formula, obtained by replacing a function with only the first two terms of its expansion in a power series, the more accurate the smaller).

CMO is translated from English as social media optimization. She pursues the task of attracting and retaining visitors on social networks. Also, the CMO is aimed at work on the modernization of the site.

CMO is an internal promotion, and SMM is an external one.

CMO optimizes only the internal component, it does not concern website promotion in social networks.

Every promising entrepreneur strives to optimize and promote his site. But along with search engine optimization, there is also social optimization. These are CMO and CMM. Social optimization can significantly increase the attendance of the target audience. Therefore, you should not limit yourself only to the promotion of your site. CMO and CMM differ slightly in procedure.

If website promotion is aimed at robot algorithms, then CMO and CMM are working on audience optimization.

Components of internal optimization of QS

With the SMO, all work can be done on the site without investing money. Internal optimization work includes technical components and site audit, work on filling and changing the content of the site, work on the appearance, linking, installing buttons, sitemaps, comments from social networks, forming blocks.

An audit includes an analysis of the weaknesses of the site and their fixes. Revised design, optimization of introductory words for ease of search, competitiveness. During a technical audit, the content is checked for literacy, link functionality, and download speed. Also, during the audit, many other parameters are checked, and all this is aimed at the effective operation of the page.

It's no secret that the content of the site constantly needs to be updated, changed, and innovated. As a rule, after the development of a full-fledged site, changing the content is an ongoing process. Literate and consistent articles are essential. The behavioral response of search engine systems largely depends on this.

Also, the appearance of the site, its design plays an important role. It should be beautiful, not overloaded with clumsy colors, differ from competitive sites, and be correctly located. The visual experience also attracts visitors. If the appearance is beautiful and solid, then this makes a positive impression on the site owner, as it produces an aesthetic pleasure. It is also very important that the information is located clearly and logically, so that you can quickly find the information you need.

Site re-linking affects navigation. The site becomes more understandable for search engines and users.

It's a good idea to set up a sitemap that contains links to all pages. Better to create it as a separate page. This will improve navigation and usability.

On the site, you need to give a place for comments from social networks. Registered users on social networks will be able to comment on articles and other text attachments on your site. These comments are displayed on social media, which will serve as an advertisement for you.

Another useful thing is block formation. On the site page at the edge, you can place a column (sidebar) with fresh and interesting articles. This will keep readers engaged as people love to be in the know. Perhaps this will be a good incentive to visit the site more than once.

P.S. If you do not want to delve into all the details and tricks of website promotion, we recommend that you entrust this business to professionals. The company JoomStudio.com.ua is engaged in the promotion of the site on the Internet at a professional level. We recommend that you contact them for website promotion.

Types of queuing systems

Depending on how the application is dealt with in the event that all channels are busy, they distinguish:

QS with a denial of service request and QS with waiting.

It is typical for a QS with a refusal that a request that has found all channels busy leaves the system immediately.

In a queuing system with an expectation, a request that has found all channels busy does not leave the system, but is put into a queue and, when one of the channels is released, is serviced. In a queuing QS, any restrictions may or may not be imposed on the process of waiting for applications in the queue. In the latter case, they say that they are dealing with a "pure" QS with expectation. If restrictions are imposed on the waiting process, then the QS is called a "mixed-type system". In such systems, due to the imposed restrictions, there may be cases when the application will receive a denial of service, i.e. Mixed type QS also shows signs of failure QS.

Mixed systems may have the following restrictions:

a) the number of applications in the queue;

b) while the application is in the queue;

c) for the total time spent by the application in the CMO.

Mixed type CMOs are most often found in the REU technology.

Mathematical description of QS with failure

Consider a failure queuing system with NS channels. Suppose that the flow of claims arriving at the QS is the simplest and has a density l. In addition, we will assume that the service time of claims is distributed exponentially with the parameter

where M (Tob) - the mathematical expectation of the service time of the request.

Therefore, the distribution density of the service time

For the system under consideration, the following states are possible:

x 0- all channels are free;

x 1 - one channel is busy;

x k - busy k channels;

x n - everyone is busy NS channels.

These states of the queuing system can be described by Erlang differential equations. their solution allows one to obtain formulas for calculating the probabilities, which are constant for the steady state. Such a regime occurs at a time t® ¥.

The coefficient is defined as

where M (Tob) - mathematical expectation of the service time of one request.

Erlang's formulas are obtained for the case of exponential distribution of the service time, but they are also valid for any other law, as long as the flow of requests is simple.

The probability of a request not being served is defined as

q

The average fraction of the time that the service system will be idle can be determined by the probability of the state x 0, those.

P idle = p (x 0) = p 0

Example. Let devices with an average density arrive at the repair site of technological equipment l= 2 units / h. The average service time for one piece of equipment is 24 minutes (0.4 hours). A claim that makes all channels busy receives a denial of service.

It is required to determine the characteristics of the CMO assuming the presence of one workplace. In addition, it is required to establish how the characteristics of the QS change with the introduction of a second workplace.

Solution. By the condition of the problem, we have a QS with a failure. We will assume that the flow of claims arriving at the QS is the simplest with an average density l.

1. Let's calculate the channel load factor or reduced order density

2. Let us find the characteristics of the QS for the number of channels n = 1. Probability of non-service requests:

Relative bandwidth q will determine how

q = 1- P required = 1 – 0,44 = 0,56.

Consequently, approximately 56% of applications received by the CMO will be served.

Channel downtime probability p 0