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

Queuing systems – these are systems that receive requests for service at random times, and the received requests are serviced using the service channels available to the system.

Examples of queuing systems include:

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

	Nodes	Requirements
Hospital	Orderlies	Patients
Production
Airport	Exits to runways Registration points	Passengers

Let's consider the operation diagram of the QS (Fig. 1). The system consists of a request generator, a dispatcher and a service unit, a failure accounting unit (terminator, order destroyer). Service center in general case may have several service channels.

Rice. 1

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

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

1. Queue – application accumulator. There may be no queue.
2. Service center consists of a finite number of service channels. Each channel has 3 states: free, busy, not working. If all channels are busy, then you can come up with a strategy for who to transfer the request to.
3. Refusal from service occurs if all channels are busy (some of them may not work).

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

terminator – destroyer of transactions;

warehouse – storage of resources and finished products;

check accounting– to perform operations such as “wiring”;

manager – resource manager;

Classification of SMO

First division (based on the presence of queues):

• QS with failures;
• SMO with a queue.

IN QS with failures an application received at a time when all channels are busy is rejected, leaves the QS and is not serviced in the future.

IN Queue with queue an application that arrives at a time when all channels are busy does not leave, but gets in a queue and waits for the opportunity to be served.

QS with queues are divided into different types depending on how the queue is organized - limited or unlimited. Restrictions may concern both the length of the queue and the waiting time, “service discipline”.

So, for example, the following QSs are considered:

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

Types of queue restrictions can be combined.

Another classification divides the CMO according to the source of applications. Applications (requirements) can be generated by the system itself or by some external environment, existing independently of the system.

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

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

In an open QS, the characteristics of the flow of applications do not depend on the state of the QS itself (how many channels are occupied). In a closed QS - they depend. For example, if one worker services a group of machines that require adjustment from time to time, then the intensity of the flow of “demands” from the machines depends on how many of them are already operational and awaiting adjustment.

An example of a closed system: a cashier issuing wages at an enterprise.

Based on the number of channels, QSs are divided into:

• single-channel;
• multichannel.

Characteristics of a queuing system

The main characteristics of any type of queuing system are:

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

Input Requirements Stream

To describe the input stream, you need to specify a probabilistic law that determines the sequence of moments when requests for service are received, and indicate the number of such requirements in each subsequent receipt. In this case, as a rule, they operate with the concept of “probabilistic distribution of the moments of receipt of requirements.” Here they can do the following: individual and group requirements (the number of such requirements in each regular receipt). In the latter case, usually we're talking about about a service system with parallel-group service.

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

E(A)– average (MO) arrival time;

λ=1/E(A)– intensity of receipt of demands;

Input Stream Characteristics:

1. A probabilistic law that determines the sequence of moments when requests for service are received.
2. The number of requests in each next arrival for group flows.

Queue discipline

Queue – a set of requirements awaiting service.

The queue has a name.

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

• first come, first served;

first in first out (FIFO)

the most common type of queue.

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

The list has a beginning and an end. The list consists of entries. A record is a list cell. The application arrives at the end of the list, and is selected for service from the beginning of the list. The record consists of characteristics of the application and a link (indicator of who is behind it). In addition, if the queue has a waiting time limit, then the maximum waiting time must also be indicated.

As programmers, you should be able to make two-way, one-way lists.

List actions:

• insert into the tail;
• take from the beginning;
• remove from the list after the timeout expires.
• Last to arrive - first to be served LIFO (cartridge clip, dead end at a train station, walked into a crowded car).

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

• random selection of applications;
• selection of applications based on priority criteria.

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

Queue characteristics

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

Service Mechanism

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

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

To analytically describe the characteristics of a service procedure, the concept of “probabilistic distribution of time for servicing requirements” is used.

S i– service time i-th requirement;

E(S)– average service time;

μ=1/E(S)– speed of servicing requests.

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

QS utilization rate

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

ρ=λ/( Nμ) – called coefficient of utilization of QS , shows how much system resources are used.

Service system structure

The structure of the service system is determined by the number and relative position of service channels (mechanisms, devices, etc.). First of all, it should be emphasized that a service system may have more than one service channel, but several; This type of system is capable of serving multiple requirements simultaneously. In this case, all service channels offer the same services, and therefore it can be argued that parallel service .

Example. Cash registers in the store.

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

Example. Medical commission.

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

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

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

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

As main criteria for the effectiveness of queuing systems Depending on the nature of the problem being solved, the following may appear:

• probability of immediate servicing of an incoming application (P obsl = K obs / K post);
• probability of refusal to service an incoming application (P open = K open / K post);

Obviously, P obsl + P open =1.

Flows, delays, maintenance. Pollacheck–Khinchin formula

Delay – one of the criteria for servicing the QS is the time spent by the application waiting for service.

D i– delay in request queue i;

W i =D i +S i– time required in the system i.

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

(with probability 1) – the established average time the requirement is in the QS (waiting).

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

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

Then the indicators (if they exist)

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

(with probability 1) – the steady-state average number of demands in the system over time.

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

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

To the most general and desired results for queuing systems the conservation equations are

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

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

• absolute system capacity – А=Р obsl *λ;
• relative system capacity –

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

.

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

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

The subject of queuing theory is to establish a relationship between the factors that determine the functionality of the queuing system and the efficiency of its operation. In most cases, all parameters describing queuing systems are random variables or functions, therefore these systems belong to stochastic systems.

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

Moscow State Technical University

named after N.E. Bauman (Kaluga branch)

Department of Higher Mathematics

Course work

in the course "Operations Research"

Simulation modeling of a queuing system

Work assignment: Create a simulation model and calculate the performance indicators of a queuing system (QS) with the following characteristics:

Number of service channels n; maximum length queue t;

The flow of applications entering the system is the simplest with an average intensity λ and an exponential law of time distribution between the receipt of applications;

The flow of requests served in the system is the simplest with an average intensity µ and an exponential distribution law of service time.

Compare the found indicator values ​​with the results. obtained by numerically solving the Kolmogorov equation for the probabilities of system states. The values ​​of the QS parameters are given in the table.

Introduction

Chapter 1. Main characteristics of CMOs and indicators of their effectiveness

1.1 The concept of a Markov random process

1.2 Event streams

1.3 Kolmogorov equations

1.4 Final probabilities and QS state graph

1.5 Performance indicators of the QS

1.6 Basic concepts of simulation modeling

1.7 Construction of simulation models

Chapter 2. Analytical modeling of QS

2.1 System state graph and Kolmogorov equations

2.2 Calculation of system efficiency indicators based on final probabilities

Chapter 3. Simulation modeling of QS

3.1 Algorithm of the QS simulation method (step-by-step approach)

3.2 Program flowchart

3.3 Calculation of QS efficiency indicators based on the results of its simulation modeling

3.4 Statistical processing of results and their comparison with the results of analytical modeling

Conclusion

Literature

Annex 1

When researching operations, one often encounters systems designed for reusable use when solving similar problems. The processes that arise are called service processes, and the systems are called queuing systems (QS).

Each QS consists of a certain number of service units (instruments, devices, points, stations), which are called service channels. Channels can be communication lines, work points, computers, sellers, etc. Based on the number of channels, QS systems are divided into single-channel and multi-channel.

Applications are usually received by the QS not regularly, but randomly, forming a so-called random flow of applications (requirements). Service of applications also continues for some random time. The random nature of the flow of requests and service time leads to the fact that the QS is unevenly loaded: in some periods of time a very large number of a large number of requests (they either queue up or leave the QS unserved); in other periods, the QS works with underload or is idle.

The subject of queuing theory is the construction mathematical models, linking the specified operating conditions of the QS (number of channels, their productivity, nature of the flow of requests, etc.) with performance indicators of the QS, describing its ability to cope with the flow of requests.

The following are used as indicators of the effectiveness of the QS:

Absolute system capacity (A), i.e. average number of applications served per unit of time;

Relative capacity (Q), i.e. the average share of received applications serviced by the system;

Probability of request service failure (

);

Average number of busy channels (k);

Average number of applications to the CMO (

);

Average time an application stays in the system (

);

Average number of applications in queue (

);

Average time an application spends in queue (

);

Average number of applications served per unit of time;

Average waiting time for service;

The probability that the number of applications in the queue will exceed a certain value, etc.

QS is divided into 2 main types: QS with failures and QS with waiting (queue). In a QS with refusals, an application received at a time when all channels are busy receives a refusal, leaves the QS and does not participate in the further service process (for example, an application for a telephone conversation at a time when all channels are busy, receives a refusal and leaves the QS unserved) . In a waiting QS, a request that arrives at a time when all channels are busy does not leave, but becomes queued for service.

One of the methods for calculating QS efficiency indicators is the simulation method. Practical use computer simulation involves the construction of an appropriate mathematical model that takes into account uncertainty factors, dynamic characteristics and the entire complex of relationships between the elements of the system being studied. Simulation modeling of system operation begins with some specific initial state. Due to the implementation of various events of a random nature, the system model transitions at subsequent times to its other possible states. This evolutionary process continues until the final moment of the planning period, i.e. until the final point of the simulation.

Let there be some system that changes its state randomly over time. In this case, they say that a random process is occurring in the system.

A process is called a discrete state process if its states

can be listed in advance and the transition of the system from one state to another occurs abruptly. A process is called a continuous-time process if the system transitions from state to state occur instantly.

The QS operation process is a random process with discrete states and continuous time.

A random process is called a Markov or random process without aftereffect if for any moment of time

the probabilistic characteristics of the process in the future depend only on its state in this moment and do not depend on when and how the system came to this state.

1.2 Event streams

A stream of events is a sequence of homogeneous events following one after another at random times.

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

The flow of events is called regular if events follow one another at certain equal intervals of time.

A flow 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:

.

A flow of events is called ordinary if the probability of occurrence is within a small period of time

two or more events is small compared to the probability of hitting one event, that is, if events appear in it individually and not in groups.

A flow of events is called a flow without aftereffect if for any two non-overlapping time periods

INTRODUCTION

CHAPTER I. FORMULATION OF QUEUE SERVICE PROBLEMS

1.1 General concept queuing theory

1.2 Modeling of queuing systems

1.3 QS state graphs

1.4 Random processes

Chapter II. EQUATIONS DESCRIBING QUEUE SYSTEMS

2.1 Kolmogorov equations

2.2 Processes of “birth - death”

2.3 Economic and mathematical formulation of queuing problems

Chapter III. MODELS OF QUEUING SYSTEMS

3.1 Single-channel QS with denial of service

3.2 Multi-channel QS with denial of service

3.3 Model of a multiphase tourist service system

3.4 Single-channel QS with limited queue length

3.5 Single-channel QS with unlimited queue

3.6 Multi-channel QS with limited queue length

3.7 Multi-channel QS with unlimited queue

3.8 Analysis of the supermarket queuing system

CONCLUSION

Introduction

Currently, a large amount of literature has appeared devoted directly to the theory of queuing, the development of its mathematical aspects, as well as various areas of its application - military, medical, transport, trade, aviation, etc.

Queuing theory is based on the theory of probability and mathematical statistics. The initial development of queuing theory is associated with the name of the Danish scientist A.K. Erlang (1878-1929), with his works in the field of design and operation of telephone exchanges.

Queuing theory is a field of applied mathematics that deals with the analysis of processes in production, service, and management systems in which homogeneous events are repeated many times, for example, in consumer service enterprises; in systems for receiving, processing and transmitting information; automatic production lines, etc. A great contribution to the development of this theory was made by Russian mathematicians A.Ya. Khinchin, B.V. Gnedenko, A.N. Kolmogorov, E.S. Wentzel et al.

The subject of queuing theory is to establish dependencies between the nature of the flow of requests, the number of service channels, the performance of an individual channel and effective service in order to find the best ways to manage these processes. The problems of queuing theory are of an optimization nature and ultimately include the economic aspect of determining a system option that will ensure a minimum of total costs from waiting for service, loss of time and resources for service, and downtime of service channels.

