Indicators of the effectiveness of the use of smo include: Course work: Simulation modeling of a queuing system. Queuing theory
The theory of QS is devoted to the development of methods for analysis, design and rational organization of systems related to various fields of activity, such as communications, computer technology, trade, transport, and military affairs. Despite all their diversity, the above systems have a number of typical properties, namely.
- Queuing systems (queuing systems) are system models, in which applications (requirements) are received at random times from outside or inside. They must be served by the system in one way or another. The duration of service is most often random.
- QS is totality serving equipment And personnel with appropriate organization of the service process.
- To set a QMS means to set it structure and statistical characteristics of the sequence of requests received and the sequence of their servicing.
- indicators characterizing the system as a whole: number n busy service channels, number of serviced (λ b), pending service or rejected applications (λ c) per unit of time, etc.;
- probabilistic characteristics: probability that the request will be served ( P obs) or receive a denial of service ( P open) that all devices are free ( p 0) or a certain number of them are occupied ( p k), probability of a queue, etc.;
- economic indicators: the cost of losses associated with the departure of an application that was not serviced for one reason or another from the system, the economic effect obtained as a result of servicing the application, etc.
During the home test, the simplest QSs are studied. These are open-loop systems; an endless source of applications is not included in the system. The input flow of requests, service flows and expectations of these systems are the simplest. There are no priorities. Single-phase systems.
Multi-channel system with failures
The system consists of one service node containing n service channels, each of which can serve only one request.All service channels have the same performance and are indistinguishable for the system model. If a request enters the system and finds at least one channel free, it immediately begins to be serviced. If at the time of receipt of an application in the system all channels are busy, then the application leaves the system unserved.
Mixed systems
- System with limitation by queue length
.
Consists of a storage device (queue) and a service node. An application leaves the queue and leaves the system if there are already m applications in the storage by the time it appears (m is the maximum possible number of places in the queue). If a request has entered the system and finds at least one channel free, it immediately begins to be serviced. If at the time an application arrives in the system, all channels are busy, then the application does not leave the system, but takes a place in the queue. An application leaves the system unserved if, by the time it enters the system, all service channels and all places in the queue are occupied.
For each system, a queue discipline is determined. This is a system of rules that determine the order in which requests arrive from the queue to the service node. If all requests and service channels are equal, then most often the rule “who comes first is served first” applies. - System with limitation for the duration of the application's stay in the queue.
Consists of a storage device (queue) and a service node. It differs from the previous system in that a request received in the storage (queue) can wait for service to begin for only a limited time So(most often this is a random variable). If its time So has expired, then the application leaves the queue and leaves the system unserved.
Mathematical description of QS
QSs are considered as some physical systems with discrete states x 0, x 1, ..., x n, operating at continuous time t. The number of states n can be finite or countable (n → ∞). The system can move from one state x i (i= 1, 2, … , n) to another x j (j= 0, 1,... ,n) at any time t. To show the rules for such transitions, use a diagram called state graph. For the types of systems listed above, state graphs form a chain in which each state (except for the extreme ones) is connected by direct and feedback with two neighboring states. This is the diagram death and reproduction .Transitions from state to state occur at random times. It is convenient to assume that these transitions occur as a result of the action of some streams(flows of input requests, refusals to service requests, flow of device restoration, etc.). If all threads protozoa, then the random flow occurring in the system a process with a discrete state and continuous time will be Markovian .
Event stream is a sequence of similar events occurring at random moments in time. It can be viewed as a sequence of random moments in time t 1 ,t 2 , ... occurrence of events.
The simplest is a stream that has the following properties:
- Ordinariness. Events follow one at a time (the opposite of a stream, where events follow in groups).
- Stationarity. Probability of a given number of events occurring in a time interval T depends only on the length of the interval and does not depend on where this interval is located on the time axis.
- No aftereffect. For two non-overlapping time intervals τ 1 and τ 2, the number of events falling on one of them does not depend on how many events fall on the other interval.
Markov random events are described by ordinary differential equations. The variables in them are the probabilities of states R 0 (t), p 1 (t),…,p n (t).
For very large moments in time of the functioning of systems (theoretically at t → ∞) in the simplest systems (systems in which all the flows are the simplest, and the graph is a scheme of death and reproduction) it is observed steady, or stationary operating mode. In this mode, the system will change its state, but the probabilities of these states ( final probabilities) r k, k= 1, 2 ,…, n, do not depend on time and can be considered as average relative time the system remains in the appropriate state.
1.1. Structure and parameters of the efficiency and quality of functioning of the QS
Many economic problems are related to queuing systems, i.e. such systems in which, on the one hand, massive requests (demands) arise for the performance of any services, and on the other hand, these requests are satisfied. The QS includes the following elements: source of requirements, incoming flow of requirements, queue, serving devices (service channels), outgoing flow of requirements. Queuing theory studies such systems.
The facilities that serve requirements are called servicers or service channels. For example, these include refueling devices at gas stations, telephone communication channels, landing strips, repairmen, ticket cashiers, loading and unloading points at bases and warehouses.
Using the methods of queuing theory, many problems in studying processes occurring in the economy can be solved. Thus, in organizing trade, these methods make it possible to determine the optimal number of retail outlets of a given profile, the number of sellers, the frequency of delivery of goods and other parameters. Another typical example of queuing systems can be gas stations, and the tasks of queuing theory in this case come down to establishing the optimal ratio between the number of service requests arriving at a gas station and the number of service devices, at which the total costs of service and losses from downtime would be minimal. The theory of queuing can also be applied when calculating the area of warehouse premises, while the warehouse area is considered as a service device, and the arrival of vehicles for unloading is considered as a requirement. Models of the theory of queuing are also used in solving a number of problems of organizing and rationing labor, and other socio-economic problems.
Each QS includes in its structure a certain number of service devices, called service channels (these may include persons performing certain operations - cashiers, operators, managers, etc.) serving a certain flow of applications (requirements), arriving at its input at random times. Service of applications occurs in an unknown, usually random time and depends on many different factors. After servicing the request, the channel is freed and ready to receive the next request. The random nature of the flow of applications and the time of their servicing leads to uneven loading of the QS - overload with the formation of queues of applications or underload - with idleness of its channels. The randomness of the nature of the flow of requests and the duration of their service gives rise to a random process in the QS, the study of which requires the construction and analysis of its mathematical model. The study of the functioning of the QS is simplified if the random process is Markovian (a process without aftereffects, or without memory), when the operation of the QS is easily described using finite systems of ordinary linear differential equations of the first order, and in the limiting mode (with a sufficiently long operation of the QS) by means of finite systems linear algebraic equations. As a result, indicators of the effectiveness of the functioning of the QS are expressed through the parameters of the QS, the flow of applications and discipline.
It is known from theory that for a random process to be Markovian, it is necessary and sufficient that all flows of events (flows of applications, flows of servicing applications, etc.), under the influence of which transitions of the system from state to state occur, are Poisson, i.e. had the properties of consequence (for any two non-overlapping time intervals, the number of events occurring during one of them does not depend on the number of events occurring after the other) and ordinariness (the probability of occurrence of more than one event during an elementary, or small, period of time is negligible compared to the probability of one event occurring during this period of time). For the simplest Poisson flow, the random variable T (the time interval between two neighboring events) is distributed according to an exponential law, representing its distribution density or differential distribution function.
If the nature of flows in a QS is different from Poisson, then its efficiency characteristics can be determined approximately using the Markov theory of queuing, and the more accurately, the more complex the QS, and the more service channels it has. In most cases, valid recommendations for the practical management of a QS do not require knowledge of its exact characteristics; it is quite enough to have their approximate values.
Each QS, depending on its parameters, has a certain operating efficiency.
The effectiveness of the functioning of the QS is characterized by three main groups of indicators:
1. Efficiency of using the QS – absolute or relative throughput, average duration of the QS busy period, QS utilization rate, QS non-use ratio;
2. Quality of servicing of applications - the average time (average number of applications, distribution law) of waiting for an application in a queue or staying of an application in the QS; the likelihood that the received application will be immediately accepted for execution;
3. The efficiency of the functioning of a pair of CMO-consumer, and the consumer is understood as a set of applications or some source of them (for example, the average income brought by the CMO per unit of operating time, etc.).
1.2 Classification of QS and their main elements
QS are classified into different groups depending on the composition and time spent in queue before the start of service, and on the discipline of servicing requests.
According to the composition of the QS, there are single-channel (with one serving device) and multi-channel (with a large number of serving devices). Multichannel systems can consist of service devices of both the same and different performance.
Based on the time requirements remain in the queue before servicing begins, systems are divided into three groups:
1) with unlimited waiting time (with waiting),
2) with refusals;
3) mixed type.
In a QS with an unlimited waiting time, the next request, finding all the devices busy, gets into a queue and waits for service until one of the devices is free.
In systems with failures, an arriving request, finding all devices busy, leaves the system. A classic example of a system with failures is the operation of an automatic telephone exchange.
In mixed-type systems, an incoming request finds all devices busy, queues and waits for service for a limited time. Without waiting for service at the set time, the request leaves the system.
Let us briefly consider the features of the functioning of some of these systems.
1. A QS with waiting is characterized by the fact that in a system of n (n>=1) any request that arrives at the QS at the moment when all channels are busy gets into a queue and awaits service, and any incoming request is serviced. Such a system can be in one of an infinite number of states: s n +к (r=1.2...) – all channels are busy and there are r applications in the queue.
2. A QS with waiting and a limit on the queue length differs from the above in that this system can be in one of n+m+1 states. In states s 0 , s 1 ,…, s n there is no queue, since there are either no applications in the system or none at all and the channels are free (s 0), or there are several I (I = 1,n) applications in the system, which is served by the corresponding (n+1, n+2,…n+r,…,n+m) number of applications and (1,2,…r,…,m) applications standing in the queue. An application that arrives at the QS input at a time when there are already m applications in the queue is rejected and leaves the system unserved.
Thus, a multi-channel QS essentially works like a single-channel one, when all n channels work as one with a mutual assistance discipline called all as one, but with a higher intensity of service. The state graph of such a similar system contains only two states: s 0 (s 1) - all n channels are free (busy).
An analysis of various types of QS with mutual assistance of the all-in-one type shows that such mutual assistance reduces the average time an application stays in the system, but worsens a number of other characteristics such as the probability of failure, throughput, the average number of applications in the queue and the waiting time for their execution. Therefore, to improve these indicators, a change in the discipline of servicing requests with uniform mutual assistance between channels is used as follows:
· If a request arrives at the QS at a time when all channels are free, then all n channels begin servicing it;
· If at this time the next request arrives, then some of the channels switch to servicing it
· If, while servicing these two requests, a third request arrives, then some of the channels are switched to servicing this third request, until each request located in the QS is served by only one channel. In this case, an application received at the moment all channels are busy, in the QS with refusals and uniform mutual assistance between channels, may be rejected and will be forced to leave the system unserved.
Methods and models used in queuing theory can be divided into analytical and simulation.
Analytical methods of queuing theory make it possible to obtain the characteristics of the system as some functions of its operating parameters. Thanks to this, it becomes possible to conduct a qualitative analysis of the influence of individual factors on the efficiency of the QS. Simulation methods are based on computer modeling of queuing processes and are used if it is impossible to use analytical models.
Currently, the most theoretically developed and convenient in practical applications are methods for solving queuing problems in which the incoming flow of requirements is the simplest (Poisson).
For the simplest flow, the frequency of requests entering the system obeys the Poisson law, i.e. the probability of arrival during time t of exactly k demands is given by the formula:
An important characteristic of a QS is the time it takes to service requirements in the system. The service time of one request is, as a rule, a random variable and, therefore, can be described by a distribution law. The exponential law of distribution of service time is most widely used in theory and especially in practical applications. The distribution function for this law has the form:
Those. the probability that the service time does not exceed a certain value t is determined by this formula, where µ is the parameter of exponential service of requirements in the system, i.e. the reciprocal of the service time t rev:
Let's consider analytical models of the most common QS with expectation, i.e. such QS in which requests received at a time when all serving channels are busy are queued and serviced as the channels become free.
The general formulation of the problem is as follows. The system has n serving channels, each of which can serve only one request at a time.
The system receives a simple (Paussonian) flow of requests with parameter . If, at the time the next request arrives, there are already at least n requests in the system for servicing (i.e., all channels are busy), then this request becomes queued and waits for servicing to begin.
In systems with a certain service discipline, an incoming request, finding all devices busy, depending on its priority, is either serviced out of turn or placed in a queue.
The main elements of the QS are: the incoming flow of requirements, the queue of requirements, serving devices (channels) and the outgoing flow of requirements.
The study of QS begins with the analysis of the incoming flow of requirements. The incoming requirement flow is the collection of requirements that enter the system and need to be serviced. The incoming flow of requirements is studied in order to establish the patterns of this flow and further improve the quality of service.
In most cases, the incoming flow is uncontrollable and depends on a number of random factors. The number of requests arriving per unit of time is a random variable. A random variable is also the time interval between adjacent incoming requests. However, the average number of requests received per unit of time and the average time interval between adjacent incoming requests are assumed to be given.
The average number of demands entering the service system per unit of time is called the demand arrival rate and is determined by the following relation:
where T is the average value of the interval between the arrival of subsequent requests.
For many real processes, the flow of requirements is fairly well described by the Poisson distribution law. Such a flow is called the simplest.
The simplest stream has the following important properties:
1) The property of stationarity, which expresses the invariance of the probabilistic flow regime over time. This means that the number of requests entering the system at equal intervals of time should, on average, be constant. For example, the number of cars arriving for loading on average per day should be the same for different periods of time, for example, at the beginning and at the end of a decade.
2) The absence of aftereffect, which determines the mutual independence of the receipt of one or another number of requests for service in non-overlapping periods of time. This means that the number of requests arriving in a given period of time does not depend on the number of requests serviced in the previous period of time. For example, the number of vehicles arriving for materials on the tenth day of the month is independent of the number of vehicles serviced on the fourth or any other previous day of the month.
3) The property of ordinaryness, which expresses the practical impossibility of the simultaneous receipt of two or more demands (the probability of such an event is immeasurably small in relation to the period of time under consideration, when the latter tends to zero).
With the simplest flow of demands, the distribution of demands entering the system obeys the Poisson distribution law:
the probability that exactly k requests will arrive at the servicing system during time t:
Where. - the average number of requests received for service per unit of time.
In practice, the conditions of the simplest flow are not always strictly met. The process is often nonstationary (at different hours of the day and different days of the month, the flow of requirements may change; it may be more intense in the morning or on the last days of the month). There is also an aftereffect, when the number of requirements for the release of goods at the end of the month depends on their satisfaction at the beginning of the month. The phenomenon of heterogeneity is also observed when several clients simultaneously arrive at the warehouse for materials. However, in general, the Poisson distribution law reflects many queuing processes with a fairly high approximation.
In addition, the presence of a Poisson flow of requirements can be determined by statistical processing of data on the receipt of requests for service. One of the features of the Poisson distribution law is the equality of the mathematical expectation of a random variable and the variance of the same variable, i.e.
One of the most important characteristics of service devices, which determines the throughput of the entire system, is service time.
The service time for one request () is a random variable that can change over a wide range. It depends on the stability of the operation of the servicing devices themselves, as well as on various parameters entering the system, requirements (for example, different carrying capacity of vehicles arriving for loading or unloading.
A random variable is completely characterized by a distribution law, which is determined on the basis of statistical tests.
In practice, the hypothesis about the exponential distribution law of service time is most often accepted.
The exponential distribution law of service time occurs when the distribution density decreases sharply with increasing time t. For example, when the bulk of requirements are serviced quickly, and long-term service is rare. The presence of an exponential distribution law for service time is established on the basis of statistical observations.
With the exponential distribution law of service time, the probability of an event that the service time will last no more than t is equal to:
where v is the intensity of servicing one requirement by one service device, which is determined from the relation:
where is the average time for servicing one request by one service device.
It should be noted that if the law of distribution of service time is indicative, then in the presence of several servicing devices of the same power, the law of distribution of service time by several devices will also be indicative:
where n is the number of service devices.
An important parameter of the QS is the load factor, which is defined as the ratio of the intensity of receipt of requirements to the intensity of service v.
where a is the load factor; - intensity of requirements entering the system; v is the intensity of servicing one request by one service device.
From (1) and (2) we obtain that
Considering that is the intensity of requests entering the system per unit time, the product shows the number of requests entering the service system during the average time of servicing one request by one device.
For a QS with waiting, the number of serviced devices n must be strictly greater than the load factor (requirement for a steady or stationary operating mode of the QS):
Otherwise, the number of incoming requests will be greater than the total productivity of all serving devices, and the queue will grow without limit.
For QS with failures and mixed types, this condition can be weakened; for the effective operation of these types of QS, it is sufficient to require that the minimum number of serviced devices n be not less than the load factor:
1.3 Simulation process
As noted earlier, the process of iterative development of a simulation model begins with the creation of a simple model, which then gradually becomes more complex in accordance with the requirements of the problem being solved. The following main stages can be distinguished in the process of simulation:
1. Formation of the problem: description of the problem under study and determination of the objectives of the study.
2. Model development: logical and mathematical description of the modeled system in accordance with the formulation of the problem.
3. Data preparation: identification, specification and collection of data.
4. Model translation: translation of the model into a language acceptable for the computer being used.
5. Verification: establishing the correctness of machine programs.
6. Validation: assessment of the required accuracy and compliance of the simulation model with the real system.
7. Strategic and tactical planning: determining the conditions for conducting a machine experiment with a simulation model.
8. Experimentation: running a simulation model on a computer to obtain the required information.
9. Analysis of results: studying the results of a simulation experiment to prepare conclusions and recommendations for solving the problem.
10. Implementation and documentation: implementation of recommendations obtained from the simulation, preparation of documentation on the model and its use.
Let's consider the main stages of simulation modeling. The first task of a simulation study is to precisely define the problem and formulate in detail the objectives of the study. Typically, problem definition is an ongoing process that typically occurs throughout the study. It is revised as a deeper understanding of the problem under study and the emergence of new aspects of it.
Once the initial definition of the problem is formulated, the stage of building a model of the system under study begins. The model includes a statistical and dynamic description of the system. In the statistical description, the elements of the system and their characteristics are determined, and in the dynamic description, the interaction of the elements of the system, as a result of which a change in its state occurs over time.
The process of forming a model is in many ways an art. The model developer must understand the structure of the system, identify the rules of its functioning and be able to highlight the most essential in them, eliminating unnecessary details. The model must be easy to understand and at the same time complex enough to realistically represent the characteristics of a real system. The most important decisions are made by the designer regarding whether the adopted simplifications and assumptions are correct, which elements and the interactions between them should be included in the model. The level of detail in the model depends on the purpose of its creation. It is necessary to consider only those elements that are essential for solving the problem under study. Both at the problem formation stage and at the modeling stage, close interaction is necessary between the model developer and its users. In addition, close interaction at the stages of problem formulation and model development gives the user confidence in the correctness of the model, and therefore helps ensure the successful implementation of the results of the simulation study.
At the model development stage, the requirements for input data are determined. Some of this data may already be available to the modeler, while others will require time and effort to collect. Usually the value of such input data is set based on some hypotheses or preliminary analysis. In some cases, the exact values of one (or more) input parameters have little impact on the results of model runs. The sensitivity of the results obtained to changes in the input data can be assessed by conducting a series of simulation runs for different values of the input parameters. The simulation model can therefore be used to reduce the time and cost required to refine input data. Once the model has been developed and the initial input data has been collected, the next task is to translate the model into a computer-accessible form.
At the verification and validation stages, the functioning of the simulation model is assessed. At the verification stage, it is determined whether the model programmed for the computer corresponds to the developer’s intention. This is usually done by manually checking the calculation, but a number of statistical methods may also be used.
Establishing the adequacy of the simulation model of the system under study is carried out at the validation stage. Model validation is usually performed at various levels. Specific validation methods include establishing adequacy by using constant values for all parameters of the simulation model or by assessing the sensitivity of outputs to changes in input data values. During the validation process, comparisons should be made based on the analysis of both real and experimental data on the functioning of the system.
The conditions for conducting machine runs of the model are determined at the stages of strategic and tactical planning. The task of strategic planning is to develop an effective experimental plan, as a result of which the relationship between controlled variables is clarified, or a combination of values of controlled variables is found, minimization or maximization of the simulation model. Tactical planning, as opposed to strategic planning, addresses the issue of how to conduct each simulation run within the experimental plan in order to obtain the greatest amount of information from the output data. An important place in tactical planning is occupied by the definition of conditions for simulation runs and methods for reducing the variance of the average value of the model response.
The next stages in the process of simulation research - conducting a computer experiment and analyzing the results - include running the simulation model on a computer and interpreting the resulting output data. The last stage of a simulation study is to implement the resulting solutions and document the simulation model and its use. No simulation project should be considered complete until the results have been used in the decision-making process. The success of the implementation largely depends on how correctly the model developer completed all the previous stages of the simulation research processes. If the developer and user worked closely and reached a mutual understanding in developing the model and exploring it, then the result of the project is likely to be successfully implemented. If there was no close relationship between them, then, despite the elegance and adequacy of simulation modeling, it will be difficult to develop effective recommendations.
The above steps are rarely performed in a strictly defined sequence, from problem definition to documentation. During simulation, there may be failures in model runs, erroneous assumptions that later have to be abandoned, refocusing of research goals, re-estimations and rebuilding of the model. This process allows the development of a simulation model that provides a valid assessment of alternatives and facilitates the decision-making process.
Chapter 2. Distributions and pseudorandom number generators
The following notations will be used below:
X is a random variable; f(x) - probability density function X; F(x) - probability function X;
a - minimum value;
b - maximum value;
μ - mathematical expectation M[X]; σ2 - variance M[(X-μ)2];
σ - standard deviation; α-parameter of the probability density function;
A queue of length k remains in it with probability Pk and does not join the queue with probability gk=1 - Pk." This is exactly how people usually behave in queues. In queuing systems, which are mathematical models of production processes, the possible queue length is limited by a constant size (bunker capacity, for example). Obviously, this is a special case of the general setting. Some...
1. Indicators of the effectiveness of using QS:
The absolute capacity of the QS is the average number of requests that can be
can serve the QS per unit time.
Relative capacity of the QS – the ratio of the average number of requests,
number of service providers served per unit of time, to the average number of arrivals for the same
application time.
Average duration of the employment period of the CMO.
QS utilization rate is the average proportion of time during which
The CMO is busy servicing requests, etc.
2. Quality indicators for servicing applications:
Average waiting time for an application in the queue.
Average time an application stays in the CMO.
The probability of a request being denied service without waiting.
The probability that a newly received application will be immediately accepted for service.
Law of distribution of waiting time for an application in a queue.
The law of distribution of the time an application stays in the QS.
The average number of applications in the queue.
Average number of applications in the CMO, etc.
3. Indicators of the effectiveness of the functioning of the “SMO – client” pair, where “client” is understood as the entire set of requests or a certain source of them. Such indicators include, for example, the average income generated by the CMO per unit of time
Classification of queuing systems
By number of QS channels:
single-channel(when there is one service channel)
multichannel, more precisely n-channel (when the number of channels n≥ 2).
By service discipline:
1. SMO with failures, in which the application received at the input of the QS at the moment when all
the channels are busy, receives a “refusal” and leaves the QS (“disappears”). So that this application is still
has been serviced, it must again enter the QS entrance and be considered as an application received for the first time. An example of a QS with refusals is the operation of an automatic telephone exchange: if the dialed telephone number (an application received at the entrance) is busy, then the application receives a refusal, and in order to reach this number, it must be dialed again.
2. SMO with anticipation(unlimited waiting or queue). In such systems
a request that arrives when all channels are busy is queued and waits for the channel to become available and accept it for service. Each application received at the entrance will eventually be serviced. Such self-service systems are often found in trade, in the field of consumer and medical services, and in enterprises (for example, servicing machines by a team of adjusters).
3. SMO mixed type(with limited expectation). These are systems in which some restrictions are imposed on the application’s stay in the queue.
These restrictions may apply to queue length, i.e. maximum possible
the number of applications that can be in the queue at the same time. An example of such a system is a car repair shop that has a limited parking lot for faulty cars awaiting repair.
Waiting restrictions may concern the time the application spent in the queue, according to history
at which point it exits the queue and leaves the system).
In QS with waiting and in QS of mixed type, different communication schemes are used.
servicing requests from the queue. Service may be ordered, when requests from the queue are serviced in the order they enter the system, and disordered, in which applications from the queue are serviced in random order. Sometimes used priority service, when some requests from the queue are considered priority and therefore are served first.
To limit the flow of applications:
closed And open.
If the flow of applications is limited and applications that have left the system can be returned to it,
xia, then QS is closed, otherwise - open.
By number of service stages:
single-phase And multiphase
If the QS channels are homogeneous, i.e. perform the same maintenance operation
niya, then such QS are called single-phase. If service channels are located sequentially and they are heterogeneous, since they perform various service operations (i.e. service consists of several successive stages or phases), then the QS is called multiphase. An example of the operation of a multiphase QS is car servicing at a service station (washing, diagnosing, etc.).
Performance indicators of the QS- absolute and relative system capacity;
- load and idle rates;
- average time to fully load the system;
- average time an application stays in the system.
- P obs – probability of request servicing,
- t syst – time of stay of the application in the system.
- λ b– absolute system throughput (average number of requests served per unit of time),
- P obs – relative system capacity,
- k z – system load factor.
Task . A shared computing center with three computers receives orders from enterprises for computing work. If all three computers are working, then the newly received order is not accepted, and the enterprise is forced to contact another computer center. The average time of work with one order is 3 hours. The intensity of the flow of applications is 0.25 (1/hour). Find the limiting probabilities of states and performance indicators of the computer center.
Solution.
According to the condition n=3, λ=0.25(1/h), t vol. =3 (h). Service flow intensity μ=1/t vol. =1/3=0.33. Computer load intensity according to formula (24) ρ=0.25/0.33=0.75. Let's find the limiting probabilities of states:
according to formula (25) p 0 =(1+0.75+0.75 2 /2!+0.75 3 /3!) -1 =0.476;
according to formula (26) p 1 =0.75∙0.476=0.357; p 2 =(0.75 2 /2!)∙0.476=0.134; p 3 =(0.75 3 /3!)∙0.476=0.033 i.e. in the stationary mode of operation of the computer center, on average 47.6% of the time there is no request, 35.7% - there is one request (one computer is occupied), 13.4% - two requests (two computers), 3.3% of the time -
three requests (three computers are occupied).
The probability of failure (when all three computers are busy), thus, P open. =p 3 =0.033.
According to formula (28), the relative capacity of the center is Q = 1-0.033 = 0.967, i.e. On average, out of every 100 requests, the computer center services 96.7 requests.
According to formula (29), the absolute capacity of the center is A = 0.25∙0.967 = 0.242, i.e. On average, 0.242 applications are served per hour.
According to formula (30), the average number of occupied computers k = 0.242/0.33 = 0.725, i.e. each of the three computers will be busy servicing requests on average only 72.5/3 = 24.2%.
When assessing the efficiency of a computer center, it is necessary to compare the income from the execution of requests with the losses from the downtime of expensive computers (on the one hand, we have a high throughput of the QS, and on the other hand, there is significant downtime of service channels) and choose a compromise solution.
Task . The port has one berth for unloading ships. The vessel flow rate is 0.4 (vessels per day). The average unloading time for one vessel is 2 days. It is assumed that the queue can be of unlimited length. Find the performance indicators of the berth, as well as the probability that no more than 2 vessels are waiting to unload.
Solution.
We have ρ = λ/μ = μt vol. =0.4∙2=0.8. Since ρ = 0.8 <
1, then the queue for unloading cannot increase indefinitely and limiting probabilities exist. Let's find them.
The probability that the berth is free, according to (33) p 0 = 1 - 0.8 = 0.2, and the probability that it is occupied, P occupancy. = 1-0.2 = 0.8. According to formula (34), the probabilities that there are 1, 2, 3 vessels at the berth (i.e., 0, 1, 2 vessels are waiting to unload) are equal to p 1 = 0.8(1-0.8) = 0, 16; p 2 = 0.8 2 ∙(1-0.8) = 0.128; p 3 = 0.8 3 ∙(1-0.8) = 0.1024.
The probability that no more than 2 vessels are waiting to unload is equal to
P=p 1 +p 2 +p 3 = 0.16 + 0.128 + 0.1024 = 0.3904
According to formula (40), the average number of ships awaiting unloading
L jh =0.8 2 /(1-0.8) = 3.2
and the average waiting time for unloading according to the formula (15.42)
Tp = 3.2/0.8 = 4 days.
According to formula (36), the average number of vessels located at the berth, L syst. = 0.8/(1-0.8) = 4 (days) (or simpler according to (37) L syst. = 3.2+0.8 = 4 (days), and the average time the vessel stays at the berth according to the formula (41) T syst = 4/0.8 = 5 (days).
It is obvious that the efficiency of unloading ships is low. To increase it, it is necessary to reduce the average time of unloading the vessel t about or increase the number of berths n.
Task . In a supermarket, a flow of customers arrives at the payment center with an intensity of λ = 81 people. at one o'clock. The average duration of service by a cashier controller to one customer t rev = 2 min. Define:
A. Minimum number of cashiers n min, in which the queue will not grow to infinity, and the corresponding service characteristics for n=n min .
b. Optimal quantity n opt. controllers-cashiers, at which the relative value of costs C rel., associated with the costs of maintaining service channels and with staying in the customer queue, given, for example, as , will be minimal, and compare the service characteristics with n=n min and n=n opt .
V. The probability that there will be no more than three customers in the queue.
Solution.
A. By condition l = 81(1/h) = 81/60 = 1.35 (1/min.). According to formula (24) r = l/ m = lt rev = 1.35×2 = 2.7. The queue will not grow indefinitely provided r/n< 1, т.е. при n >r = 2.7. Thus, the minimum number of cashier controllers is n min = 3.
Let us find the service characteristics of the QS at P= 3.
The probability that there are no buyers in the settlement node, according to formula (45) p 0 = (1+2.7+2.7 2 /2!+2.7 3 /3!+2.7 4 /3!(3 -2.7)) -1 = 0.025, i.e. on average 2.5%
controllers and cashiers will be idle for a while.
The probability that there will be a queue at the calculation node, according to (48) P very. = (2.7 4 /3!(3-2.7))0.025 = 0.735
The average number of customers in the queue for (50) L och. = (2.7 4 /3∙3!(1-2.7/3) 2)0.025 = 7.35.
Average waiting time in queue for (42) T very. = 7.35/1.35 = 5.44 (min).
Average number of buyers in the settlement node according to (51) L system. = 7.35+2.7 = 10.05.
Average time spent by buyers in the settlement node according to (41) T syst. = 10.05/1.35 = 7.44 (min).
Table 1
| Service characteristics | Number of cashiers | ||||
| 3 | 4 | 5 | 6 | 7 | |
| Probability of downtime of cashiers p 0 | 0,025 | 0,057 | 0,065 | 0,067 | 0,067 |
| Average number of customers in the queue T very. | 5,44 | 0,60 | 0,15 | 0,03 | 0,01 |
| Relative value of costs C rel. | 18,54 | 4,77 | 4,14 | 4,53 | 5,22 |
Coefficient (share) of cashiers employed in servicing
= ρ/n = 2.7/3 = 0.9.
Absolute throughput of the calculation node A = 1.35 (1/min), or 81 (1/h), i.e. 81 customers per hour.
Analysis of service characteristics indicates a significant overload of the payment center in the presence of three cashiers.
b. Relative cost value for n = 3
C rel. = = 3/1.35+3∙5.44 = 18.54.
Let's calculate the relative value of costs for other values P(Table 1).
As can be seen from table. 2, the minimum costs are obtained at n = n opt. = 5 controllers-cashiers.
Let us determine the service characteristics of the calculation node for n = n opt. =5. We get P very good. = 0.091; L very = 0.198; T och. = 0.146 (min); L syst. = 2.90; T snst. = 2.15 (min); k = 2.7; k 3 = 0.54.
As we can see, with n = 5 compared to n = 3, the probability of occurrence of a queue P very decreased significantly. , queue length L very and the average time spent in queue T very. and, accordingly, the average number of buyers L system. and the average time spent in the payment node T system, as well as the share of controllers engaged in servicing k 3. But the average number of cashier controllers engaged in servicing k and the absolute throughput of the payment node A naturally did not change.
V. The probability that there will be no more than 3 buyers in the queue is given by
= 1- P very good + p 5+1 + p 5+2 + p 5+3 , where we find each term using formulas (45) – (48). We get for n=5:
Note that in the case of n=3 cashiers, the same probability is significantly lower: P(r ≤ 3) =0.464.
The queuing system consists of the following elements (Figure 5.6).
1 - incoming flow requirements ω( t) – a set of requirements for a service provider to carry out certain work (refueling, washing, maintenance, etc.) or provide services (purchase of products, parts, materials, etc.). The incoming flow of requirements can be constant or variable.
Requirements can be homogeneous (same types of work or services) and heterogeneous (different types of work or services).
2 - queue - requirements awaiting service. The queue is being evaluated average length r– the number of objects or clients awaiting service.
Figure 5.6 – General diagram of the queuing system
3 - service devices(service channels) – a set of workplaces, performers, equipment that service requirements using a certain technology.
4 -outgoing demand flowω’( t) – flow of requirements that have passed the QS. In general, the output stream may consist of serviced and unserviced requests. An example of unserved claims: a required part is missing from a vehicle being repaired.
5- short circuit(possible) QS – a state of the system in which the incoming flow of requirements depends on the outgoing flow.
In road transport, after servicing requirements (maintenance, repairs), the vehicle must be technically sound.
Queuing systems are classified as follows.
1 According to queue length restrictions:
QS with losses – the request leaves the QS unserved if at the time of its arrival all channels are busy;
Query without loss - the request takes a queue, even if all channels
busy;
QS with queue length restrictions m or waiting time: if there is a limit on the queue, then the newly arrived ( m The +1)th requirement leaves the system unserved (for example, the limited capacity of the storage area in front of a gas station).
2 By number of service channels n:
Single channel: n=1;
Multichannel n≥2.
3 By type of service channels:
Same type (universal);
Various types (specialized).
4 In order of service:
Single-phase – maintenance is performed on one device (station);
Multiphase - requirements are sequentially passed through several service devices (for example, maintenance production lines; car assembly line; external care line: cleaning → washing → drying → polishing).
5 By service priority:
Without priority – requirements are serviced in the order they are received by the QS;
With priority - requirements are serviced depending on the priority rank assigned to them upon receipt (for example, refueling of ambulances at a gas station; priority repairs at the ATP of vehicles that bring the greatest profit in transportation).
6 By the size of the incoming flow of requirements:
With unlimited incoming flow;
With a limited incoming flow (for example, in the case of pre-registration for certain types of work and services).
7 According to the structure of the QS:
Closed - the incoming flow of demands, all other things being equal, depends on the number of previously serviced requests (complex ATP servicing only its own cars ( 5 in Figure 5.6));
Open – the incoming flow of demands does not depend on the number of previously serviced ones: public gas stations, a store selling spare parts.
8 According to the relationship of service devices:
With mutual assistance - the capacity of the devices is variable and depends on the occupancy of other devices: team maintenance of several service stations; use of "sliding" workers;
Without mutual assistance - the throughput of the device does not depend on the operation of other QS devices.
In relation to the technical operation of automobiles, closed and open, single- and multi-channel queuing systems are becoming widespread, with the same type or specialized service devices, with single- or multi-phase service, without losses or with restrictions on the length of the queue or the time spent in it.
The following parameters are used as indicators of the performance of the QS.
Service intensity
where ω is the demand flow parameter.
shows the number of requests arriving per unit of time, i.e.
| A=ω g, | (5.13) |
Where g- .
Relative Bandwidth determines the share of serviced requests from their total number.
The likelihood that that all posts are free R 0 , characterizes the state of the system in which all objects are operational and do not require technical interventions, i.e. there are no requirements.
Probability of denial of service P otk makes sense for a QS with losses and with a limitation on the length of the queue or the time spent in it. It shows the share of requirements “lost” for the system.
R och defines a system state in which all servicing devices are busy, and the next request “stands” in a queue with the number of waiting requests r.
The dependencies for determining the named parameters of the functioning of the QS are determined by its structure.
Where n zan - .
Time required to communicate with the system:
QS with losses
| t syst = GT d; | (5.16) |
Lossless QS
| t syst = t d + t cool | (5.17) |
| AND=WITH 1 r+WITH 2 n dn +( WITH 1 +C 2)ρ, | (5.18) |
Where WITH 1 - cost of car idle time in line;
r- average queue length;
WITH 2 - cost of downtime of the service channel;
nсн - number of idle (free) channels;
t ozh - average time spent in queue.
Due to the randomness of the incoming flow of requirements and the duration of their completion, there is always some average number of idle vehicles. Therefore, it is necessary to distribute the number of service devices (posts, jobs, performers) among various subsystems so that And= min. This class of problems deals with discrete changes in parameters, since the number of devices can only change in a discrete manner. Therefore, when analyzing the vehicle performance system, methods from operations research, queuing theory, linear, nonlinear and dynamic programming and simulation are used.
Example. The service station has one diagnostic post ( n= 1). The queue length is limited to two cars ( t= 2). Determine the performance parameters of the diagnostic post if the intensity of the flow of requirements for diagnosis is on average A=2 required/hour, diagnostic duration t d = 0.4 hours
Diagnostic intensity μ=1/0.4=2.5.
Reduced flux density ρ=2/2.5=0.8.
The probability that a post is vacant is
P 0 =(1-ρ)/(1-ρ m +2)=(1-0,8)/(1-0,8 4)=0,339.
Probability of queue formation
P och =ρ 2 R 0 =0,8 2 0,339=0,217.
Probability of denial of service
P otk =ρ m+1 (1-ρ)/(1-ρ m +2)=0,8 3 (1-0,8)/(1-0,84)=0,173.
Relative Bandwidth
g=1-P otk =1-0.173=0.827.
Absolute throughput
A=2 0.827=1.654 required/hour.
Average number of occupied posts or probability of a post being loaded
n zan =(ρ-ρ m+2)/(1-ρ m +2)=(0,8-0,8 4)/(1-0,8 4)=0,661=1-P 0 .
Average number of requests in queue
Average time a request spends in queue
t cool = r/ω=0.564/2=0.282 h.
Example. At the motor transport enterprise there is one diagnostic post ( n= 1). In this case, the queue length is practically unlimited. Determine the performance parameters of the diagnostic post if the cost of vehicle idle time in the queue is WITH 1 = 20 re (units of account) per shift, and the cost of downtime of posts WITH 2 = 15 re The remaining initial data are the same as for the previous example.
Probability that a post is vacant
P 0 =1-ρ=1-0.8=0.2.
Probability of queue formation
P och =ρ 2 R 0 =0,8 2 0,2=0,128.
Relative Bandwidth g=1, since all targeted cars will pass through the diagnostic station.
Absolute throughput A=ω=2 required/hour.
Average number of occupied posts n zan =ρ=0.8.
r=ρ 2 /(1-ρ)=0.8 2 /(1-0.8)=3.2.
Average waiting time in queue
t coolant =ρ 2 /(1-ρ)/μ=0.8 2 /(1-0.8)/2.5=1.6.
System operating costs
AND=WITH 1 r+WITH 2 n dn +( WITH 1 +C 2)ρ=20 3.2+15 0.2+(20+15) 0.8=95.0 re/shift.
Example. At the same motor transport enterprise, the number of diagnostic posts has been increased to two ( n=2), i.e. a multi-channel system has been created. Since capital investments (space, equipment, etc.) are required to create a second post, the cost of downtime of maintenance equipment increases to WITH' 1 =22 re. Determine the performance parameters of the diagnostic system. The rest of the initial data is the same as for the previous example.
The diagnostic intensity and reduced flux density remain the same: μ=2.5, ρ=0.8.
The probability that both posts are vacant is
R 0 =1: 
=0,294.
Probability of queue formation
P och =ρ n P 0 /n!=0,8 2 0,294/2=0,094,
those. 37% lower than in the previous example.
Relative Bandwidth g=1, since all cars will go through diagnostic posts.
Absolute throughput A=2 required/hour
Average number of occupied posts n zan =ρ=0.8.
Average number of requests in queue
r=ρ P very /( n-ρ)=0.8 2 0.094/(2-0.8)=0.063.
Average time spent in queue
t cool = P very /( n-ρ)/μ=0.094/(2-0.8)/2.5=0.031.
System operating costs
AND=WITH 1 r+WITH 2 n dn +( WITH 1 +C 2)ρ=20 0.063+22 1.2+(20+22) 0.8=61.26 re/shift,
those. 1.55 times lower than under the same conditions for one diagnostic post, mainly due to the reduction in the queue of cars for diagnostics and the waiting time for cars by more than 50 times. Therefore, the construction of a second diagnostic post in the conditions under consideration is advisable. Using formula (5.18) from the condition AND 1 =And 2 , it is possible to estimate the maximum values of the cost of downtime of service facilities during the construction and equipping of the second diagnostic station, which in the considered example is C 2 pr = 39 re.
