A SIMULATION ALGORITHM FOR QUEUING SYSTEMS WITH PARALLEL WORKING STATIONS HAVING ONE'S OWN QUEUE FOR EVERY STATION WITH HOL SERVING DISCIPLINE
Abstract We can think the queuing system as having only one queue to all stations, where the client joins in order to be served when a free station exists or every station has its own queue where the arrived clients joins. Also, the queued clients are served based on serving discipline, FIFO or based on dividing in priority classes of the customers. This paper presents a simulation algorithm for the queuing system, where very station has own queue and serving discipline is of Head of Line type. One proves the polynomial complexity of the proposed algorithm. Also, we present the object oriented approach of the system.
The queuing models deal with systems that have agglomerations. Such models assume a random generation mechanism for the arrivals in the system, for the clients serving and the same serving discipline. In the traditional approach, where the stations topology is parallel and there is only one queue to all stations, the arrived client is immediately served, if there is a station in laziness otherwise it joins to the queue. Also, based on a serving discipline (FIFO, HOL etc.), when a station finishes a service and own queue is not empty, a new client is selected in order to be served.
If there are no clients in the queue, the station becomes lazy. In the following we assume that every station has its own queue. So, when a client arrives in system, it chooses a station based on a random mechanism, described in . Also, when one server finishes serving a customer, if the queue is not empty, a client is selected for serving based one the Head-of-Line (HOL) discipline, that consists in: if m is the class number, the i-class customer have serving priority versus those of j-class, if ; inside the same class, the clients are served in FIFO order; when a customer arrives and there is a an idle server, the client is immediately served, otherwise it is last queued inside his class and when a station finish a service the first client of the high class is selected to be served
There are a lot of real systems that can be abstracted in this mode. The CPU of a computer divides the processes in priority class; also, a printing server in a network divides the file in the same mode. As a general rule, a computing system has resources which the clients (processes) try to access. These resources can have the same type. In this case, we assume that there is only one queue to all resources or every resource has its own queue. In  one queuing system simulation algorithm is presented for the case with only one queue for all stations and HOL discipline and in  it is proposed such studying method for the queuing systems, with parallel stations having own queue and FIFO discipline. In this paper we will consider the same topology of station but the HOL discipline, which is a generalization of the FIFO discipline.
2. The model entities and the simulation mechanism
i) If then by a simple calculus we can proof .
ii) Also we have and .
iii) When all stations are free, i.e. nc(i)=0, for all i, , i=1,..,n we can consider one of the two possibilities:
Also, every station is characterized by the following variables:
For i station, we denote the end of the serving event time, that is, the station clock. If the station is free and there aren't clients queued for the station, the variable is .
The bi-dimensional vector holds the number of the j priority class of i station, at a given time; obviously is true.
The tri-dimensional vector holds the serving time values needed for the corresponding clients queued at the station i. Here the value represents the amount of time needed to serve the client k queued client of j priority class at the station i ..
We define the index ip as being
The algorithm that we are going to present follows the "next event"("minimum time") rule. If the moment of a serving end, in every moment it's possible to have one of the two events:
Handling of an arrival (arrival event); this event arrises when; a new arrival is generated.
Handling of an end of service event (Cevent), if .
Remark 2 If we define a simulation cycle as the handling of an arrival or of an event of type end of service, then we can say that the simulation consists of these cycles. Considering the hypothesis that the number of arrivals is smaller than the number of servings, the number of servings is less than Tnra. Also, if we consider the Tnra of a sufficiently great value, we can say that the great majority of clients are served. This leads to the conclusion that the number of cycles executed, in the case of the FIFO discipline, is smaller than 2Tnra.
Every handled event ends with an update of the following
, where represents the total waiting time for the queued clients of the j priority class at the working station i;
, where represents the total laziness amount of time for the working station i .
In addition, after every end of service event the following are updated:
, where represents the total amount of time spent to serve client of j class, by the working station i;
, where represents the total number of clients from j class served by the working station i.
At the end of the simulation we determine the following global efficiency factors:
is the average amount of time spent by the queued clients waiting to be served by the working station i and it is given by the formula:
is the average amount of time spent by the queued clients of j class waiting to be served by all working stations and it is given by the formula:
represents the average amount of time spent by the working station i to serve clients. This value is given by the formula:
If Ltime is the number of time units of the entire simulation, represents the i working station laziness coefficient . This value is given by the formula:
We denote the average length of the queue for the working station i, and is given by :
3. Algorithm description and the complexity study
The following pseudo-code procedure describes "the main function" of the simulation algorithm of this queuing system type.
Read(Random generation parameters);
for i=1 to n do
for j=1 to m do
ncq(i,j) 0; Tts(i,i) 0;Nrs(i,j) 0;;Tw(i,j)
While Nra Tnra do
if Atime Ctime(ip) then
tipev Aev;timpev Atime;
tipev Cev;timpev Ctime(ip);
if nc(ip)>1 then FinServ(ip, Ctime, Ts, Tss, nc)
MinCtime determines the index of station that firstly will finish the service and it was described in . Depending on the type of the event, the next procedure will update the previous mentioned arrays:
for i= to n do
for j=1 to m do
for i=i,n do
if Ctime (i)= then Tlen(i) Tlen(i)+timpev-Ltime
if tipev="Cev" then
Nrs(ip,ic) Nrs(ip,ic)+1;Tts(ip,ic) Tts(ip)+Tss(ip)
Besides the amounts generated in the algorithm presented in , the GenArriv procedure will generate the priority client class.
Atime Atime+IntAriv;Nra Nra+1;Discr(nc,X,NrSt)
The JoinStation procedure will join the arrived client to a generated station; if the station is free, it will be immediately served otherwise it will be introduced in the queue.
Ctime(NrSt) Atime+Stime;Tss(NrSt) Stime
When the queue of the station is not empty, the FinServ procedure will select the first client of high class, in order to be served.
while ncq(ip,ic)=0 do ic ic+1;
Ctime(ip) Ctime(ip)+Ts(ip,ic,1); Tss(ip) Ts(ip,,ic,1);
for i=1 to ncq(ip,ic)-1 do Ts(ip,ic,i) Ts(ip,ic,i+1);
Algorithm complexity. We assume that the time needed to resolve a comparison and the time needed to assign a value to a variable is O(1). With these assumptions the complexity needed to run the algorithm is: initialization phase - n steps; the simulation algorithm will execute at most 2*Tnra cycles that handle either an arrival in the system or an end of service. The numbers of arrivals is greater but approximately equal to the number of end-of-service cycles
If we have an Aevent event: Execution of MinCtime - O(n) but can be considered O(1) since n is small; Execution of PrelVectEfFact- O(m*n) but can be considered O(1) since n,m have small values; Execution of JoinStation - O(1); Execution GenArrival- known polynomial complexity- we consider it O(1).
If we have a Cevent event: Execution of PrelVectEfFact- O(m*n) but can be considered O(1) since n,m have small values; Execution of FinServ- O(1)
Summing the complexities identified above we can conclude that the complexity of the algorithm is O(2*Tnra).
4. The OOP approach
The use of object in programming is a way of shortening the distance between the real life and the way it has to be modeled for the computer world. In order to generate the simulation needed we use model presented in , with slightly modifications. Inserting the priority classes modifies the client generation and handling and the efficiency information gathering. The HOL discipline had to be implemented. We had to implement also means to retain information, such as: the number of clients belonging to certain priority class, served by a station; the total time of wait for the clients belonging to a certain priority class.
4. Models Validity and practical considerations
In the following we consider 10,000 arrivals simulated.
Case 1. n=1, m=1. This model is the same with
ii) Case 2.n=2, m=2. This model implements HOL having two serving stations and two priority classes. We shall consider l m The obtained results are presented in the table 2. As we can see the values are approximately equal for the two simulated stations and we can observe a slightly difference in matter of time of wait between the two priority classes. The class with a bigger priority (the "0" class) has a smaller time of wait value. To increase this gap we increase the frequency of arrivals as in:
iii) Case 3 n=2, m=2. This model implements HOL having two serving stations and two priority classes. We shall consider l m .The obtained results are presented in the table 3.
Table 1. The results for case 1
MTw(0 class )
MTw (1 class)
Table 2.The results for case 2
1st Simulated station
2nd Simulated station
MTw( 0 class)
MTw (1 class)
Table 3.The results for case 2
As we can see, the gap between the time of wait for the clients with different priority is bigger and more easy to observe. The privileged clients must wait a smaller amount of time until they are served.
Conclusions. We remark that in both case 2 and 3 we obtain results approximately similar. We constructed the first case simulation to verify the analytical model. For the next two simulations we obtained the results as expected. If the probability of choosing a station is equal in the case of zero client's number, the efficiency factors calculated in for the two stations are similar. The difference can be observed between the time of wait of a client with bigger priority and a client with a smaller priority.
Cormen, T.H., Leirson, C.E, Rivest R.L.: Introductions to Algorithms. MIT Press, Cambridge, 1992.
Florea, I.: One Algorithmic Approach of the Parallel Multi Server Queuing System of Head of Line Type, Bulletin of the Transilvania University of Brasov, vol. 8(43), p.22-30, 2002
Florea, I., Carstea A.: A Simulation Algorithm for Queuing Systems with Parallel Working Stations Having one's Own Queue for Every Station, Bulletin of the Transilvania University of Brasov, vol. 11(46),(to appear),2005
Gross, D., Harris C.: Foundamentals of Queuing Theory, John Wiley & Sons, NewYork,1998.
Tanner, M. : Practical Queuing Analysis. McGraw-Hill Book Company, 1995.
Vaduva, I.: Computer Simulation Model., Technical Publishing House, Bucharest, 1977
Vaduva, I., Stoica, M., Odagescu, I.: Economy Processes Simulation. Technical, Publishing House, Bucharest, 1983.
Algoritm de simulare pentru sistemele de asteptare cu statii de servire paralele, cu coada la fiecare statie si disciplina de servire HOL
Rezumat Putem considera un sistem de asteptare ca avand o coada unica pentru toate statiile, unde sunt introdusi clientii care asteapta sa fie serviti cind o statie devine libera sau fiecare statie are propria sa coada unde sunt introdusi clientii sositi. De asemenea, clientii din coada sunt serviti pe baza unei discipline de server, FIFO sau bazata pe impartirea clientilor in clase de prioritati . Aceasta lucrare, prezinta un algoritm de simulare pentru sistemele de asteptare, unde fiecare statie are propria coada,iar disciplina de servire este HOL. Se demonstreaza complexitatea polinomiala a algoritmului propus. De asemenea, prezentam abordarea orientata pe obiecte a sistemului.
Politica de confidentialitate|
2023 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.
|vezi toate proiectele|
|PROIECT DE LECTIE CLASA A II-A, Educatie plastica, Tehnica marmorata|
|PROIECT DIDACTIC 5-7 ani activitate matematica - „Cum este si cum nu este aceasta piesa”|
|Proiect Circuite Digitale|
|Organizarea si conducerea procesului tehnologic proiectat|
Lucrari de diploma
|vezi toate lucrarile de diploma|
|LUCRARE DE DIPLOMA - Rolul asistentului medical in ingrijirea pacientului cu A.V.C.|
|Spatiul romanesc, intre diplomatie si conflict in Evul Mediu|
|Lucrare de diploma managementul firmei “diagnosticul si evaluarea firmei”|
|Lucrare de diploma Facultatea de Textile – Pielarie - Tehnologia confectiilor din piele si inlocuitori - PROIECTAREA CONSTRUCTIV TEHNOLOGICA A UNUI PR|
|vezi toate lucrarile de licenta|
|Lucrare de licenta contabilitate si informatica de gestiune - politici si tratamente contabile privind leasingul (ias 17). prevalenta economicului asupra juridicului|
|Lucrare de licenta educatie fizica si sport - sistemul de selectie in jocul de handbal pentru copii de 10-11 ani in concordanta cu cerintele handbalul|
|Lucrare de licenta - cercetare si analiza financiara asupra deseurilor de ambalaje la sc.ambalaje sa|
|LUCRARE DE LICENTA - Asigurarea calitatii la firma Trans|
|vezi toate lucrarile de doctorat|
|Diagnosticul ecografic in unele afectiuni gastroduodenale si hepatobiliare la animalele de companie - TEZA DE DOCTORAT|
|Doctorat - Modele dinamice de simulare ale accidentelor rutiere produse intre autovehicul si pieton|
|LUCRARE DE DOCTORAT ZOOTEHNIE - AMELIORARE - Estimarea valorii economice a caracterelor din obiectivul ameliorarii intr-o linie materna de porcine|
Proiecte de atestat
|vezi toate proiectele de atestat|
|Lucrare atestat informatica - „administrarea gradinii botanice”|
|Lucrare atestat Tehnician operator tehnica de calcul - Sursa de tensiune cu tranzistoare npn|
|ATESTAT PROFESIONAL LA INFORMATICA - programare FoxPro for Windows|
|Proiect atestat tehnician in turism - carnaval la venezia|
|Algoritmul Dijkstra pentru gasirea celui mai scurt traseu intre doua noduri date ale unui graf|
|Informatica - ce este informatica?|
|Infrastructura tehnologica a CE. Server-e Web|
|Alte tipuri de produse software|
|Elementele de baza ale unui template Joomla|
|Algoritmi si scheme logice|
|A SIMULATION ALGORITHM FOR QUEUING SYSTEMS WITH PARALLEL WORKING STATIONS HAVING ONE'S OWN QUEUE FOR EVERY STATION WITH HOL SERVING DISCIPLINE|
|Termeni si conditii|
|Creeaza si tu|