In commercial activities, the application of queuing theory has not yet found the desired distribution.

This is mainly due to the difficulty of setting tasks, the need for a deep understanding of the content of commercial activities, as well as reliable and accurate tools that allow one to calculate various options for the consequences of management decisions in commercial activities.

Chapter I . Setting queuing tasks

1.1 General concept of queuing theory

The nature of mass services, in various fields, is very subtle and complex. Commercial activity is associated with the performance of many operations at the stages of movement, for example, the mass of goods from the sphere of production to the sphere of consumption. Such operations are loading of goods, transportation, unloading, storage, processing, packaging, and sales. In addition to such basic operations, the process of movement of goods is accompanied by a large number of preliminary, preparatory, accompanying, parallel and subsequent operations with payment documents, containers, money, cars, clients, etc.

The listed fragments of commercial activity are characterized by the massive arrival of goods, money, and visitors at random times, then their sequential servicing (satisfying demands, requests, applications) by performing appropriate operations, the execution time of which is also random. All this creates unevenness in work, gives rise to underloads, downtime and overloads in commercial operations. Queues cause a lot of trouble, for example, for visitors in cafes, canteens, restaurants, or car drivers at commodity depots waiting for unloading, loading or paperwork. In this regard, the tasks arise of analyzing existing options for performing the entire set of operations, for example, the sales floor of a supermarket, restaurant or in workshops for the production of own products for the purpose of assessing their work, identifying weak links and reserves for ultimately developing recommendations aimed at increasing the efficiency of commercial activities.

In addition, other tasks arise related to the creation, organization and planning of a new economical, rational option for performing many operations within the trading floor, confectionery shop, all levels of service in a restaurant, cafe, canteen, planning department, accounting, personnel department, etc.

The tasks of organizing mass service arise in almost all spheres of human activity, for example, sellers serving customers in stores, serving visitors in public catering establishments, customer service in consumer services establishments, providing telephone conversations at the telephone exchange, rendering medical care patients in the clinic, etc. In all of the above examples, there is a need to satisfy requests large number consumers.

The listed problems can be successfully solved using methods and models of queuing theory (QST) specially created for these purposes. This theory explains that it is necessary to serve someone or something, which is defined by the concept of “service request (demand)”, and service operations are performed by someone or something called service channels (nodes). The role of requests in commercial activities is played by goods, visitors, money, auditors, documents, and the role of service channels is played by sellers, administrators, cooks, confectioners, waiters, cashiers, merchandise experts, loaders, commercial equipment, etc. It is important to note that in one embodiment, for example, a cook in the process of preparing dishes is a service channel, and in another he acts as a request for service, for example to the production manager to receive goods.

Applications, due to the massive number of receipts for servicing, form flows that are called incoming before servicing operations are performed, and after a possible wait for the start of servicing, i.e. idle time in the queue form service flows in the channels, and then an outgoing flow of requests is formed. In general, the combination of elements of the incoming flow of requests, a queue, service channels and the outgoing flow of requests forms the simplest single-channel queuing system - QS.

A system is understood as a set of interconnected systems. purposefully interacting parts (elements). Examples of such simple QS in commercial activities are places for receiving and processing goods, payment centers for customers in stores, cafes, canteens, workplaces for economists, accountants, merchants, cooks, etc.

The service procedure is considered completed when the service request leaves the system. The duration of the time interval required to implement the service procedure depends mainly on the nature of the request for service, the state of the service system itself and the service channel.

Indeed, the duration of a buyer’s stay in a supermarket depends, on the one hand, on personal qualities the buyer, his requests, the range of goods he is going to purchase, and on the other hand, the form of organization of service and service personnel, which can significantly affect the time the buyer stays in the supermarket and the intensity of service. For example, mastering the work of cashiers-controllers using the “blind” method on cash register made it possible to increase the throughput of payment nodes by 1.3 times and save time spent on settlements with customers at each checkout by more than 1.5 hours per day. The introduction of a single payment center in a supermarket provides tangible benefits to the buyer. Thus, if with the traditional form of payment the time for servicing one customer was on average 1.5 minutes, then with the introduction of a single payment unit it was 67 seconds. Of these, 44 seconds are spent on making a purchase in the section and 23 seconds directly on payments for purchases. If the buyer makes several purchases in different sections, then the loss of time is reduced when purchasing two purchases by 1.4 times, three by 1.9, five by 2.9 times.

By servicing requests we mean the process of satisfying a need. Services are varied in nature. However, in all examples, received requests require servicing by some device. In some cases, the service is performed by one person (service to the buyer by one seller, in some - by a group of people (service to a patient by a medical commission in a clinic), and in some cases - by technical devices (sale of sparkling water, sandwiches by vending machines). A set of means that service requests , is called the service channel.

If service channels are capable of satisfying identical requests, then service channels are called homogeneous. A set of homogeneous service channels is called a service system.

The queuing system receives a large number of requests at random times, the service duration of which is also a random variable. The sequential arrival of applications into the service system is called the incoming flow of applications, and the sequence of applications leaving the service system is called the outgoing flow.

The random nature of the distribution of the duration of service operations, along with the random nature of the receipt of requests for service, leads to the fact that a random process occurs in the service channels, which “can be called (by analogy with the input flow of requests) the flow of service requests or simply the flow of service.

Note that applications entering the service system may leave it without being serviced. For example, if a customer does not find the desired product in a store, he leaves the store without being served. The buyer can also leave the store if the desired product is available, but there is a long queue, and the buyer does not have time.

Queuing theory deals with the study of processes associated with queuing and the development of methods for solving typical queuing problems.

When studying the efficiency of a service system, an important role is played by various ways location in the system of service channels.

With a parallel arrangement of service channels, a request can be served by any free channel. An example of such a service system is a payment center in self-service stores, where the number of service channels coincides with the number of cashiers-controllers.

In practice, one request is often serviced sequentially by several service channels. In this case, the next service channel begins work on servicing the request after the previous channel has completed its work. In such systems, the service process is multi-phase; servicing a request through one channel is called the service phase. For example, if a self-service store has departments with sellers, then customers are first served by the sellers, and then by cashier-controllers.

The organization of the service system depends on the will of the person. In queuing theory, the quality of system functioning is understood not as how well the service is performed, but how fully loaded the service system is, whether service channels are idle, or whether a queue is forming.

In commercial activities, applications entering the queuing system also make high demands on the quality of service as a whole, which includes not only a list of characteristics that have historically developed and are considered directly in the theory of queuing, but also additional ones characteristic of the specifics of commercial activity, including in particular, individual maintenance procedures, requirements for the level of which have now increased greatly. In this regard, it is also necessary to take into account indicators of commercial activity.

The performance of the service system is characterized by the following indicators. Such as the waiting time for service to begin, the length of the queue, the possibility of receiving a refusal of service, the possibility of downtime of service channels, the cost of service and, ultimately, satisfaction with the quality of service, which also includes indicators of commercial activity. To improve the quality of operation of the service system, it is necessary to determine how to distribute incoming requests between service channels, how many service channels should be available, how to arrange or group service channels or service devices to improve business performance. To solve these problems there is effective method modeling, including and combining the achievements of various sciences, including mathematics.

1.2 Modeling of queuing systems

Transitions of a QS from one state to another occur under the influence of very specific events - the receipt of applications and their servicing. The sequence of events occurring one after another at random times forms the so-called flow of events. Examples of such flows in commercial activities are flows of various natures - goods, money, documents, transport, clients, buyers, telephone calls, negotiations. The behavior of a system is usually determined not by one, but by several streams of events. For example, customer service in a store is determined by the flow of customers and the flow of service; in these flows, the moments when customers appear, the waiting time in line, and the time spent serving each customer are random.

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

A flow of events is called regular if events follow one another at predetermined and strictly defined intervals. This flow is ideal and is very rarely encountered in practice. More often there are irregular flows that do not have the property of regularity.

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

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

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

Let us consider a certain time interval t on the time axis. Let us assume that the probability of a random event falling into this interval is p, and the total number of possible events is n. If there is a property of the ordinary flow of events, the probability p should be a sufficiently small value, and i should be a sufficiently small value a large number, since mass phenomena are considered. Under these conditions, to calculate the probability of a certain number of events m occurring in a time period t, you can use the Poisson formula:

P m, n = a m_e -a; (m=0,n),

where the value a = pr is the average number of events falling within a time period t, which can be determined through the intensity of the flow of events X as follows: a= λ τ

The dimension of the flow intensity X is the average number of events per unit time. There is the following relationship between n and λ, p and τ:

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

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

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

F(t)=1-P 0 =1-(a 0 *e -a)0!=1-e -Xt ,t≥0

For small ∆t, it is possible to obtain an approximate formula obtained by replacing the function e - Xt, with only two terms of the expansion in powers of ∆t, then the probability of at least one event occurring within a small period of time ∆t is

P(T<∆t)=1-e - λ t ≈1- ≈ λΔt

We obtain the distribution density of the time interval between two consecutive events by differentiating F(t) with respect to time,

f(t)= λe- λ t ,t≥0

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

M(T)= λ ∞ ∫ 0 t*e - λt *dt=1/ λ ; D(T)=1/ λ 2 ; σ(T)=1/ λ .

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

P k (t)=(λt) k / k! *e -λ t ,

where λ is the intensity of the flow of requests, the average number of events in the QS per unit of time, for example [person/min; rub./hour; checks/hour; document/day; kg./hour; t./year].

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

ƒ(t)= λe - λ t .

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

ƒ (t och)=V*e - v t och,

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

where T och is the average waiting time for service in the queue.

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

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

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

µ=1/ t obs [person/min; rub./hour; checks/hour; document/day; kg./hour; t./year] ,

where t obs is the average time for servicing requests.

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

In addition to the concept of the simplest stream of events, it is often necessary to use the concepts of streams of other types. A stream of events is called a Palm stream when in this stream the time intervals between successive events T 1, T 2, ..., T k ..., T n are independent, identically distributed, random variables, but unlike the simplest stream, they are not necessarily distributed according to the exponential law. The simplest flow is a special case of the Palm flow.

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

This flow is obtained by “thinning” the simplest flow. This “thinning” is carried out by selecting events from the simplest flow according to a certain rule.

For example, having agreed to take into account only every second event forming the simplest flow, we obtain a second-order Erlang flow. If we take only every third event, then a third-order Erlang flow is formed, etc.

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

Any study of a queuing system begins with studying what needs to be served, therefore, with studying the incoming flow of applications and its characteristics.

Since time moments t and time intervals of receipt of requests τ, then the duration of service operations t obs and the waiting time in the queue t och, as well as the length of the queue l och are random variables, then, therefore, the characteristics of the state of the QS are probabilistic in nature, and to describe them it is necessary apply methods and models of queuing theory.

The characteristics listed above k, τ, λ, L och, T och, v, t obs, µ, p, P k are the most common for QS, which are usually only some part of the objective function, since it is also necessary to take into account indicators of commercial activity.

1.3 QS state graphs

When analyzing random processes with discrete states and continuous time, it is convenient to use a variant of a schematic representation of the possible states of the CMO (Fig. 6.2.1) in the form of a graph with the marking of its possible fixed states. The states of the QS are usually depicted either by rectangles or circles, and the possible directions of transitions from one state to another are oriented by arrows connecting these states. For example, the labeled state graph of a single-channel system of a random service process at a newsstand is shown in Fig. 1.3.

12

Rice. 1.3. Labeled QS state graph

The system can be in one of three states: S 0 - channel is free, idle, S 1 - channel is busy with servicing, S 2 - channel is busy with servicing and one request is in the queue. The transition of the system from state S 0 to S l occurs under the influence of a simple flow of requests with intensity λ 01 , and from state S l to state S 0 the system is transferred by a service flow with intensity λ 01 . The state graph of the service system with the flow intensities indicated at the arrows is called labeled. Since the presence of a system in one state or another is probabilistic, the probability: p i (t) that the system will be in state S i at time t is called the probability of the i-th state of the QS and is determined by the number of incoming requests k for service.

The random process occurring in the system is that at random times t 0 , t 1, t 2 ,..., t k ,..., t n the system finds itself in one or another previously known discrete state sequentially. Like this. a random sequence of events is called a Markov chain if for each step the probability of transition from one state S t to any other Sj does not depend on when and how the system transitioned to state S t . A Markov chain is described using the probability of states, and they form a complete group of events, so their sum is equal to one. If the transition probability does not depend on the number k, then the Markov chain is called homogeneous. Knowing the initial state of the service system, one can find the probabilities of states for any value of the k-number of requests received for service.

1.4 Random processes

The transition of a QS from one state to another occurs randomly and is a random process. The operation of a QS is a random process with discrete states, since its possible states in time can be listed in advance. Moreover, the transition from one state to another occurs abruptly, at random times, which is why it is called a process with continuous time. Thus, the operation of a QS is a random process with discrete states and continuous; time. For example, in the process of servicing wholesale customers at the Kristall company in Moscow, all possible states of protozoa can be recorded in advance. CMO, which are included in the entire cycle of commercial services from the moment of concluding an agreement for the supply of alcoholic beverages, payment, paperwork, release and receipt of products, additional loading and removal of finished products from the warehouse.

Of the many varieties of random processes, the most widespread in commercial activity are those processes for which at any time the characteristics of the process in the future depend only on its state at the present moment and do not depend on the prehistory - on the past. For example, the possibility of receiving liquor products from the Kristall plant depends on its availability in the finished product warehouse, i.e. its condition at the moment, and does not depend on when and how other buyers received and took away these products in the past.

Such random processes are called processes without consequences, or Markov processes, in which, given a fixed present, the future state of the QS does not depend on the past. A random process occurring in a system is called a Markov random process, or a “process without consequences,” if it has the following property: for each moment of time t 0, the probability of any state t > t 0 of the system Si, - in the future (t>t Q ) depends only on its state in the present (at t = t 0) and does not depend on when and how the system came to this state, i.e. because of how the process developed in the past.

Markov random processes are divided into two classes: processes with discrete and continuous states. A process with discrete states occurs in systems that have only some fixed states, between which jump-like transitions are possible at certain, previously unknown moments in time. Let's consider an example of a process with discrete states. There are two telephones in the company's office. The following states are possible for this service system: S o -phones are free; S l - one of the phones is busy; S 2 - both phones are busy.

The process occurring in this system is that the system randomly jumps from one discrete state to another.

Processes with continuous states are characterized by a continuous smooth transition from one state to another. These processes are more typical for technical devices than for economic objects, where usually we can only approximately talk about the continuity of the process (for example, the continuous consumption of a stock of goods), while in fact the process always has a discrete nature. Therefore, further we will consider only processes with discrete states.

Markov random processes with discrete states are in turn divided into processes with discrete time and processes with continuous time. In the first case, transitions from one state to another occur only at certain, pre-fixed moments in time, while in the intervals between these moments the system maintains its state. In the second case, the transition of the system from state to state can occur at any random moment in time.

In practice, processes with continuous time are much more common, since transitions of a system from one state to another usually occur not at any fixed moments in time, but at any random moments in time.

To describe processes with continuous time, a model is used in the form of a so-called Markov chain with discrete states of the system, or a continuous Markov chain.

Chapter II . Equations describing queuing systems

2.1 Kolmogorov equations

Let's consider the mathematical description of a Markov random process with discrete states of the system S o , S l , S 2 (see Fig. 6.2.1) and continuous time. We believe that all transitions of the queuing system from state S i to state Sj occur under the influence of simple event flows with intensities λ ij , and the reverse transition under the influence of another flow λ ij ,. Let us introduce the notation pi as the probability that at time t the system is in state S i . For any moment of time t, it is fair to write down the normalization condition - the sum of the probabilities of all states is equal to 1:

Σp i (t)=p 0 (t)+ p 1 (t)+ p 2 (t)=1

Let us analyze the system at time t, specifying a small time increment Δt, and find the probability p 1 (t+ Δt) that the system at time (t+ Δt) will be in state S 1, which can be achieved in different ways:

a) the system at moment t with probability p 1 (t) was in state S 1 and for a small increment of time Δt never passed into another neighboring state - neither S 0 nor bS 2 . The system can be removed from state S 1 by the total simplest flow with intensity (λ 10 + λ 12), since the superposition of the simplest flows is also the simplest flow. On this basis, the probability of leaving state S 1 in a short period of time Δt is approximately equal to (λ 10 +λ 12)* Δt. Then the probability of not leaving this state is equal to . In accordance with this, the probability that the system will remain in the state Si based on the probability multiplication theorem is equal to:

p 1 (t);

b) the system was in the neighboring state S o and in a short time Δt passed into the state S o The transition of the system occurs under the influence of the flow λ 01 with a probability approximately equal to λ 01 Δt

The probability that the system will be in state S 1 in this version is equal to p o (t)λ 01 Δt;

c) the system was in the S 2 state and during the time Δt transitioned to the S 1 state under the influence of a flow of intensity λ 21 with a probability approximately equal to λ 21 Δt. The probability that the system will be in state S 1 is equal to p 2 (t) λ 21 Δt.

Applying the probability addition theorem for these options, we obtain the expression:

p 2 (t+Δt)= p 1 (t) + p o (t)λ 01 Δt+p 2 (t) λ 21 Δt,

which can be written differently:

p 2 (t+Δt)-p 1 (t)/ Δt= p o (t)λ 01 + p 2 (t) λ 21 - p 1 (t) (λ 10 +λ 12).

Passing to the limit at Δt-> 0, the approximate equalities will turn into exact ones, and then we obtain the first order derivative

dp 2 /dt= p 0 λ 01 +p 2 λ 21 -p 1 (λ 10 +λ 12) ,

which is a differential equation.

Carrying out reasoning in a similar way for all other states of the system, we obtain the system differential equations, which are called the equations of A.N. Kolmogorov:

dp 0 /dt= p 1 λ 10,

dp 1 /dt= p 0 λ 01 +p 2 λ 21 -p 1 (λ 10 +λ 12) ,

dp 2 /dt= p 1 λ 12 +p 2 λ 21.

There are general rules for composing Kolmogorov equations.

Kolmogorov's equations make it possible to calculate all the probabilities of the states of the QS S i as a function of time p i (t). In the theory of random processes, it is shown that if the number of states of a system is finite, and from each of them it is possible to go to any other state, then there are limiting (final) probabilities of states that indicate the average relative value of the time the system remains in this state. If the marginal probability of the state S 0 is equal to p 0 = 0.2, then, therefore, on average 20% of the time, or 1/5 of the working time, the system is in the state S o . For example, in the absence of requests for service k = 0, p 0 = 0.2,; Therefore, on average, the system is in the S o state for 2 hours a day and is idle if the working day is 10 hours.

Since the limiting probabilities of the system are constant, replacing the corresponding derivatives in Kolmogorov’s equations with zero values, we obtain a system of linear algebraic equations, describing the stationary mode of the QS. Such a system of equations is compiled using a labeled graph of QS states according to following rules: to the left of the equal sign in the equation is the limiting probability p i of the state Si in question multiplied by the total intensity of all flows outputting (outgoing arrows) of the published state Si system, and to the right of the equal sign is the sum of the products of the intensity of all flows entering (incoming arrows) into state Sisystem, on the probability of those states from which these flows come. To solve such a system, it is necessary to add one more equation that determines the normalization condition, since the sum of the probabilities of all states of the QS is equal to 1: n

For example, for a QS that has a labeled graph of three states S o , S 1 , S 2 Fig. 6.2.1, the Kolmogorov system of equations, compiled on the basis of the stated rule, has the following form:

For the state S o → p 0 λ 01 = p 1 λ 10

For state S 1 →p 1 (λ 10 +λ 12) = p 0 λ 01 +p 2 λ 21

For the state S 2 → p 2 λ 21 = p 1 λ 12

p 0 +p 1 +p 2 =1

dp 4 (t)/dt=λ 34 p 3 (t) - λ 43 p 4 (t) ,

p 1 (t)+ p 2 (t)+ p 3 (t)+ p 4 (t)=1 .

We must add initial conditions to these equations. For example, if at t = 0 the system S is in state S 1, then the initial conditions can be written as follows:

p 1 (0)=1, p 2 (0)= p 3 (0)= p 4 (0)=0 .

Transitions between QS states occur under the influence of the receipt of applications and their servicing. The transition probability if the flow of events is the simplest is determined by the probability of the event occurring during time Δt, i.e. the value of the transition probability element λ ij Δt, where λ ij is the intensity of the flow of events that transfer the system from state i to state i (along the corresponding arrow on the state graph).

If all the streams of events that transfer the system from one state to another are the simplest, then the process occurring in the system will be a Markov random process, i.e. process without consequences. In this case, the behavior of the system is quite simple, determined if the intensity of all these simplest flows of events is known. For example, if a Markov random process with continuous time occurs in a system, then by writing a system of Kolmogorov equations for state probabilities and integrating this system under given initial conditions, we obtain all state probabilities as a function of time:

p i (t), p 2 (t),…., p n (t) .

In many cases in practice it turns out that state probabilities as a function of time behave in such a way that there is

lim p i (t) = p i (i=1,2,…,n) ; t→∞

regardless of the type of initial conditions. In this case, they say that there are limiting probabilities of the states of the system at t->∞ and a certain limiting stationary regime is established in the system. In this case, the system randomly changes its states, but each of these states occurs with a certain constant probability, determined by the average time the system remains in each of the states.

It is possible to calculate the limiting probabilities of the state p i if all derivatives in the system are set equal to 0, since in the Kolmogorov equations at t-> ∞ the time dependence disappears. Then the system of differential equations turns into a system of Ordinary linear algebraic equations, which, together with the normalization condition, allows us to calculate all the limiting probabilities of states.

2.2 Processes of "birth - death"

Among homogeneous Markov processes, there is a class of random processes that are widely used in constructing mathematical models in the fields of demography, biology, medicine (epidemiology), economics, and commercial activity. These are the so-called “birth-death” processes, Markov processes with stochastic state graphs of the following form:

S 3

kjlS n

μ 0 μ 1 μ 3 μ 4 μ n-1

Rice. 2.1 Labeled graph of the “birth-death” process

This graph reproduces the well-known biological interpretation: the value λ k reflects the rate of birth of a new representative of a certain population, for example, rabbits, and the current population volume is equal to k; the value μ is the rate of death (sale) of one representative of this population if the current population volume is equal to k. In particular, the population can be unlimited (the number n of states of the Markov process is infinite but countable), the intensity λ can be equal to zero (a population without the possibility of rebirth), for example, when rabbits stop reproducing.

For the Markov “birth-death” process described by the stochastic graph shown in Fig. 2.1, we find the final distribution. Using the rules for composing equations for a finite number n of limiting probabilities of the state of the system S 1, S 2, S 3,… S k,…, S n, we will compose the corresponding equations for each state:

for the state S 0 -λ 0 p 0 =μ 0 p 1 ;

for the state S 1 -(λ 1 +μ 0)p 1 = λ 0 p 0 +μ 1 p 2, which, taking into account the previous equation for the state S 0, can be transformed to the form λ 1 p 1 = μ 1 p 2.

Similarly, you can create equations for the remaining states of the system S 2, S 3,..., S k,..., S n. As a result, we obtain the following system of equations:

By solving this system of equations, one can obtain expressions that determine the final states of the queuing system:

It should be noted that the formulas for determining the final probabilities of the states p 1, p 2, p 3,..., p n include terms that are part of the sum of the expression that determines p 0. The numerators of these terms contain the products of all intensities standing at the arrows of the state graph leading from left to right to the considered state S k , and the denominators are the products of all intensities standing at the arrows leading from right to left to the considered state S k , i.e. . μ 0, μ 1, μ 2, μ 3,… μ k. In this regard, let us write these models in a more compact form:

k=1,n

2.3 Economic and mathematical formulation of queuing problems

The correct or most successful economic and mathematical formulation of the problem largely determines the usefulness of recommendations for improving queuing systems in commercial activities.

In this regard, it is necessary to carefully monitor the process in the system, search and identify significant connections, formulate a problem, highlight the goal, determine indicators and highlight economic criteria evaluation of the performance of the QS. In this case, the most general, integral indicator can be the costs, on the one hand, of the QS of commercial activity as a service system, and on the other hand, the costs of applications, which may have a different nature in their physical content.

K. Marx ultimately viewed increasing efficiency in any field of activity as saving time and saw this as one of the most important economic laws. He wrote that saving time, as well as the planned distribution of working time across various branches of production, remains the first economic law based on collective production. This law is manifested in all spheres of social activity.

For goods, including funds entering the commercial sphere, the efficiency criterion is related to the time and speed of circulation of goods and determines the intensity of the flow of funds to the bank. Time and speed of circulation, being economic indicators of commercial activity, characterize the efficiency of using funds invested in inventory. Inventory turnover reflects average speed implementation of average inventory. Indicators of turnover and inventory levels are closely related famous models. Thus, it is possible to trace and establish the relationship between these and other indicators of commercial activity with time characteristics.

Consequently, the operational efficiency of a commercial enterprise or organization consists of the total time spent performing individual service operations, while for the population, time spent on travel, visiting a store, canteen, cafe, restaurant, waiting for service to begin, familiarizing yourself with the menu, choosing products, calculation, etc. Conducted studies of the structure of time spent by the population indicate that a significant part of it is spent irrationally. notice, that commercial activity ultimately aimed at satisfying human needs. Therefore, QS modeling efforts must include time analysis for each elementary maintenance operation. Using appropriate methods, models for connecting QS indicators should be created. This necessitates the need to link the most general and well-known economic indicators, such as turnover, profit, distribution costs, profitability and others, in economic and mathematical models with an additional emerging group of indicators determined by the specifics of service systems and introduced by the specifics of queuing theory.

For example, the features of QS indicators with failures are: waiting time for applications in the queue T och =0, since by its nature in such systems the existence of a queue is impossible, then L och =0 and, therefore, the probability of its formation P och =0. Based on the number of requests k, the operating mode of the system and its state will be determined: with k=0 – idle channels, with 1 n – maintenance and failure. The indicators of such QS are the probability of denial of service P refuse, the probability of service P obs, the average downtime of the channel t pr, the average number of busy n h and free channels n st, the average service t obs, the absolute throughput A.

For a QS with unlimited waiting, it is characteristic that the probability of servicing a request is P obs = 1, since the length of the queue and the waiting time for the start of service are not limited, i.e. formally L och →∞ and T och →∞. The following operating modes are possible in the systems: with k=0, downtime of service channels is observed, with 1 n – service and queue. Indicators of such efficiency of such QS are the average number of applications in the queue L och, the average number of applications in the system k, the average time of stay of an application in the system T cm, the absolute throughput A.

In a QS with waiting with a limit on the queue length, if the number of applications in the system is k = 0, then there is a downtime of channels, with 1 n+m - service, queue and refusal while waiting for service. Indicators of the effectiveness of such QS are the probability of denial of service P refuse - probability of service P obs, the average number of applications in the queue L och, the average number of applications in the system L cm, the average residence time of an application in the system T cm, the absolute throughput A.

Thus, the list of characteristics of queuing systems can be presented as follows: average service time – t obs; average waiting time in queue – T och; average stay in the SMO – T smo; average queue length - L och; average number of applications in SMO- L smo; number of service channels – n; intensity of the input flow of applications – λ; service intensity – μ; load intensity – ρ; load factor – α; relative throughput – Q; absolute throughput – A; share of downtime in QS – P 0 ; share of served applications – R obs; share of lost requests – P open, average number of occupied channels – n з; average number of free channels - n St; channel load factor – Кз; average downtime of channels - t pr.

It should be noted that sometimes it is enough to use up to ten key indicators to identify weaknesses and develop recommendations for improving the QS.

This is often associated with resolving issues of coordinated work chain or sets of QS.

For example, in commercial activities it is also necessary to take into account the economic indicators of the CMO: total costs - C; circulation costs - C io, consumption costs - C ip, costs of servicing one application - C 1, losses associated with the departure of an application - C y1, channel operating costs - C k, channel downtime costs - C pr, capital investments - C cap, reduced annual costs – C pr, current costs – C tek, CMO income per unit of time – D 1

In the process of setting tasks, it is necessary to reveal the interrelationships of the QS indicators, which, according to their basic affiliation, can be divided into two groups: the first is associated with the costs of handling the IO, which are determined by the number of channels occupied by servicing, the costs of maintaining the QS, the intensity of service, the degree of channel load, their efficiency usage, QS capacity, etc.; the second group of indicators is determined by the costs of the SIP applications themselves, received for service, which form the incoming flow, feel the effectiveness of the service and are associated with such indicators as the length of the queue, waiting time for service, the probability of refusal of service, the time the application remains in the service system, etc.

These groups of indicators are contradictory in the sense that improving the indicators of one group, for example, reducing the length of the queue or waiting time in line by increasing the number of service channels (waiters, cooks, porters, cashiers), is associated with a deterioration in the indicators of the group, since this can lead to increased downtime of service channels, costs of their maintenance, etc. In connection with this formalization of service tasks, it is quite natural to strive to build a QS in such a way as to establish a reasonable compromise between the performance of the requests themselves and the full use of the system’s capabilities. For this purpose, it is necessary to select a generalized, integral indicator of the effectiveness of the QS, which simultaneously includes the claims and capabilities of both groups. As such an indicator, a criterion of economic efficiency can be chosen, including both the circulation costs C io and the costs of applications C ip, which will have an optimal value with a minimum of total costs C. On this basis, the objective function of the problem can be written as follows:

C= (C io + C ip) →min

Since circulation costs include costs associated with the operation of the QS - C ex and downtime of service channels - C pr, and the costs of applications include losses associated with the departure of unserviced applications - C nz, and with staying in the queue - C och, then the objective function can be rewrite taking into account these indicators in this way:

C=((C pr n st +C ex n h)+C och R obs λ(T och +t obs)+C from R open λ)→min.

Depending on the task at hand, variable, i.e. controllable, indicators can be: number of service channels, organization of service channels (parallel, sequential, mixed), queue discipline, priority of servicing requests, mutual assistance between channels, etc. Some of the indicators in the task appears as unmanaged ones, which are usually the initial data. As an efficiency criterion in the objective function, there can also be turnover, profit, or income, for example, profitability, then the optimal values ​​of the controlled indicators of the QS are obviously found already during maximization, as in the previous version.

In some cases, you should use another option for writing the objective function:

C=(C ex n z +C pr (n-n z)+C open *P open *λ+C syst * n z )→min

For example, the level of culture of customer service at enterprises can be chosen as a general criterion, then the target function can be represented by the following model:

K ob =[(Z pu *K y)+(Z pv *K v)+(Z pv *K d)+(Z pz *K z)+(Z along *K 0)+(Z kt *K kt )]*K mp,

where Zpu is the significance of the indicator of sustainability of the product range;

K y - coefficient of stability of the product range;

Z pv – the significance of the indicator of the introduction of progressive methods of selling goods;

K in – coefficient of introduction of progressive methods of selling goods;

Zp – significance of the additional service indicator;

K d - additional service coefficient;

Z pz - the significance of the purchase completion indicator;

Kz - purchase completion rate;

3 - the significance of the indicator of time spent waiting for service;

K about – indicator of time spent waiting for service;

Z kt – the significance of the indicator of the quality of the team’s work;

Ккт – coefficient of quality of the team’s work;

KMP is an indicator of service culture in the opinion of customers;

To analyze the QS, you can choose other criteria for assessing the effectiveness of the QS. For example, as such a criterion for systems with failures, one can choose the probability of failure P failure, the value of which would not exceed a predetermined value. For example, requirement R open<0,1 означает, что не менее чем в 90% случаев система должна справляться с обслуживанием потока заявок при заданной интенсивности λ. Можно ограничить среднее время пребывания заявки в очереди или в системе. В качестве показателей, подлежащих определению, могут выступать: либо число каналов n при заданной интенсивности обслуживания μ, либо интенсивность μ при заданном числе каналов.

After constructing the objective function, it is necessary to determine the conditions for solving the problem, find restrictions, set initial values ​​of indicators, identify uncontrollable indicators, build or select a set of models for the relationship of all indicators for the analyzed type of QS, in order to ultimately find the optimal values ​​of controlled indicators, for example, the number of cooks, waiters , cashiers, loaders, storage space volumes, etc.

Chapter III . Models of queuing systems

3.1 Single-channel QS with denial of service

Let us analyze a simple single-channel QS with service failures, which receives a Poisson flow of requests with intensity λ, and servicing occurs under the influence of a Poisson flow with intensity μ.

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

Transitions of the QS from one state S 0 to another S 1 occur under the influence of the input flow of requests with intensity λ, and the reverse transition occurs under the influence of the service flow with intensity μ.

S 0

S 1

S 0 – service channel is free; S 1 – channel is busy with service;

Rice. 3.1 Labeled state graph of a single-channel QS

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

Where do we get the differential equation for determining the probability p 0 (t) of the state S 0:

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

In this case, the differential leveling solution allows us to determine the probability that the channel is free and not occupied by service:

Then it is easy to obtain an expression for the probability of determining the probability of channel occupancy:

The probability p 0 (t) decreases over time and in the limit as t→∞ tends to the value

and the probability p 1 (t) at the same time increases from 0, tending in the limit as t→∞ to the value

These probability limits can be obtained directly from the Kolmogorov equations, provided

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

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

Probability p 0 (t) determines the relative capacity of the QS, which determines the proportion of serviced applications in relation to the total number of incoming applications per unit time.

Indeed, p 0 (t) is the probability that a request arriving at time t will be accepted for service. In total, an average of λ applications arrive per unit time, and λр 0 applications are serviced.

Then the share of serviced applications in relation to the entire flow of applications will be determined by the value

In the limit at t→∞, practically already at t>3τ the value of the relative throughput will be equal to

The absolute throughput, which determines the number of requests served per unit of time in the limit at t→∞, is equal to:

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

and the total number of unserved applications is equal to

Examples of single-channel QS with service denials are: an order desk in a store, a control room of a motor transport enterprise, a warehouse office, a management office of a commercial company, with which communication is established by telephone.

3.2 Multi-channel QS with denial of service

In commercial activities, examples of multi-channel QS are the offices of commercial enterprises with several telephone channels; a free help desk for the availability of the cheapest cars in auto stores in Moscow has 7 telephone numbers, and, as is known, it is very difficult to call and get help.

Consequently, auto stores lose customers, the opportunity to increase the number of cars sold and sales revenue, turnover, and profit.

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

Let's consider a multi-channel QS with service denials in Fig. 3.2, the input of which is a Poisson flow of requests with intensity λ.

S 0

S 1

S k

S n

μ 2μkμ (k+1)μ nμ

Rice. 3.2. Labeled state graph of a multichannel QS with failures

The service flow in each channel has an intensity μ. Based on the number of QS requests, its states S k are determined, presented in the form of a labeled graph:

S 0 – all channels are free k=0,

S 1 – only one channel is occupied, k=1,

S 2 – only two channels are occupied, k=2,

S k – k channels are occupied,

S n – all n channels are occupied, k= n.

The states of a multichannel QS change abruptly at random times. The transition from one state, for example S 0 to S 1, occurs under the influence of the input flow of requests with intensity λ, and vice versa - under the influence of the flow of servicing requests with intensity μ. For the system to transition from state S k to S k -1, it does not matter which channel is released, therefore the flow of events that transfers the QS has an intensity kμ, therefore, the flow of events that transfers the system from S n to S n -1 has an intensity nμ . This is how the classic Erlang problem is formulated, named after the Danish engineer, mathematician and founder of queuing theory.

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

.

By calculating all the probabilities of states of an n-channel QS with failures p 0, p 1, p 2, ..., p k,..., p n, you can find the characteristics of the service system.

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

k=n.

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

P open + P obs = 1

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

Q = P obs = 1-P open =1-P n

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

The probability of service, or the proportion of requests served, determines the relative capacity of the QS, which can be determined using another formula:

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

The occupancy rate of channels by service is determined by the ratio of the average number of occupied channels to their total number

The probability of channels being occupied by service, which takes into account the average busy time t busy and idle time t pr channels, is determined as follows:

From this expression you can determine the average downtime of channels

The average time a request stays in the system in steady state is determined by Little’s formula

T smo = n s /λ.

3.3 Model of a multiphase tourist service system

In real life, the tourist service system looks much more complicated, so it is necessary to detail the formulation of the problem, taking into account the requests and requirements of both clients and travel agencies.

To increase the efficiency of a travel agency, it is necessary to model the overall behavior of a potential client from the beginning of the operation to its completion. The structure of the relationship between the main queuing systems actually consists of different types of QS (Fig. 3.3).

Search Selection Selection Solution

referent

search for tour company by tour

Payment Flight Exodus

Rice. 3.3 Model of a multiphase tourist service system

The problem from the point of view of mass servicing of tourists going on vacation is to determine the exact vacation spot (tour) that is adequate to the requirements of the applicant, corresponding to his health and financial capabilities and ideas about vacation in general. In this he can be assisted by travel agencies, the search for which is usually carried out from advertising messages of SMO r, then after choosing a company, he receives consultations by phone SMO t, after a satisfactory conversation, he arrives at the travel agency and receives more detailed consultations in person with the referent, then pays for the trip and receives service from the airline for the CMO flight and ultimately service at the CMO hotel 0 0 . Further development of recommendations for improving the work of the company’s QS is associated with a change in the professional content of negotiations with clients over the phone. To do this, it is necessary to deepen the analysis related to the detailing of the dialogue between the assistant and the clients, since not every telephone conversation leads to the conclusion of an agreement for the purchase of a voucher. The formalization of the service task indicated the need to form a complete (necessary and sufficient) list of characteristics and their exact meanings of the subject of a commercial transaction. Then these characteristics are ranked, for example by the method of paired comparisons, and placed in the dialogue according to the degree of their importance, for example: season (winter), month (January), climate (dry), air temperature (+25 "C), humidity (40 %), geographical location (closer to the equator), flight time (up to 5 hours), transfer, country (Egypt), city (Hurghada), sea (Red), sea water temperature (+23°C), hotel rank ( 4 stars, working air conditioning, guarantee of shampoo in the room), distance from the sea (up to 300 m), distance from shops (nearby), distance from discos and other noise sources (farther away, silence while sleeping in the hotel), food (Swedish table - breakfast, dinner, frequency of menu changes per week), hotels (Princes, Marlin-In, Hour-Palace), excursions (Cairo, Luxor, coral islands, scuba diving), entertainment shows, sports games, tour price, form of payment , contents of insurance, what to take with you, what to buy on the spot, guarantees, penalties.

There is another very significant indicator that is beneficial for the client, which the discerning reader is invited to establish independently. Then, using the method of pairwise comparison of the listed characteristics x i, you can form an n x n comparison matrix, the elements of which are filled in sequentially row by row according to the following rule:

0, if the characteristic is less significant,

and ij = 1, if the characteristic is equivalent,

2 if the characteristic is dominant.

After this, the values ​​of the sums of estimates for each indicator of the line S i =∑a ij are determined, the weight of each characteristic M i = S i /n 2 and, accordingly, the integral criterion, on the basis of which it is possible to select a travel agency, tour or hotel, according to the formula

F = ∑ M i * x i -» max.

In order to eliminate possible errors in this procedure, for example, a 5-point rating scale is introduced with a gradation of characteristics B i (x i) according to the principle worse (B i = 1 point) - better (B i = 5 points). For example, the more expensive the tour, the worse, the cheaper it is, the better. On this basis, the objective function will have a different form:

F b = ∑ M i * B i * x i -> max.

Thus, it is possible, based on the use of mathematical methods and models, using the advantages of formalization, to formulate the statement of tasks more accurately and more objectively and significantly improve the performance of QS in commercial activities to achieve the goals.

3.4 Single-channel QS with limited queue length

In commercial activities, QS with waiting (queuing) is more common.

Let's consider a simple single-channel QS with a limited queue, in which the number of places in the queue m is a fixed value. Consequently, an application received at a time when all places in the queue are occupied is not accepted for service, does not join the queue and leaves the system.

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

S m

S 3

S 2

S 1

S 0

λ λλλ... λ

μ μμμ... μ

Rice. 3.4. Labeled graph of the “birth - death” process of service; all intensities of service flows are equal

The states of the QS can be represented as follows:

S 0 - service channel is free,

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

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

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

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

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

p 1 = ρ * ρ o

p 2 =ρ 2 * ρ 0

p k =ρ k * ρ 0

P m+1 = p m=1 * ρ 0

p 0 = -1

The expression for p 0 can be written more simply in this case, using the fact that the denominator contains a geometric progression relative to p, then after appropriate transformations we obtain:

ρ= (1- ρ )

This formula is valid for all p other than 1, but if p = 1, then p 0 = 1/(t + 2), and all other probabilities are also equal to 1/(t + 2). If we assume m = 0, then we move from considering a single-channel QS with waiting to the already considered single-channel QS with denials of service. Indeed, the expression for the marginal probability p 0 in the case m = 0 has the form:

p o = μ / (λ+μ)

And in the case of λ = μ it has the value p 0 = 1 / 2.

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

An application is rejected if it arrives at a time when the QS is already in state S m +1 and, therefore, all places in the queue are occupied and one channel is serving. Therefore, the probability of failure is determined by the probability of occurrence

States S m +1:

P open = p m +1 = ρ m +1 * p 0

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

Q = 1- p open = 1- ρ m+1 * p 0

absolute throughput is:

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

The random variable takes the following integer values ​​only:

1 - there is one application in the queue,

2 - there are two applications in the queue,

t-all the places in the queue are occupied

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

k	1	2	m
p i	p2	p 3	p m+1

The mathematical expectation of this random variable is:

L och = 1* p 2 +2* p 3 +...+ m* p m +1

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

Lp = p 2 * 1- p m * (m-m*p+1)* p 0

In the special case when p = 1, when all probabilities p k are equal, you can use the expression for the sum of the terms of the number series

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

Then we get the formula

L’ och = m(m+1)* p 0 = m(m+1)(p=1).

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

T och = L och /A (for p ≠ 1) and T 1 och = L’ och /A (for p = 1).

This result, when it turns out that T och ~ 1/ λ, may seem strange: with an increase in the intensity of the flow of applications, the length of the queue seems to increase and the average waiting time decreases. However, it should be borne in mind that, firstly, the value of L och is a function of λ and μ and, secondly, the QS under consideration has a limited queue length of no more than m applications.

An application received by the QS at a time when all channels are busy is rejected, and, therefore, its “waiting” time in the QS is zero. This leads in the general case (for p ≠ 1) to a decrease in T with increasing λ, since the proportion of such requests increases with increasing λ.

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

p k =р k *(1 - р)

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

L och = p 2 1-p

and the average waiting time according to Little's formula

T och = L och /A

In the limit p<< 1 получаем Т оч = ρ / μт.е. среднее время ожидания быстро уменьшается с увеличением интенсивности потока обслуживания. В противном случае при р ≥ 1 оказывается, что в СМО отсутствует установившийся режим. Обслуживание не успевает за потоком заявок, и очередь неограниченно растет со временем (при t → ∞). Предельные вероятности состояний поэтому не могут быть определены: при Q= 1 они равны нулю. Фактически СМО не выполняет своих функций, поскольку она не в состоянии обслужить все поступающие заявки. Нетрудно определить, что доля обслуживаемых заявок и абсолютная пропускная способность соответственно составляют в среднем ρ и μ, однако неограниченное увеличение очереди, а следовательно, и времени ожидания в ней приводит к тому, что через некоторое время заявки начинают накапливаться в очереди на неограниченно долгое время.

As one of the characteristics of the QS, the average time T cm of a request's stay in the QS is used, including the average time spent in queue and the average service time. This value is calculated using Little’s formulas: if the queue length is limited, the average number of applications in the queue is equal to:

L cm= m +1 ;2

T smo= L smo; at p ≠1

Then the average time a request stays in the queuing system (both in queue and under service) is equal to:

T smo= m +1 at p ≠1 2μ

3.5 Single-channel QS with unlimited queue

In commercial activities, for example, a commercial director acts as a single-channel CMO with unlimited waiting, since he, as a rule, is forced to service requests of various natures: documents, telephone conversations, meetings and conversations with subordinates, representatives of the tax inspectorate, police, commodity experts, marketers, product suppliers and solve problems in the commodity-financial sphere with a high degree of financial responsibility, which is associated with the mandatory fulfillment of requests that sometimes impatiently await the fulfillment of their requirements, and errors of incorrect service are, as a rule, very economically significant.

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

The length of the queue is the number of goods intended for sale. In this situation, sellers act as channels servicing goods. If the number of goods intended for sale is large, then in this case we are dealing with a typical case of QS with waiting.

Let's consider the simplest single-channel QS with waiting for service, which receives a Poisson flow of requests with intensity λ and service intensity µ.

Moreover, a request received at a time when the channel is busy with servicing is put in a queue and awaits service.

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

The number of possible states is infinite:

The channel is free, there is no queue, ;

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

Channel busy, one request in queue, ;

The channel is busy, the application is in queue.

Models for estimating the probability of QS states with an unlimited queue can be obtained from the formulas allocated for QS with an unlimited queue by passing to the limit as m→∞:

Rice. 3.5 State graph of a single-channel QS with an unlimited queue.

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

there is a geometric progression with the first term 1 and the denominator . Such a sequence is the sum of an infinite number of terms at . This sum converges if the progression, which decreases infinitely at , which determines the steady-state operating mode of the QS, with the queue at can grow to infinity over time.

Since in the QS under consideration there is no restriction on the length of the queue, any request can be served, therefore, therefore, the relative throughput, respectively, and the absolute throughput

The probability of k applications being in the queue is:

;

Average number of applications in queue –

Average number of applications in the system –

;

Average time an application stays in the system –

;

The average time an application stays in the system is

.

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

3.6 Multi-channel QS with limited queue length

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

All channels are free;

Only one channel (any) is occupied;

Only two channels (any) are occupied;

All channels are busy.

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

All channels are busy and one application is in queue,

All channels are busy and two requests are in queue,

All channels and all places in the queue are occupied,

State graph of an n-channel QS with a queue limited by m places in Fig. 3.6

Rice. 3.6 State graph of an n-channel QS with a limitation on queue length m

The transition of the QS to a state with large numbers is determined by the flow of incoming requests with an intensity , while according to the condition, identical channels with an equal service flow intensity for each channel take part in servicing these requests. In this case, the total intensity of the service flow increases with the connection of new channels up to a state when all n channels are busy. With the appearance of the queue, the service intensity increases further, since it has already reached the maximum value equal to .

Let us write down expressions for the limiting probabilities of states:

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

The formation of a queue is possible when a newly received application finds at least the requirements in the system, i.e. when there are requirements in the system. These events are independent, so the probability that all channels are busy is equal to the sum of the corresponding probabilities. Therefore, the probability of a queue being formed is:

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

The relative throughput will be equal to:

Absolute throughput –

Average number of busy channels –

Average number of idle channels –

Channel occupancy (use) factor –

Channel downtime ratio –

Average number of applications in queues –

If , this formula takes a different form -

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

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

3.7 Multi-channel QS with unlimited queue

Let's consider a multi-channel QS with waiting and an unlimited queue length, which receives a flow of requests with intensity and which has a service intensity of each channel. The labeled state graph is shown in Figure 3.7. It has an infinite number of states:

S - all channels are free, k=0;

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

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

S - all n channels are busy, k=n, no queue;

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

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

We obtain the state probabilities from the formulas for a multichannel QS with a limited queue when passing to the limit at m. It should be noted that the sum of the geometric progression in the expression for p diverges at the load level p/n>1, the queue will increase indefinitely, and at p/n<1 ряд сходится, что определяет установившийся стационарный режим работы СМО.

No queue

…

…

Fig. 3.7 Labeled state graph of a multi-channel QS

with unlimited queue

for which we define expressions for the limiting probabilities of states:

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

average number of applications in queue –

average waiting time in queue –

average number of applications to the CMO –

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

This probability determines the average percentage of service channel downtime. Probability of being busy servicing k requests –

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

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

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

The average number of applications in the queue and awaiting service is:

Average waiting time for an application in the queue according to Little’s formula: and in the system

average number of channels occupied by service:

average number of free channels:

service channel occupancy ratio:

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

3.8 Analysis of the supermarket queuing system

One of the important tasks of commercial activity is the rational organization of the trade and technological process of mass services, for example in a supermarket. In particular, determining the capacity of a retail outlet's cash register is not an easy task. Such economic and organizational indicators as the turnover load per 1 m 2 of retail space, the throughput of the enterprise, the time spent by customers in the store, as well as indicators of the level of technological solution of the trading floor: the ratio of the areas of self-service zones and the payment center, the coefficients of installation and exhibition areas, in many ways determined by the throughput of the cash register. In this case, the capacity of two service zones (phases): the self-service zone and the settlement node zone (Fig. 4.1).

SMO

SMO

Intensity of incoming customer flow;

Intensity of arrival of customers in the self-service area;

Intensity of customers arriving at the payment center;

Service flow intensity.

Fig.4.1. Model of a two-phase QS system for a supermarket trading floor

The main function of the settlement center is to ensure high throughput of customers in the sales area and create a comfortable customer service. Factors affecting the throughput of a computational node can be divided into two groups:

1) economic and organizational factors: the system of financial liability in the supermarket; average cost and structure of one purchase;

2) organizational structure of the cash register;

3) technical and technological factors: the types of cash registers and cash registers used; customer service technology used by the cashier; correspondence of the capacity of the cash register to the intensity of customer flows.

Of the listed groups of factors, the greatest influence is exerted by the organizational structure of the cash register and the correspondence of the capacity of the cash register to the intensity of customer flows.

Let's consider both phases of the service system:

1) choice of goods by customers in the self-service area;

2) customer service in the settlement area. The incoming flow of customers enters the self-service phase, and the buyer independently selects the product units he needs, forming them into a single purchase. Moreover, the time of this phase depends on how the product zones are mutually located, what front they have, how much time the buyer spends choosing a specific product, what the purchase structure is, etc.

The outgoing flow of customers from the self-service area is at the same time an incoming flow into the cash register area, which sequentially includes waiting for the buyer in line and then being served by the cashier. The cash register can be considered as a service system with losses or as a service system with waiting.

However, neither the first nor the second considered systems allow us to really describe the service process at the cash register of a supermarket for the following reasons:

in the first option, the cash register unit, the power of which will be designed for a system with losses, requires significant both capital investments and current costs for the maintenance of cashier controllers;

in the second option, the cash register unit, the power of which will be designed for a system with expectations, leads to a large waste of time for customers waiting for service. At the same time, during peak hours, the checkout area “overflows” and the queue of customers “flows” into the self-service area, which violates the normal conditions for other customers to select goods.

In this regard, it is advisable to consider the second phase of service as a system with a limited queue, intermediate between a system with waiting and a system with losses. It is assumed that no more than L can be in the system at the same time, and L=n+m, where n is the number of customers served at the cash desks, m is the number of customers standing in line, and any m+1 application leaves the system unserved.

This condition makes it possible, on the one hand, to limit the area of ​​the checkout area, taking into account the maximum permissible queue length, and, on the other, to introduce a limit on the time customers wait for service at the cash desk, i.e. take into account consumer consumption costs.

The validity of setting the problem in this form is confirmed by surveys of customer flows in supermarkets, the results of which are given in Table. 4.1, the analysis of which revealed a close relationship between the average long queue at the cash register and the number of customers who did not make purchases.

Opening hours	Day of the week
	Friday			Saturday			Sunday
	queue,	quantity buyers no shopping		queue,	quantity buyers no shopping		queue,	quantity buyers no shopping
		people	%		people	%		people	%
from 9 to 10	2	38	5	5	60	5,4	7	64	4,2
from 10 to 11	3	44	5,3	5	67	5	6	62	3,7
from 11 to 12	3	54	6,5	4	60	5,8	7	121	8,8
from 12 to 13	2	43	4,9	4	63	5,5	8	156	10
from 14 to 15	2	48	5,5	6	79	6,7	7	125	6,5
from 15 to 16	3	61	7,3	6	97	6,4	5	85	7,2
from 16 to 17	4	77	7,1	8	140	9,7	5	76	6
from 17 to 18	5	91	6,8	7	92	8,4	4	83	7,2
from 18 to 19	5	130	7,3	6	88	5,9	7	132	8
from 19 to 20	6	105	7,6	6	77	6
from 20 to 21	6	58	7	5	39	4,4
Total	749	6,5	862	6,3	904	4,5

There is one more important feature in the organization of the cash desk of a supermarket, which significantly affects its throughput: the presence of express checkouts (for one or two purchases). A study of the structure of the flow of customers in supermarkets by type of cash service shows that the turnover flow is 12.9% (Table 4.2).

Days of the week	Customer flows			Trade turnover
	Total	by express checkout	% to daily flow	Total	by express checkout	% to daily turnover
Summer period
Monday	11182	3856	34,5	39669,2	3128,39	7,9
Tuesday	10207	1627	15,9	38526,6	1842,25	4,8
Wednesday	10175	2435	24	33945	2047,37	6
Thursday	10318	2202	21,3	36355,6	1778,9	4,9
Friday	11377	2469	21,7	43250,9	5572,46	12,9
Saturday	10962	1561	14,2	39873	1307,62	3,3
Sunday	10894	2043	18,8	35237,6	1883,38	5,1
Winter period
Monday	10269	1857	18,1	37121,6	2429,73	6,5
Tuesday	10784	1665	15,4	38460,9	1950,41	5,1
Wednesday	11167	3729	33,4	39440,3	4912,99	12,49,4
Thursday	11521	2451	21,3	40000,7	3764,58	9,4
Friday	11485	1878	16,4	43669,5	2900,73	6,6
Saturday	13689	2498	18,2	52336,9	4752,77	9,1
Sunday	13436	4471	33,3	47679,9	6051,93	12,7

For the final construction of a mathematical model of the service process, taking into account the factors listed above, it is necessary to determine the distribution functions of random variables, as well as random processes describing incoming and outgoing customer flows:

1) the function of distributing customers’ time to select goods in the self-service area;

2) the function of distributing the work time of the cashier for regular cash registers and express cash registers;

3) a random process describing the incoming flow of customers in the first phase of service;

4) a random process describing the incoming flow into the second phase of service for regular cash registers and express cash registers.

It is convenient to use models for calculating the characteristics of a queuing system if the incoming flow of requests into the queuing system is a simple Poisson flow, and the service time of requests is distributed according to an exponential law.

A study of the flow of customers in the checkout area showed that a Poisson flow can be adopted for it.

The distribution function of time for servicing customers by cashiers is exponential; this assumption does not lead to large errors.

Of undoubted interest is the analysis of the characteristics of servicing the flow of customers in the cash register of a supermarket, calculated for three systems: with losses, with waiting and mixed type.

Calculations of the parameters of the customer service process at the cash register were carried out for a commercial enterprise with a sales area of ​​S = 650 based on the following data.

The objective function can be written in the general form of the connection (criterion) of sales revenue from the characteristics of the QS:

where - the cash register consists of =7 regular cash registers and =2 express cash registers,

The intensity of customer service in the area of ​​regular cash registers is 0.823 people/min;

The load intensity of cash registers in the area of ​​regular cash registers is 6.65,

The intensity of customer service in the express checkout area is 2.18 people/min;

The intensity of the incoming flow into the area of ​​regular cash desks is 5.47 people/min.

The load intensity of cash registers in the express cash register area is 1.63,

The intensity of the incoming flow into the express cash desk area is 3.55 people/min;

For the QS model with a restriction on the length of the queue in accordance with the designed area of ​​the cash register, the maximum permissible number of customers standing in line at one cash register is assumed to be equal to m = 10 customers.

It should be noted that in order to obtain relatively small absolute values ​​of the probability of loss of applications and the waiting time of customers at the cash register, the following conditions must be met:

Table 6.6.3 shows the results of the quality characteristics of the functioning of the QS in the area of ​​the calculation node.

Calculations were carried out for the busiest period of the working day from 17 to 21 hours. It is during this period, as survey results have shown, that about 50% of the one-day flow of buyers accounts for.

From the data given in table. 4.3 it follows that if the following were chosen for the calculation:

1) model with refusals, then 22.6% of the flow of customers served by regular cash registers, and accordingly 33.6% of the flow of customers served by express cash registers, would have to leave without purchasing;

2) a model with expectation, then there should be no loss of orders in the settlement node;

Table 4.3 Characteristics of the queuing system for customers in the checkout area

Cash desk type	Number of cash desks in the node	SMO type	Characteristics of the SMO
			Average number of occupied cash desks,	average waiting time for service,	The probability of losing applications,
Regular cash registers	7	with failures with anticipation with limitation
Express cash desks	2	with failures with anticipation with limitation

3) a model with a limit on the length of the queue, then only 0.12% of the flow of customers served by regular cash registers and 1.8% of the flow of customers served by express cash registers will leave the trading floor without making purchases. Consequently, a model with a limit on the length of the queue allows a more accurate and realistic description of the process of servicing customers in the checkout area.

Of interest is a comparative calculation of the capacity of a cash register unit both with and without express cash registers. In table Table 4.4 shows the characteristics of the cash register service system for three standard sizes of supermarkets, calculated using models for self-service stores with a limit on the length of the queue for the busiest period of the working day from 17 to 21 hours.

Analysis of the data in this table shows that not taking into account the factor “Structure of customer flow by type of cash service” at the stage of technological design can lead to an increase in the area of ​​the payment center by 22-33%, and hence, accordingly, to a reduction in the installation and exhibition areas of retail and technological equipment and commodity mass placed on the sales floor.

The problem of determining the capacity of a cash register is a chain of interrelated characteristics. Thus, increasing its capacity reduces the time customers wait for service, reduces the likelihood of loss of requirements and, consequently, loss of turnover. Along with this, it is necessary to correspondingly reduce the self-service area, the front of trade and technological equipment, and the stock of goods on the sales floor. At the same time, the costs of wages for cashiers and the equipment of additional workplaces increase. That's why

No.	Characteristics of the SMO	Unit	Designation		Indicators calculated by type of supermarket selling area, sq. m
					No express checkouts						Including express checkout
					650		1000		2000		650			1000			2000
											Regular cash registers		Express cash desks	Regular cash registers		express cash desks	Regular cash registers		express cash desks
1	Number of buyers	people	k		2310		3340		6680		1460		850	2040		1300	4080		2600
2	Incoming flow intensity		λ		9,64		13,9		27,9		6,08		3,55	8,55		5,41	17,1		10,8
3	Service intensity	person/min	μ		0,823		0,823		0,823		0,823		2,18	0,823		2,18	0,823		2,18
4	Load intensity	-	ρ		11,7		16,95		33,8		6,65		1,63	10,35		2,48	20,7		4,95
5	Number of cash registers	PC.	n		12		17		34		7		2	11		3	21		5
6	Total number of cash desks of the payment center	PC.		∑n		12		17		34		9			14			26

it is necessary to carry out optimization calculations. Let us consider the characteristics of the service system in the cash desk of a supermarket with a retail area of ​​650 m2, calculated using QS models with a limited queue length for various capacities of its cash desk in Table. 4.5.

Based on the analysis of data from table. 4.5 we can conclude that as the number of checkouts increases, the waiting time for customers in the queue increases, and then after a certain point it drops sharply. The nature of the change in the customer waiting time schedule is clear if we simultaneously consider the change in the probability of losing a claim. It is quite obvious that when the capacity of the cash register is too low, more than 85% of customers will leave unserved, and the remaining customers will be served in a very short time. The greater the capacity of the cash register, the more likely it is that customers will be lost while waiting for service, which means that their waiting time in the queue will increase accordingly. Afterwards, expectations and the likelihood of losses will decrease sharply.

For a supermarket with a sales area of ​​650, this limit for the regular cash register area lies between 6 and 7 cash registers. With 7 cash registers, the average waiting time is 2.66 minutes, and the probability of losing applications is very small - 0.1%. Thus, which will allow you to obtain the minimum total costs for mass customer service.

Cash service type	Number of cash registers in node n, pcs.	Characteristics of the service system		Average revenue per 1 hour rub.	Average loss of revenue per 1 hour rub.	Number of customers in the settlement area	Area of ​​the calculation node zone, Sy, m	Specific gravity of the node zone area 650/Sy
		Average waiting time, T,min	Probability of losing applications
Regular checkout zones
Express checkout zones

Conclusion

Based on the analysis of data from table. 4.5 we can conclude that as the number of checkouts increases, the waiting time for customers in the queue increases. And then after a certain point it drops sharply. The nature of the change in the customer waiting time schedule is clear if we simultaneously consider the change in the probability of losing claims. It is quite obvious that when the capacity of the cash register is too low, then more than 85% of customers will leave unserved, and the rest of the customers will be served in a very short time. The greater the power of the cash register. The probability of losing claims will decrease and, accordingly, the greater the number of customers will wait for their service, which means their waiting time in line will correspondingly increase. Once the computational node exceeds its optimal capacity, the latency and the probability of losses will decrease sharply.

For a supermarket with a sales area of ​​650 sq. meters, this limit for the area of ​​​​regular cash registers lies between 6-8 cash registers. With 7 cash registers, the average waiting time is 2.66 minutes, and the probability of losing applications is very small - 0.1%. Thus, the task is to select such a capacity of the cash register that will allow the minimum total costs for mass customer service.

In this regard, the next stage of solving the problem is to optimize the capacity of the cash register based on the use of different types of QS models, taking into account the total costs and the factors listed above.

Over the past decades, in various areas of the national economy, the need has arisen to solve probabilistic problems related to the operation of queuing systems. Examples of such systems are telephone exchanges, repair shops, retail establishments, ticket offices, etc. The job of any queuing system is to service the flow of demands entering it (subscriber calls, customers coming to the store, requests to perform work in the workshop, etc.).
The mathematical discipline that studies models of real queuing systems is called queuing theory. The task of queuing theory is to establish the dependence of the resulting performance indicators of the queuing system (the probability that a request will be served; the mathematical expectation of the number of requests served, etc.) on the input indicators (the number of devices in the system, parameters of the incoming flow of requests, etc. .) it is possible to establish such dependencies in formula form only for simple queuing systems. The study of real systems is carried out by imitation, or modeling of their operation on a computer using the statistical testing method.
A queuing system is considered specified if:
1) the incoming flow of requirements, or, in other words, the distribution law characterizing the moments in time when requirements enter the system. The root cause of the requirements is called the source. In what follows, we will agree to assume that the source has an unlimited number of requirements and that the requirements are homogeneous, that is, they differ only in the moments of their appearance in the system;
2) a service system consisting of a storage device and a service unit. The latter represents one or more servicing devices, which we will further call devices. Each request must arrive at one of the devices in order to be serviced. It may be that requirements will have to wait until devices become available. In this case, the requests reside in a backlog, forming one or more queues. Let us assume that the transfer of a request from the storage unit to the service node occurs instantly;
3) the time for servicing a request by each device, which is a random variable and is characterized by a certain distribution law;
4) waiting discipline, i.e. a set of rules regulating the number of requirements located at the same point in time in the system. A system in which a request is rejected when all servers are busy is called a no-waiting system. If a request finds all devices busy, it gets queued and waits until
until one of the devices becomes available, such a system is called a pure waiting system. A system in which a demand that finds all devices busy is queued only if the number of requests in the system does not exceed a certain level (otherwise the demand is lost) is called a mixed queuing system;
5) service discipline, i.e. a set of rules according to which a requirement is selected from the queue for service. The following rules are most often used in practice:
- applications are accepted for service on a first-come, first-served basis;
- applications are accepted for service according to the minimum time for receiving a refusal;
- applications are accepted for service in a random order in accordance with specified probabilities;
6) queue discipline, i.e. a set of rules according to which a request gives preference to one or another queue (if there are several of them) and is located in the selected queue. For example, an incoming request may take place in the shortest queue; in this queue it can be the last to be located (such a queue is called ordered), or it can go for service out of turn. Other options are also possible.

Simulation modeling of queuing systems

Model - this is any image, analogue, mental or established, image, description, diagram, drawing, etc. of any object, process or phenomenon, which in the process of cognition (study) replaces the original, preserving some typical properties that are important for this study.
Modeling is the study of an object or system of objects by constructing and studying their models. And also - this is the use of models to determine or clarify the characteristics and rationalize the methods of constructing newly constructed objects.
The model is a tool for studying complex systems.
In general a complex system is presented as a multi-level structure of interacting elements combined into subsystems of various levels. Complex systems include information systems. The design of such complex systems is carried out in two stages.

1 Exterior design

At this stage, the structure of the system, its main elements are selected, the interaction between elements is organized, the influence of the external environment is taken into account, and the system’s performance indicators are assessed.

2 Internal design - design of individual elements
systems

A typical method for studying complex systems at the first stage is their computer simulation.
As a result of modeling, dependencies are obtained that characterize the influence of the structure and parameters of the system on its efficiency, reliability and other properties. These dependencies are used to obtain the optimal structure and parameters of the system.
A model formulated in the language of mathematics using mathematical methods is called mathematical model.
Simulation modeling is characterized by the reproduction of phenomena described by a mathematical model, while maintaining their logical structure and sequence of alternations over time. To estimate the required quantities, any suitable information circulating in the model can be used, as long as it is available for registration and subsequent processing.
The required values ​​when studying processes using the simulation method are usually determined as average values ​​based on data from a large number of process implementations. If the number of realizations N used to estimate the required quantities is large enough, then, by virtue of the law of large numbers, the resulting estimates acquire statistical stability and can be accepted as approximate values ​​of the sought quantities with sufficient accuracy for practice.
The essence of the simulation method as applied to queuing problems is as follows. Algorithms are being built
with the help of which it is possible to develop random implementations of given flows of homogeneous events, as well as to simulate the processes of functioning of service systems. These algorithms are used to reproduce the implementation of a random service process many times under fixed problem conditions. The information obtained about the state of the process is subjected to statistical processing to estimate values ​​that are indicators of service quality

3 Formation of implementations of a random flow of requests

When studying complex systems using simulation modeling, significant attention is paid to taking into account random factors.
Random events, random variables and random processes (functions) are used as mathematical schemes used to formalize the action of these factors. The formation on a computer of implementations of random objects of any nature comes down to the generation and transformation of random numbers. Let's consider a method for obtaining possible values ​​of random variables with a given distribution law. To form possible values ​​of random variables with a given distribution law, the starting material is random variables that have a uniform distribution in the interval (0, 1). In other words, the possible values ​​xi of a random variable £, which has a uniform distribution in the interval (0, 1), can be transformed into possible values ​​yi of a random variable r), the distribution law of which is given. The transformation method consists in selecting random numbers from a uniformly distributed population that satisfy a certain condition in such a way that the selected numbers obey a given distribution law.
Suppose that it is necessary to obtain a sequence of random numbers yi having a density function 1^(y). If the domain of definition of the function f^y) is not limited on one or both sides, it is necessary to go to the corresponding truncated distribution. Let the range of possible values ​​for the truncated distribution be (a, b).
From the random variable r) corresponding to the density function f ^ y), we pass to f.
Random value Kommersant, will have a range of possible values ​​(0, 1) and a density function f ^(z) given by the expression.
Let the maximum value of f^(z) be equal to f m . Let us define uniform distributions in the intervals (0, 1) of random numbers x 2 i-1 and x 2 i. The procedure for obtaining a sequence yi of random numbers having a density function ^(y) is reduced to the following:
1) pairs of random numbers x2i-1 are selected from the initial population,
2) for these numbers the validity of the inequality is checked
x 21<-- ^[а + (Ъ-а)х 2М ] (3)
m
3) if inequality (3) is satisfied, then the next number yi is determined from the relation
yi =a + (b-a)x 21 (4)
When modeling service processes, the need arises to generate implementations of a random flow of homogeneous events (requests). Each flow event is characterized by the time moment tj at which it occurs. To describe a random flow of homogeneous events as a random process, it is sufficient to specify a distribution law characterizing the sequence of random variables tj. In order to obtain a realization of a stream of homogeneous events t1, t2..., tk, it is necessary to generate a realization z b z 2 ,...,zk of a k-dimensional random vector ££2,..., Sk and calculate the values ​​ti in accordance with the following relations:
t 2 =
Let a stationary ordinary flow with limited aftereffect be specified by the density function f(z). In accordance with the Palm formula (6), we find the density function f1(z1) for the first interval z1.
1-Jf(u)du
Now you can generate a random number z b as shown above, corresponding to the density function f1(z1), and obtain the moment of appearance of the first request t1 = z1. Next, we form a series of random numbers corresponding to the density function f(z), and using relation (4) we calculate the values ​​of t2, t3,.., tk.
4 Processing of simulation results
When implementing modeling algorithms on a computer, information about the states of the system under study is generated. This information is the source material for determining approximate values ​​of the desired quantities, or, as they say, estimates for the desired quantities.
The probability estimate for event A is calculated using the formula
p(A) = mN. (7)
Estimating the mean x of a random variable Kommersant, calculated by
formula
_ 1 n
k =1
The estimate S2 for the variance of the random variable ^ is calculated using the formula
1 N 1 ( N L 2
S 2 =1 YA xk 2-5>J (9)
Estimation of the correlation moment K^ for random variables Kommersant, And ts with possible values ​​x k and y k, respectively, is calculated by the formula
1 N 1 NN
Y> [ Wow

5 Example of QS modeling
Consider the following system:
1 Requirements arrive at random times, with
the time interval Q between any two consecutive demands has an exponential law with the parameter i, i.e. the distribution function has the form
>0. (11) The service system consists of s identical, numbered devices.
3 Time T about bsl - a random variable with a uniform distribution law on the segment.
4 System without waiting, i.e. a request that finds all devices busy leaves the system.
5 The service discipline is as follows: if at the moment of arrival of the kth request the first server is free, then it starts servicing the request; if this device is busy and the second one is free, then the request is serviced by the second device, etc.
It is required to estimate the mathematical expectations of the number of requests served by the system during time T and rejected.
For the initial moment of calculation, we choose the moment of arrival of the first demand T1=0. Let us introduce the following notation: Tk is the moment of arrival of the kth request; ti is the moment of completion of servicing the request by the i-th device, i=1, 2, 3, ...,s.
Let us assume that at time T 1 all devices are free.
The first demand arrives at device 1. The service time for this device has a uniform distribution over the segment . Therefore, we find the specific value of tobsl for this time using the formula
(12)
where r is the value of the random variable R, uniformly distributed on the segment. Device 1 will be busy for time t about bsl. Therefore, the moment of time t 1 of the end of servicing the request by device 1 should be considered equal to: t 1 = T1+ t o bsl.
Then you should add one to the counter of served requests and proceed to consider the next request.
Let's assume that k requirements have already been considered. Let us determine the moment T k+1 of arrival of the (k+1)th demand. To do this, we find the value t of the time interval between successive requirements. Since this interval has an exponential law, then
12
x = - In r (13)
| Ll
where r is the next value of the random variable R. Then the moment of arrival of the (k+1)th demand: T k +1 = Tk+ T.
Is the first device free at this moment? To answer this question you need to check the condition ti< Tk + i - Если это условие выполнено, то к моменту Т k +1 первый прибор освободился и может обслуживать требование. В этом случае t 1 заменяем на (Т k +1 + t обсл), добавляем единицу в счетчик об служенных требований и переходим к следующему требованию. Если t 1>T k +1, then the first device at the moment T k +1 is busy. In this case, we check whether the second device is free. If condition i 2< Tk + i выполнено, заменяем t2 на (Т k +1+ t о бсл), добавляем единицу в счетчик обслуженных требований и переходим к следующему требованию. Если t 2>Т k +1, then we check condition 1з<Тк+1 и т. д. Eсли при всех i от 1 до s имеет ti >T k +1, then at the moment T k +1 all devices are busy. In this case, we add one to the failure counter and move on to the next requirement. Each time, having calculated T k +1, it is necessary to check the condition for the end of the implementation: Tk + i< T . Если это условие выполнено, то одна реализация процесса функционирования системы воспроизведена и испыта ние заканчивается. В счетчике обслуженных требований и в счетчике отказов находятся числа n обсл и n отк.
By repeating such a test n times (using different r) and averaging the experimental results, we determine estimates of the mathematical expectations of the number of requests served and the number of requests rejected:
(14)
(Ji
n j =1
where (n obsl) j and (n otk) j are the values ​​of n obsl and n otk in the jth experiment.
13

List of sources used
1 Emelyanov A.A. Simulation modeling of economic processes [Text]: Textbook. manual for universities / A.A. Emelyanov, E.A. Vlasova, R.V. Thought. - M.: Finance and Statistics, 2002. - 368 p.
2 Buslenko, N.P. Modeling of complex systems [Text]/ N.P. Buslenko. - M.: Nauka, 1978. - 399 p.
3 Soviets B.Ya. Modeling of systems [Text]: Textbook. for universities / B.Ya. Sovetov, S.A. Yakovlev. -M. : Higher school, 1985. - 271 p.
4 Soviets B.Ya. Modeling of systems [Text]: Laboratory practical work: Proc. manual for universities in the specialty: "Automatic information processing and control system." / B.Ya. Sovetov, S.A. Yakovlev. -M. : Higher school, 1989. - 80 p.
5 Maksimey I.V. Simulation modeling on a computer [Text]/ Maksimey, I.V. -M: RADIO AND COMMUNICATION, 1988. - 231 p.
6 Ventzel E.S. Probability theory [Text]: textbook. for universities / E.S. Vent goal.- M.: Higher. school, 2001. - 575 p.
7 Gmurman, V.E. Probability theory and mathematical statistics [Text]: textbook. allowance / V.E. Gmurman.- M.: Higher. school, 2001. - 479 p.
Appendix A
(required)
Approximate topics of calculation and graphic work
1 There is only one doctor working at the emergency room. Duration of patient treatment
and time intervals between admissions of patients are random variables distributed according to the Poisson law. According to the severity of injuries, patients are divided into three categories; admission of a patient of any category is a random event with an equally probable distribution. The doctor first deals with patients with the most severe injuries (in the order of their admission), then, if there are none, with moderately severe patients, and only then with patients with minor injuries. Model the process and estimate the average waiting times in the queue for patients of each category.
2 The city motor vehicle fleet has two repair zones. The first serves repairs of short and medium duration, the second - medium and long. As breakdowns occur, vehicles are delivered to the fleet; the time interval between deliveries is a random Poisson variable. The repair duration is a random variable with a normal distribution law. Model the described system. Estimate the average waiting times in the queue for vehicles requiring short-term, medium-term and long-term repairs, respectively.
3 A mini-market with one controller-cashier serves customers whose incoming flow obeys Poisson’s law with a parameter of 20 customers/hour. Carry out a simulation of the described process and determine the probability of downtime of the controller - cashier, the length of the queue, the average number of customers in the mini-market, the average waiting time for service, the average time of customers in the mini-market and evaluate its work.
4 The ATS receives requests for long-distance calls. The customer flow is Poisson. On average, 13 applications are received per hour. Find the average number of applications received per day, the average time between the appearance of applications. A telephone exchange experiences malfunctions if it receives more than 50 requests in half an hour. Find the probability of a station failure.
5 The service station receives the simplest
current requests with an intensity of 1 car per 2 hours. There can be no more than 3 cars in the queue in the yard. Average repair time is 2 hours. Assess the performance of the CMO and develop recommendations for improving service.
6 One weaver serves a group of looms, carrying out short-term intervention as necessary, the duration of which is a random variable. Simulate the described situation. What is the probability of downtime of two machines at once? How long is the average downtime of one machine?
7 At a long-distance telephone exchange, two telephone operators serve a common queue of orders. The next order is served by the telephone operator who was the first to become available. If both are busy at the time the order is received, the call will be cancelled. Model the process, considering the input flows to be Poisson.
8 There are two doctors working at the emergency room. Duration of treatment is painful
and the time intervals between admissions of patients are random variables distributed according to the Poisson law. According to the severity of injuries, patients are divided into three categories; admission of a patient of any category is a random event with an equally probable distribution. The doctor first deals with patients with the most severe injuries (in the order of their admission), then, if there are none, with moderately severe patients, and only then with patients with minor injuries. Model the process and estimate the average waiting times in the queue for patients of each category.
9 At the long-distance telephone exchange, two telephone operators served
create a general queue of orders. The next order is served by that telephone operator,
who was the first to free herself. If both are busy at the time the order arrives, a queue is formed. Model the process, considering the input flows to be Poisson.
10 In a data transmission system, data packets are exchanged between nodes A and B over a duplex communication channel. Packets arrive at system points from subscribers with time intervals between them of 10 ± 3 ms. The packet transmission takes 10 ms. The points have buffer registers that can store two packets, including the one being transmitted. If a packet arrives when the registers are busy, the system points are provided with access to a satellite half-duplex communication line, which transmits data packets in 10 ± 5 ms. When the satellite line is busy, the packet is rejected. Model the exchange of information in a data transmission system for 1 minute. Determine the frequency of calls to the satellite line and its load. In case of possible failures, determine the volume of buffer registers necessary for failure-free operation of the system.
11 Let the usual system be used at a telephone exchange with one input: if the subscriber is busy, then the queue is not formed and you need to call again. Simulate the situation: three subscribers try to call the same number owner and, if successful, talk to him for some (random in duration) time. What is the probability that someone trying to call will not be able to do so within a certain time T.
12 A trading company plans to fulfill orders for the purchase of goods by telephone, for which it is necessary to install an appropriate mini-PBX with several telephone sets. If an order arrives when all lines are busy, the customer is refused. If at the time of receipt of an appearance at least one line is free, then a switch is made to this line and an order is placed. The intensity of the incoming flow of applications is 30 orders per hour. The average application processing time is 5 minutes. Determine the optimal number of service channels to ensure stationary operation of the QS.
13 The self-service store has 6 controllers - cashiers. The incoming flow of customers obeys Poisson's law with an intensity of 120 people/hour. One cashier can serve 40 people per hour. Determine the probability of a cashier being idle, the average number of customers in the queue, the average waiting time, the average number of busy cashiers. Evaluate the work of the QS.
14 A self-service store receives a Poisson flow with an intensity of 200 customers per hour. During the day, they are served by 3 cashier controllers with an intensity of 90 customers per hour. The intensity of the incoming flow of customers during peak hours increases to 400 customers per hour, and during slump hours it reaches 100 customers per hour. Determine the probability of a queue forming in the store and the average length of the queue during the day, as well as the required number of cashiers during peak and off-peak hours, ensuring the same length of the queue and the probability of its formation as in the nominal mode.
15 The average number of customers arriving at the payment center in a self-service store is 100 people/hour. A cashier can serve 60 people per hour. Model the process and determine how many cashiers are needed to ensure that the probability of a queue does not exceed 0.6.
16 Simulate a queue in a store with one seller under equiprobable laws of distribution of random variables: arrival of customers and duration of service (with some fixed set of parameters). Obtain stable characteristics: average values ​​of waiting in line by the buyer and idle time of the seller while waiting for the arrival of buyers. Assess their reliability.
17 Simulate a queue in a store with one seller under Poisson laws of distribution of random variables: arrival of customers and duration of service (with some fixed set of parameters). Obtain stable characteristics: average values ​​of waiting in line by the buyer and idle time of the seller while waiting for the arrival of buyers. Assess their reliability.
18 Create a model of a gas station. Find ticket service quality indicators. Determine the number of counters so that the queue does not increase.
19 The average number of customers arriving at the payment center of a self-service store is 60 people per hour. A cashier can serve 35 people per hour. Model the process and determine how many cashiers are needed to ensure that the probability of a queue does not exceed 0.6.
20 Develop a model of a bus route with n stops. Determine the performance indicators for using the QS.

Analytical research of queuing systems (QS) is an approach alternative to simulation modeling, and consists of obtaining formulas for calculating the output parameters of the QS and then substituting the values ​​of the arguments into these formulas in each individual experiment.

The QS models consider the following objects:

1) service requests (transactions);

2) service devices (OA), or devices.

The practical task of queuing theory is associated with the study of operations by these objects and consists of individual elements that are influenced by random factors.

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

A request can be either in a service state or in a service pending state.

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

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

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

The most important output parameters of the QS

Performance

Bandwidth

Probability of denial of service

Average service time;

Equipment load factor (OA).

Applications can be orders for the production of products, problems solved in a computer system, clients in banks, goods received for transportation, etc. Obviously, the parameters of applications entering the system are random variables and during research or design only their laws of distribution.

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

The simplest models of QS

In the simplest case, the QS is a device called a service apparatus (SA), with queues of requests at the inputs.

CUSTOMER SERVICE MODEL (Fig. 5.1)

Rice. 5.1. QS model with failures:

0 – source of requests;

1 – service device;

A– input flow of requests for service;

V– output stream of served requests;

With– output stream of unprocessed requests.

In this model, there is no demand accumulator at the OA input. If a request arrives from source 0 at a time when the OA is busy servicing the previous request, then the newly arrived request leaves the system (since it is denied service) and is lost (flow With).

M o d e l o f f o r m e n t i n g (Fig. 5.2)

Rice. 5.2. QS model with expectation

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

In this model there is a demand accumulator at the OA input. If a request arrives from source 0 at a time when the OA is busy servicing the previous request, then the newly arrived request ends up in the storage unit, where it waits for an indefinitely long time until the OA becomes free.

SERVICE MODEL WITH LIMITED TIME

o w i d a n i a (Fig. 5.3)

Rice. 5.4. Multi-channel QS model with failures:

n– number of identical service devices (devices)

In this model there is not one OA, but several. Applications, unless specifically stated, may be submitted to any OA free from service. There is no storage device, so this model includes the properties of the model shown in Fig. 5.1: refusal to service an application means its irretrievable loss (this occurs only if, at the time of arrival of this application, All OA are busy).

W aiting time (Fig. 5.5)

Rice. 5.6. Multichannel model of SMO with expectation and restoration of OA:

e– service devices that are out of order;

f– refurbished service equipment

This model has the properties of the models presented in Fig. 5.2 and 5.4, and in addition properties that make it possible to take into account possible random failures of the OA, which in this case arrive at the repair unit 2, where they remain for random periods of time spent on their restoration, and then return again to the service unit 1.

MULTI-CHANNEL MODEL OF SMO WITH LIMITED

TIME OF WAITING AND RECOVERY OF OA (Fig. 5.7)

Rice. 5.7. Multi-channel QS model with limited latency and OA recovery

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